Conjunctive queries are generalized so that inequality comparisons can be made between elements of the query. Algorithms for containment and equivalence of such “inequality queries” are given, under the assumption that the data domains are dense and totally ordered. In general, containment does not imply the existence of homomorphisms (containment mappings), but the homomorphism property does exist for subclasses of inequality queries. A minimization algorithm is defined using the equivalence algorithm. It is first shown that the constants appearing in a query can be divided into “essential” and “nonessential” subgroups. The minimum query can be nondeterministically guessed using only the essential constants of the original query.

Abstract We describe the implementation of a flexible data storage system for the UNIX environment that has been designed as an experimental vehicle for building database management systems. The storage component forms a foundation upon which a variety of database systems can be constructed including support for unconventional types of data. We describe the system architecture, the design decisions incorporated within its implementation, our experiences in developing this large piece of software, and the applications that have been built on top of it.

Access to a relation R m a relational database is sometimes based on how R joins with other relations rather than on what values appear m the attributes of R-tuples Usmg sunple predicate locks forces the entire relation to be locked m these cases.A technique is presented which allows locking of the smallest possible set oftuples even when the selecuon is based on joins w~th other relauons The algonthms are based on a generalization of tableaux The tableaux used here can represent relational algebra quenes wtth any of the domain companson operators =, #, <, _<, >, and >-..

This paper addresses questions of efficiency in relational databases. We present polynomial time algorithms for minimizing and testing equivalence of what we call “fan-out free” queries. The fan-out free queries form a more general and more powerful subclass of the conjunctive queries than those previously studied. In particular, they can be used to express questions about transitive properties of databases, questions that are impossible to express if one operates under the assumption, implicit in previous work, that each variable has an assigned “type,” and hence can only refer to one fixed attribute of a relation. Our algorithms are graph-theoretic in nature, and the equivalence algorithm can be viewed as solving a special case of the graph isomorphism problem (by reducing it to a series of labelled forest isomorphism questions).

We consider the problem of optimizing conjunctive queries in the presence of inclusion and functional dependencies. We show that the problem of containment (and hence those of equivalence and non-minimality) is in NP when either (a) there are no functional dependencies or (b) the set of dependencies is what we call key-based. These results assume that infinite databases are allowed. If only finite databases are allowed, new containments may arise, as we illustrate by an example. We also prove a "compactness" theorem that shows that no such examples can exist for case (b).

An increasingly important part of information processing today involves the taking of counts, sums, averages, and other statistical or aggregate quantities. The "Abe" query language is designed to make formulation of complicated aggregations simple. Access path selection in Abe finds efficient ways to execute these complicated queries. Access paths for Abe queries perform "aggregate joins", that is, they compute aggregate quantities at the same time as they join subqueries with parent queries. This can be done using index scans or merging scans depending on how many "partitions" need to be accessed.

Aggregate functtons m relattonal query languages allow intricate reports to be written.In this paper aggregate functions are precisely defined The definition does not use the notion of "duphcates."gelattonal algebra and relattonal calculus are extended m a general and natural fashton to include aggregate functions It is shown that the languages so extended have eqmvalent expressive power Categories and Subject Descriptors.H 2 3 [

The interconnection between conceptual and external levels of a relational database is made precise in terms of the notion of “interpretation” between first-order languages. This is then used to obtain a methodology for discovering constraints at the external level that are “implied” by constraints at the conceptual level and by conceptual-to-external mappings. It is also seen that these concepts are important in other database issues, namely, automatic program conversion, database design, and compile-time error checking of embedded database languages. Although this the deals exclusively with the relational approach, it also discusses how these ideas can be extended to hierarchical and network databases.

A relational database models some part of the real world by a set of relations and a set of constraints. The constraints model properties of the stored information and must be maintained true at all times. For views defined over physically stored (base) relations, this is done by determining whether the view constraints are logical consequences of base relation constraints. A technique for determining such valid view constraints is presented in this paper. A generalization of the tableau chase is used. The idea of the method is to generate a tableau for the expression whose summary violates the test constraints in a “canonical” way. The chase then tries to remove this violation. It is also shown how this method has applications to schema design. Relations not in normal form or having other deficiencies can be replaced by normal form projections without losing the ability to represent all constraint information.

We present polynomial time algorithms for minimizing and testing equivalence of what we call "fan-out free" queries. The fan-out free queries form a more general and more powerful subclass of the conjunctive queries than those previously studied, as they can be used to express questions about transitive properties of databases, questions that are impossible to express if one operates under the "disjoint domain assumption" implicit in previous work. Our algorithms are graph-theoretic in nature, and the equivalence algorithm can be viewed as solving a special case of the graph isomorphism problem (by reducing it to a series of labelled forest isomorphism questions).

This paper deals with the problem of determining which of a certain class of constraints hold on a given relational algebra expression where the base relations come from a given schema. The class of constraints includes functional dependencies, equality of domains, and constancy of domains. The relational algebra consists of projection, selection, restriction, cross product, union, and difference. The problem as given is undecidable, but if set difference is removed from the algebra, there is a solution. Operators specifying a closure function (similar to functional dependency closure on one relation) are defined; these will generate exactly the set of constraints valid on the given relational algebra expression. We prove that the operators are sound and complete.