In this paper we examine the probl of how to give hands-on assignments in a database syst internals course. We argue that current approaches are inadequate, either because they are not sufficiently comprehensive or because they require using software that has a steep learning curve. We then describe SimpleDB, which is software written expressly for such a course. SimpleDB is a database syst in the spirit of Minibase. Unlike Minibase, however, it supports multiple users and transactions via JDBC, and its code is easy to read and modify. We then describe a course that we teach using SimpleDB, and discuss the educational benefits resulting from it.

No abstract available.

Enterprise databases are comprised of multiple local databases that exchange information. The component databases will rarely have the same native form, so one must map between the supplier’s native interface and the consumer’s. Using a SQL view to define this map is convenient and powerful, because it provides not just an evaluation mechanism, but also query, and (to some degree) update and trigger capabilities. However, SQL views do not map the critical metadata (e.g., security, source attribution, and quality information) between supplier and consumer. We present motivation, theory, and some pragmatics for creating an administrator’s assistant. We propose a framework into which one would put definitions and translators for individual metadata types. The underlying theory supports consistent (but not complete) inference services, to add value and to get maximal value from the currently available knowledge. We also discuss why support for collaboration and negotiation are essential such administrative environments, and sketch an initial approach.

Large organizations need to exchange information among many separately developed systems. In order for this exchange to be useful, the individual systems must agree on the meaning of their exchanged data. That is, the organization must ensure semantic interoperability . This paper provides a theory of semantic values as a unit of exchange that facilitates semantic interoperability betweeen heterogeneous information systems. We show how semantic values can either be stored explicitly or be defined by environments . A system architecture is presented that allows autonomous components to share semantic values. The key component in this architecture is called the context mediator , whose job is to identify and construct the semantic values being sent, to determine when the exchange is meaningful, and to convert the semantic values to the form required by the receiver. Our theory is then applied to the relational model. We provide an interpretation of standard SQL queries in which context conversions and manipulations are transparent to the user. We also introduce an extension of SQL, called Context-SQL (C-SQL), in which the context of a semantic value can be explicitly accessed and updated. Finally, we describe the implementation of a prototype context mediator for a relational C-SQL system.

Two important features of modern database models are support for complex data structures and support for high-level data retrieval and update. The first issue has been studied by the development of various semantic data models; the second issue has been studied through universal relation data models. How the advantages of these two approaches can be combined is presently examined. A new data model that incorporates standard concepts from semantic data models such as entities, aggregations, and ISA hierarchies is introduced. It is then shown how nonnavigational queries and updates can be interpreted in this model. The main contribution is to demonstrate how universal relation techniques can be extended to a more powerful data model. Moreover, the semantic constructs of the model allow one to eliminate many of the limitations of previous universal relation models.>

The use of inference rules to support intelligent data processing is an increasingly important tool in many areas of computer science. In database systems, rules are used in semantic query optimization as a method for reducing query processing costs. The savings is dependent on the ability of experts to supply a set of useful rules and the ability of the optimizer to quickly find the appropriate transformations generated by these rules. Unfortunately, the most useful rules are not always those that would or could be specified by an expert. This paper describes the architecture of a system having two interrelated components: a combined conventional/semantic query optimizer, and an automatic rule deriver. Our automatic rule derivation method uses intermediate results from the optimization process to direct the search for learning new rules. Unlike a system employing only user-specified rules, a system with an automatic capability can derive rules that may be true only in the current state of the database and can modify the rule set to reflect changes in the database and its usage pattern. This system has been implemented as an extension of the EXODUS conventional query optimizer generator. We describe the implementation, and show how semantic query optimization is an extension of conventional optimization in this context.

The concept of annotation from object-oriented languages is adapted to object-oriented databases. It is shown how annotations can be used to model activities such as constraint checking, default values, and triggers. Annotations also are an appropriate way to model different versioning concepts. This paper discusses three kinds of versioning—histories, revisions, and alternatives—and demonstrates how each one can be modeled effectively using annotations. The use of annotations also allows other kinds of versioning to be defined extensibly, and arbitrary combinations of versions can be handled easily.

