ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

The Complexity of Testing Predicate Locks.

Harry B. Hunt III, Daniel J. Rosenkrantz: The Complexity of Testing Predicate Locks. SIGMOD Conference 1979: 127-133
@inproceedings{DBLP:conf/sigmod/HuntR79,
  author    = {Harry B. Hunt III and
               Daniel J. Rosenkrantz},
  editor    = {Philip A. Bernstein},
  title     = {The Complexity of Testing Predicate Locks},
  booktitle = {Proceedings of the 1979 ACM SIGMOD International Conference on
               Management of Data, Boston, Massachusetts, May 30 - June 1},
  publisher = {ACM},
  year      = {1979},
  isbn      = {0-89791-001-X},
  pages     = {127-133},
  ee        = {http://doi.acm.org/10.1145/582095.582115, db/conf/sigmod/HuntR79.html},
  crossref  = {DBLP:conf/sigmod/79},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

The problem of testing predicates for satisfiability arises in several aspects of database systems such as the use of predicate locks in concurrency control [7]. Such problems are NP-complete even for "simple predicates", i.e. predicates consisting of Boolean combinations of comparisons between a field of a tupleand a constant. However, when the relations referred to by the predicates are of fixed degree, there is an algorithm whose runtime is bounded by a polynanialin the length of the predicate. This is true not only for "simple predicates" but also for predicates containing comparisons between a field and another field, possibly offset by a constant. The proofs involve showing that if a predicate is satisfiable, then it is satisfiable by a tuple whose field values are related to constants occurring in the predicate.

Copyright © 1979 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.


ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

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

Printed Edition

Philip A. Bernstein (Ed.): Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data, Boston, Massachusetts, May 30 - June 1. ACM 1979, ISBN 0-89791-001-X BibTeX
Contents

Online Edition: ACM Digital Library


References

[1]
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) BibTeX
[2]
Jon Louis Bentley: Multidimensional Binary Search Trees Used for Associative Searching. Commun. ACM 18(9): 509-517(1975) BibTeX
[3]
Stephen A. Cook: The Complexity of Theorem-Proving Procedures. STOC 1971: 151-158 BibTeX
[4]
...
[5]
...
[6]
Kapali P. Eswaran, Donald D. Chamberlin: Functional Specifications of Subsystem for Database Integrity. VLDB 1975: 48-68 BibTeX
[7]
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) BibTeX
[8]
Raphael A. Finkel, Jon Louis Bentley: Quad Trees: A Data Structure for Retrieval on Composite Keys. Acta Inf. 4: 1-9(1974) BibTeX
[9]
...
[10]
Donald E. Knuth: The Art of Computer Programming, Volume I: Fundamental Algorithms, 2nd Edition. Addison-Wesley 1973
BibTeX
[11]
Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX
[12]
Ronald L. Rivest: Partial-Match Retrieval Algorithms. SIAM J. Comput. 5(1): 19-50(1976) BibTeX
[13]
...
[14]
Michael Stonebraker, Erich J. Neuhold: A Distributed Database Version of INGRES. Berkeley Workshop 1977: 19-36 BibTeX
[15]
Kai C. Wong, Murray Edelberg: Interval Hierarchies and Their Application to Predicate Files. ACM Trans. Database Syst. 2(3): 223-232(1977) BibTeX

Referenced by

  1. Divyakant Agrawal, Amr El Abbadi, Ambuj K. Singh: Consistency and Orderability: Semantics-Based Correctness Criteria for Databases. ACM Trans. Database Syst. 18(3): 460-486(1993)
  2. Michael V. Mannino, Injun Choi: Object-Oriented Modelling and Reasoning. ER 1990: 455-464
  3. Sreekumar T. Shenoy, Z. Meral Özsoyoglu: Design and Implementation of a Semantic Query Optimizer. IEEE Trans. Knowl. Data Eng. 1(3): 344-361(1989)
  4. Heikki Mannila, Kari-Jouko Räihä: Practical Algorithms for Finding Prime Attributes and Testing Normal Forms. PODS 1989: 128-133
  5. Charles Elkan: A Decision Procedure for Conjunctive Query Disjointness. PODS 1989: 134-139
  6. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
  7. Wojtek Kozaczynski, Leszek Lilien: An Extended Entity-Relationship (E²R) Database Specification and its Automatic Verification and Transformation into the Logical Relational Design. ER 1987: 533-549
  8. Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
    Contents
  9. Stefan Böttcher, Matthias Jarke, Joachim W. Schmidt: Adaptive Predicate Managers in Database Systems. VLDB 1986: 21-29
  10. Manuel Reimer: Solving the Phantom Problem by Predicative Optimistic Concurrency Control. VLDB 1983: 81-88
  11. Daniel J. Rosenkrantz, Harry B. Hunt III: Processing Conjunctive Predicates and Queries. VLDB 1980: 64-72
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:39:21 2009