ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Processing Conjunctive Predicates and Queries.

Daniel J. Rosenkrantz, Harry B. Hunt III: Processing Conjunctive Predicates and Queries. VLDB 1980: 64-72
@inproceedings{DBLP:conf/vldb/RosenkrantzH80,
  author    = {Daniel J. Rosenkrantz and
               Harry B. Hunt III},
  title     = {Processing Conjunctive Predicates and Queries},
  booktitle = {Sixth International Conference on Very Large Data Bases, October
               1-3, 1980, Montreal, Quebec, Canada, Proceedings},
  publisher = {IEEE Computer Society},
  year      = {1980},
  pages     = {64-72},
  ee        = {db/conf/vldb/RosenkrantzH80.html},
  crossref  = {DBLP:conf/vldb/80},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Several aspects of relational database systems require the processing of predicates. For example, predicates can be tested for satisfiability (as in processing predicate locks), and predicates occurring in queries may be preprocessed in order to reduce the number of database operations when the query is answered. Here we study predicates consisting of conjunctions of comparisons. First, we consider predicates that are conjunctions of =, <, <= , >, and >= comparisons, where a variable can be compared with a constant or with another variable, possibly offset by a constant. Efficient algorithms are given for satisfiability, equivalence, and minimizing the number of comparisons in a predicate. Second, we show that when unequal comparisons between variables are allowed, satisfiability, equivalence, and minimization are NP-hard. Most approximation problems corresponding to minimization are also NP-hard. The preceding efficient algorithms show that the unequal comparison operation is the sole cause of this complexity.

Copyright © 1980 by The Institute of Electrical and Electronic Engineers, Inc. (IEEE). Abstract used with permission.


ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Sixth International Conference on Very Large Data Bases, October 1-3, 1980, Montreal, Quebec, Canada, Proceedings. IEEE Computer Society 1980
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[1]
Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[2]
Morton M. Astrahan, Mike W. Blasgen, Donald D. Chamberlin, Kapali P. Eswaran, Jim Gray, Patricia P. Griffiths, W. Frank King III, Raymond A. Lorie, Paul R. McJones, James W. Mehl, Gianfranco R. Putzolu, Irving L. Traiger, Bradford W. Wade, Vera Watson: System R: Relational Approach to Database Management. ACM Trans. Database Syst. 1(2): 97-137(1976) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[3]
Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[4]
...
[5]
Stephen A. Cook: The Complexity of Theorem-Proving Procedures. STOC 1971: 151-158 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[6]
...
[7]
Kapali P. Eswaran: Aspects of a Trigger Subsystem in an Integrated Data Base System. ICSE 1976: 243-250 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[8]
Kapali P. Eswaran, Donald D. Chamberlin: Functional Specifications of Subsystem for Database Integrity. VLDB 1975: 48-68 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[9]
Kapali P. Eswaran, Jim Gray, Raymond A. Lorie, Irving L. Traiger: The Notions of Consistency and Predicate Locks in a Database System. Commun. ACM 19(11): 624-633(1976) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[10]
J. J. Florentin: Consistency Auditing of Databases. Comput. J. 17(1): 52-58(1974) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[11]
...
[12]
M. R. Garey, David S. Johnson, Larry J. Stockmeyer: Some Simplified NP-Complete Graph Problems. Theor. Comput. Sci. 1(3): 237-267(1976) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[13]
Patricia P. Griffiths, Bradford W. Wade: An Authorization Mechanism for a Relational Database System. ACM Trans. Database Syst. 1(3): 242-255(1976) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[14]
Harry B. Hunt III, Daniel J. Rosenkrantz: The Complexity of Testing Predicate Locks. SIGMOD Conference 1979: 127-133 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[15]
...
[16]
Rudolf Munz, H.-J. Schneider, Frank Steyer: Application of Sub-Predicate Tests in Database Systems. VLDB 1979: 426-435 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[17]
...
[18]
Daniel R. Ries, Michael Stonebraker: Effects of Locking Granularity in a Database Management System. ACM Trans. Database Syst. 2(3): 233-246(1977) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[19]
Gunter Schlageter: The Problem of Lock by Value in Large Data Bases. Comput. J. 19(1): 17-20(1976) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[20]
Michael Stonebraker, Erich J. Neuhold: A Distributed Database Version of INGRES. Berkeley Workshop 1977: 19-36 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[21]
Kai C. Wong, Murray Edelberg: Interval Hierarchies and Their Application to Predicate Files. ACM Trans. Database Syst. 2(3): 223-232(1977) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Tue Mar 16 02:21:56 2010 by Michael Ley (ley@uni-trier.de)