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.

ACM SIGMOD Anthology

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

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/vldb7588 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

Printed Edition

Sixth International Conference on Very Large Data Bases, October 1-3, 1980, Montreal, Quebec, Canada, Proceedings. IEEE Computer Society 1980
Contents

References

[1]: Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979)
[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)
[3]: Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90
[4]: ...
[5]: Stephen A. Cook: The Complexity of Theorem-Proving Procedures. STOC 1971: 151-158
[6]: ...
[7]: Kapali P. Eswaran: Aspects of a Trigger Subsystem in an Integrated Data Base System. ICSE 1976: 243-250
[8]: Kapali P. Eswaran, Donald D. Chamberlin: Functional Specifications of Subsystem for Database Integrity. VLDB 1975: 48-68
[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)
[10]: J. J. Florentin: Consistency Auditing of Databases. Comput. J. 17(1): 52-58(1974)
[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)
[13]: Patricia P. Griffiths, Bradford W. Wade: An Authorization Mechanism for a Relational Database System. ACM Trans. Database Syst. 1(3): 242-255(1976)
[14]: Harry B. Hunt III, Daniel J. Rosenkrantz: The Complexity of Testing Predicate Locks. SIGMOD Conference 1979: 127-133
[15]: ...
[16]: Rudolf Munz, H.-J. Schneider, Frank Steyer: Application of Sub-Predicate Tests in Database Systems. VLDB 1979: 426-435
[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)
[19]: Gunter Schlageter: The Problem of Lock by Value in Large Data Bases. Comput. J. 19(1): 17-20(1976)
[20]: Michael Stonebraker, Erich J. Neuhold: A Distributed Database Version of INGRES. Berkeley Workshop 1977: 19-36
[21]: Kai C. Wong, Murray Edelberg: Interval Hierarchies and Their Application to Predicate Files. ACM Trans. Database Syst. 2(3): 223-232(1977)