On conjunctive queries containing inequalities
- 1 January 1988
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 35 (1), 146-160
- https://doi.org/10.1145/42267.42273
Abstract
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.Keywords
This publication has 8 references indexed in Scilit:
- Testing containment of conjunctive queries under functional and inclusion dependenciesJournal of Computer and System Sciences, 1984
- Optimizing Conjunctive Queries that Contain Untyped VariablesSIAM Journal on Computing, 1983
- Algebraic dependenciesJournal of Computer and System Sciences, 1982
- Equivalences Among Relational Expressions with the Union and Difference OperatorsJournal of the ACM, 1980
- Efficient optimization of a class of relational expressionsACM Transactions on Database Systems, 1979
- Some properties of relational expressionsPublished by Association for Computing Machinery (ACM) ,1979
- The design and implementation of INGRESACM Transactions on Database Systems, 1976
- System RACM Transactions on Database Systems, 1976