ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Adaptive Predicate Managers in Database Systems.

Stefan Böttcher, Matthias Jarke, Joachim W. Schmidt: Adaptive Predicate Managers in Database Systems. VLDB 1986: 21-29
@inproceedings{DBLP:conf/vldb/BottcherJS86,
  author    = {Stefan B{\"o}ttcher and
               Matthias Jarke and
               Joachim W. Schmidt},
  editor    = {Wesley W. Chu and
               Georges Gardarin and
               Setsuo Ohsuga and
               Yahiko Kambayashi},
  title     = {Adaptive Predicate Managers in Database Systems},
  booktitle = {VLDB'86 Twelfth International Conference on Very Large Data Bases,
               August 25-28, 1986, Kyoto, Japan, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1986},
  isbn      = {0-934613-18-4},
  pages     = {21-29},
  ee        = {db/conf/vldb/BottcherJS86.html},
  crossref  = {DBLP:conf/vldb/86},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Relational databases use predicates for a large variety of different functions, some leading to database search, others being handled by theorem proving. First we demonstrate that the theorem proving applications have very similar basic requirements for predicate management but differ in their need for efficiency. Second we present dedicated deduction methods for DBMS that employ a copcept of "doubtfuls" in order to allow tradeoffs between deductive completeness and efficiency. A new algorithm for testing the satisfiability of predicates with universally quantified variables is described and shown to offer advantages over general-purpose theorem provers for many database applications.

Copyright © 1986 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.


Online Paper

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 ... BibTeX

Printed Edition

Wesley W. Chu, Georges Gardarin, Setsuo Ohsuga, Yahiko Kambayashi (Eds.): VLDB'86 Twelfth International Conference on Very Large Data Bases, August 25-28, 1986, Kyoto, Japan, Proceedings. Morgan Kaufmann 1986, ISBN 0-934613-18-4
Contents BibTeX

References

[Ackermann54]
...
[Aho79]
Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Efficient Optimization of a Class of Relational Expressions. ACM Trans. Database Syst. 4(4): 435-454(1979) BibTeX
[Andrews81]
Peter B. Andrews: Theorem Proving via General Mappings. J. ACM 28(2): 193-214(1981) BibTeX
[Bibel81]
Wolfgang Bibel: On Matrices with Connections. J. ACM 28(4): 633-645(1981) BibTeX
[Bläsius81]
...
[Bledsoe80]
W. W. Bledsoe, Larry M. Hines: Variable Elimination and Chaining in a Resolution-based Prover for Inequalities. CADE 1980: 70-87 BibTeX
[Böttcher85]
...
[Böttcher86]
...
[Bowen82]
...
[Brachman86]
Ronald J. Brachman, Hector J. Levesque: What Makes a Knowledge Base Knowledgeable? A View of Databases from the Knowledge Level. Expert Database Workshop 1984: 69-78 BibTeX
[Carey85]
...
[Ceri84]
Stefano Ceri, Giuseppe Pelagatti: Distributed Databases: Principles and Systems. McGraw-Hill Book Company 1984, ISBN 0-07-010829-3
BibTeX
[Chakravarthy86]
...
[Chandra82]
Ashok K. Chandra, David Harel: Structure and Complexity of Relational Queries. J. Comput. Syst. Sci. 25(1): 99-128(1982) BibTeX
[Chang73]
...
[Codd70]
E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX
[Codd72]
E. F. Codd: Relational Completeness of Data Base Sublanguages. In: R. Rustin (ed.): Database Systems: 65-98, Prentice Hall and IBM Research Report RJ 987, San Jose, California : (1972) BibTeX
[Eckhardt85]
...
[Edelmann84]
...
[Eswaran76]
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
[Finkelstein82]
Sheldon J. Finkelstein: Common Subexpression Analysis in Database Applications. SIGMOD Conference 1982: 235-245 BibTeX
[Garey79]
M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7
BibTeX
[Hsiang83]
Jieh Hsiang, Nachum Dershowitz: Rewrite Methods for Clausal and Non-Clausal Theorem Proving. ICALP 1983: 331-346 BibTeX
[Hunt79]
Harry B. Hunt III, Daniel J. Rosenkrantz: The Complexity of Testing Predicate Locks. SIGMOD Conference 1979: 127-133 BibTeX
[Jarke83]
Matthias Jarke, Jürgen Koch: Range Nesting: A Fast Method to Evaluate Quantified Queries. SIGMOD Conference 1983: 196-206 BibTeX
[Jarke85]
Matthias Jarke: Common Subexpression Isolation in Multiple Query Optimization. Query Processing in Database Systems 1985: 191-205 BibTeX
[Jarke86]
Matthias Jarke: External Semantic Query Simplification: A Graph-Theoretic Approach and its Implementation in Prolog. Expert Database Workshop 1984: 675-692 BibTeX
[Kerschberg86]
...
[Kitakami84]
Hajime Kitakami, Susumu Kunifuji, Taizo Miyachi, Koichi Furukawa: A Methodology for Implementation of a Knowledge Acquisition System. SLP 1984: 131-142 BibTeX
[Kleene71]
...
[Klug83]
Anthony C. Klug: Locking Expressions for Increased Database Concurrency. J. ACM 30(1): 36-54(1983) BibTeX
[Kowalski75]
Robert A. Kowalski: A Proof Procedure Using Connection Graphs. J. ACM 22(4): 572-595(1975) BibTeX
[Mall84]
...
[Munz79]
Rudolf Munz, H.-J. Schneider, Frank Steyer: Application of Sub-Predicate Tests in Database Systems. VLDB 1979: 426-435 BibTeX
[Rosenkrantz80]
Daniel J. Rosenkrantz, Harry B. Hunt III: Processing Conjunctive Predicates and Queries. VLDB 1980: 64-72 BibTeX
[Schmidt77]
Joachim W. Schmidt: Some High Level Language Constructs for Data of Type Relation. ACM Trans. Database Syst. 2(3): 247-261(1977) BibTeX
[Shepherd86]
Allan Shepherd, Larry Kerschberg: Constraint Management in Expert Database Systems. Expert Database Workshop 1984: 309-331 BibTeX
[Stonebraker75]
Michael Stonebraker: Implementation of Integrity Constraints and Views by Query Modification. SIGMOD Conference 1975: 65-78 BibTeX
[Ullman82]
Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX

Referenced by

  1. Naci Ishakbeyoglu, Z. Meral Özsoyoglu: Maintenance of Implication Integrity Constraints Under Updates to Constraints. VLDB J. 7(2): 67-78(1998)
  2. Andreas Gawecki, Florian Matthes: Exploiting Persistent Intermediate Code Representations in Open Database Environments. EDBT 1996: 403-423
  3. 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)
  4. Yang Hee Kim, Hyoung-Joo Kim: Applying Intensional Query Processing Techniques to Object-Oriented Database Systems. DASFAA 1993: 405-412
  5. Joachim W. Schmidt, Florian Matthes: The Rational behind DBPL. MFDBS 1991: 389-395
  6. Stefan Böttcher: Improving the Concurrency of Integrity Checks and Write Operations. ICDT 1990: 259-273
  7. Stefan Böttcher: Attribute Inheritance Implemented on Top of a Relational Database System. ICDE 1990: 503-509
  8. Catriel Beeri, Hans-Jörg Schek, Gerhard Weikum: Multi-Level Transaction Management, Theoretical Art or Practical Need ? EDBT 1988: 134-154
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
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:45:27 2009