Abstract: The book describes the Modula-90K database programming
system. The system consists of the Modula-90K programming language, libraries,
interactive environment, and the debugging subsystem. The introduction
briefly discusses the features of the Modula-90K programming language.
The book is meant for the users of the system as well as for experts specializing
in the area of database programming languages.
Abstract: The concept of an object-oriented database programming language (OODBPL) is appealing because it has the potential of combining the advantages of object orientation and database programming to yield a powerful and universal programming language design.
A uniform and consistent combination of object orientation and database programming, however, is not straightforward. Since one of the main components of an object-oriented programming language is its type system, one of the first problems that arise during an OODBPL design is related to the development of a uniform, consistent, and theoretically sound type system that is sufficiently expressive to satisfy the combined needs of object orientation and database programming.
This dissertation presents the design of a type system suitable for
object-oriented database programming. The type system
has a unique combination of uniformity, expressibility, verifiability,
and theoretically proven soundness. It also possesses features that make
it suitable for database programming, such as seamless integration of imperative
types and features, precise query typing via union and intersection types,
separation among three abstraction layers providing a high degree of code
reuse, parametric polymorphism, extensibility, and dynamic type analysis
capabilities.
In the process of type system development, a theoretical framework for dealing with type systems that combine parametric and inclusion polymorphism is established. Due to its modular construction, this framework can be easily extended and used beyond the scope of this dissertation. Another contribution of this work is an extensive analysis of existing and proposed type systems from the point of view of the set of requirements related to object orientation and database programming.
This research leads to the development of a uniform and theoretically sound OODBPL that can successfully utilize the power inherent in both object orientation and database programming paradigms. This will eventually lead to the development and implementation of a uniform object-oriented database system that will use the OODBPL as its main programming and query engine.
Keywords: language design, type system, multiple dispatch, object-oriented languages, parametricity
Supervisors: Prof.
Tamer Özsu and
Prof.
Duane Szafron.
Abstract: The concept of an object-oriented database programming language (OODBPL) is appealing because it has the potential of combining the advantages of object orientation and database programming to yield a powerful and universal programming language design. A uniform and consistent combination of object orientation and database programming, however, is not straightforward. Since one of the main components of an object-oriented programming language is its type system, one of the first problems that arises during an OODBPL design is related to the development of a uniform, consistent, and theoretically sound type system that is sufficiently expressive to satisfy the combined needs of object orientation and database programming.The purpose of this article is to answer two questions: "What are the requirements that a modern type system for an object-oriented database programming language should satisfy?" and "Are there any type systems developed to-date that satisfy these requirements?". In order to answer the first question, we compile the set of requirements that an OODBPL type system should satisfy. We then use this set of requirements to evaluate more than 30 existing type systems. The result of this extensive analysis shows that while each of the requirements is satisfied by at least one type system, no type system satisfies all of them. It also enables identification of the mechanisms that lie behind the strengths and weaknesses of the current type systems.
Article: PDF
Official ACM version
Article: Postscript
Abstract: Multiple Row Displacement (MRD) is a new dispatch technique for multi-method languages. It is based on compressing an n-dimensional table using an extension of the single-receiver row displacement mechanism. This paper presents the new algorithm and provides experimental results that compare it with implementations of existing techniques: compressed n-dimensional tables, look-up automata and single-receiver projection. MRD uses comparable space to the other techniques, but has faster dispatch performance.
Article: Postscript
Compressed
postscript
Abstract: In this paper we present a model that supports a clean separation between the concepts of interface, implementation, and representation. We present several problems that are difficult to solve in the absence of such separation and describe how the proposed model can be used to provide a solution. We also describe the principles that can be used to implement the proposed model in an existing object-oriented database management system.
Article:
Postscript
Compressed
postscript
Presentation:
Postscript
Compressed
postscript
Abstract: The fundamental question about a temporal model is "what is its underlying temporal structure?" More specifically, what are the temporal primitives supported in the model, what temporal domains are available over these primitives, and whether the primitives are determinate or indeterminate? In this paper a simple, general framework for supporting temporal primitives (instants, intervals, sets of intervals) is presented. The framework allows seamless integration of dense and discrete temporal domains of time over a linearly ordered, unbounded point structure. The framework also provides a set-theoretic basis that allows uniform treatment of determinate and indeterminate temporal primitives.
Article: Postscript Compressed postscript Presentation: Postscript Compressed postscript
Keywords: implementation, database programming languages, AVL-trees
Supervisor: Prof. Vladimir Lvovitch Arlazarov.
Abstract: A new technique for multi-method dispatch is presented. It operates by performing projections onto single-receiver dispatch tables, and thus benefits from existing research into single-receiver dispatch techniques. It provides method dispatch in O(k), where k is the arity of the method. It has the highest number of dispatches to memory ratio of all existing table-based multi-method dispatch techniques. The technique applies both to traditional non-reflexive languages and to reflexive languages where methods and types can be added and removed at run-time.
Keywords: language design, implementation, multiple dispatch,
object-oriented languages
Abstract: In this paper we present a model that supports a clean separation between the concepts of interface, implementation, and representation. We present several problems that are difficult to solve in the absence of such separation and describe how the proposed model can be used to provide a solution. We also describe the principles that can be used to implement the proposed model in an existing object-oriented database management system.
Keywords: object-oriented databases, implementation, inheritance, type systems
Abstract: In this paper we present a type system that combines inclusion and parametric polymorphism with behaviors (multi-methods) and precise function typing. Type declarations allow user-definable variance specification of type parameters and user-definable subtyping between types of different kind. Our approach involves use of type specification logic which translates type specifications into types. Types are computable values. Type computation of types generated by the logic results in precise function and behavior typing. As a proof of concept, a toy language with its syntax, semantics, and subject reduction theorem is presented.
Keywords: type systems, typechecking, logic, polymorphism
Abstract: Most of the work in modeling time in information systems has concentrated on issues such as support for historical information and providing query facilities to manipulate such information. In doing so, some simplistic view of the underling nature of time has been assumed. However, the domain of time is far from being simplistic. In this paper, we outline the various issues which arise in modeling basic temporal entities and propose solutions to these issues. More specifically, we note that the nature of temporal information can either be anchored (e.g., October 25, 1995) or unanchored (e.g., 1 week), and is usually available in multiple granularities (e.g., the airline flight departure and arrival times are usually given in minutes, while the history of the salary of an employee is usually recorded in days). Physical temporal information also needs to be represented in a manner so as to be human readable. This is achieved using calenders. In this work, we show how both anchored and unanchored temporal entities are represented within the context of calenders. We discuss how calenders provide relationships between multiple granularities and facilitate the conversion of anchored and unanchored times from one granularity to another. We also give the semantics of various operations on anchored and unanchored times.
Keywords: temporal databases, object models, calenders, granularity
Abstract: In this work, we present a uniform behavioral temporal object model which includes a rich and extensible set of types and behaviors to support various notions of time. Our temporal model supports the continuous and discrete domains of time. It also supports various specifications of time, namely, time instants, time intervals and time spans. Two issues that frequently arise in real-world applications which deal with temporal information are the need to consistently store and operate on temporal information that is comprised of different granularities, and the ability to represent indeterminate temporal information. Temporal indeterminacy arises when we know for certain that an event did occur, but exactly when it occured is unknown. Our model provides a uniform framework that supports different granularities of time and temporal indeterminacy. We show how different granularities can be converted to each other, and how this leads to temporal indeterminacy. We further show how continuous and discrete indeterminate time intervals, spans and instants are consistently modeled in our framework.
Keywords: temporal databases, object models, granularity, incomplete
information, temporal indeterminacy.