An examination is made of existing rule-based optimizers, showing that they have significant limitations. A new approach to optimization based on the idea of modules is presented. An optimizer is divided into several interconnected modules. Each module has its own set of rewrite rules and can be implemented differently according to how the rules are used. This modular approach avoids the limitations of existing systems and supports flexible optimizer prototyping, efficient optimize-time search, and convenient access to metadata. To illustrate these ideas, a decomposition into modules is given for an example relational query optimizer.>

A description is given of extended relations, a generalization of ordinary relations in which tuple identifiers (tids) can appear as attribute values. The relational algebra is extended to include new operators that manipulate these tids; the resulting algebra is called the tid-algebra. The theorems of the tid-algebra are shown to provide a formal basis for optimizer transformations that involve high-level access structures. Three particular access structures-secondary indices, join indices, and join extensions-are examined in detail.>

Specialization hierarchies typically are treated as type-level constructs and are used to define various inheritance mechanisms. In this paper we consider specialization at the level of objects. We show that doing so creates a more flexible and powerful notion of inheritance by allowing objects to define their own inheritance path. Object specialization can also be used to model certain forms of versioning, implement data abstraction, and provide a “classless” prototype-based language interface to the user.

The power of the relational model with inclusion dependencies is compared with that of the universal instance model. A characterization of allowable sets of inclusion dependencies is made, the relational and universal instance models are proved equivalent given this restriction.

This paper examines the technique of adding attributes to a relational database scheme. It is shown that doing so can result in an improvement in the conceptual simplicity and efficiency of the scheme. Some well-known non-independent schemes are made independent by adding attributes, results are given to support the conjecture that all schemes can be made independent as well.

We introduce a restriction on the structure of a database scheme, called the primary key condition, and show that this condition characterizes independent database schemes when constraints are presented as keys. The primary key condition provides added insight into the structure of independent schemes, and leads to a general design methodology. We describe a linear-time algorithm for recognizing independent schemes.

Properties of join dependencies are discussed, along wRh the dlfficuRles arising m their axlomaUzaUon The notion of jom dependency ~s generalized, and a set of axioms for these new dependenoes ts presented.A sunulat~on of the chase procedure Is used to show that this set is complete for full jom dependencies.

According to database theory, a database designer can specify any set of data dependencies, no matter how complex, to constrain a database scheme. This paper investigates how much complexity is actually needed in real-world situations. It is shown that every "natural" set of mvd's must belong to a class of mvd's called conflict-free. Conflict-free sets of mvd's have the desirable property that they allow a unique 4NF dependency preserving database scheme; moreover, non conflict-free sets have no such normalization. If a set of mvd's is not conflict-free, then the dependencies are inadequately specified; there are semantic concepts that are unrepresented in the scheme. These concepts are isolated, and it is shown that adding these concepts amounts to making the set of mvd's conflict-free.

Standard semantics for the relational model considers domain values to be objects, which assume the roles indicated by the name of its associated attribute. Entities are related to each other to form tuples in a relation; attributes are also interrelated, but in this case the exact relationships have always been left implied or "intuitive." This paper introduces renaming rules, which are a way to formally specify these relationships. Properties of these rules are discussed, and a complete axiomatization is presented.Renaming rules allow meaningful equi-joins to be couched in terms of natural joins. They are intimately associated with the abstraction concept of generalization, and provide a natural semantics and theory for the relational algebraic operatiors select and union. These operators in turn use Smith's subcategory functional dependencies to achieve a better decomposition of a database scheme; to this end, a general normal form algorithm is presented.

Denotational semantics was introduced by Strachey as a means of defining semantics of programming languages. It's mathematical foundation was justified by Scott [14] in 1969 when he introduced continuous lattices to model data types and showed how to solve reflexive domain equations.