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

A Decision Procedure for Conjunctive Query Disjointness.

Charles Elkan: A Decision Procedure for Conjunctive Query Disjointness. PODS 1989: 134-139
@inproceedings{DBLP:conf/pods/Elkan89,
  author    = {Charles Elkan},
  title     = {A Decision Procedure for Conjunctive Query Disjointness},
  booktitle = {Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, March 29-31, 1989, Philadelphia,
               Pennsylvania},
  publisher = {ACM Press},
  year      = {1989},
  isbn      = {0-89791-308-6},
  pages     = {134-139},
  ee        = {http://doi.acm.org/10.1145/73721.73735, db/conf/pods/Elkan89.html},
  crossref  = {DBLP:conf/pods/89},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

This paper presents an algorithm that decides whether two conjunctive query expressions always describe disjoint sets of tuples. The decision procedure solves an open problem identified by Blakeley, Coburn, and Larson: how to check whether an explicitly stored view relation must be recomputed after an update, taking into account functional dependencies. For nonconjunctive queries, the disjointness problem is NP-hard. For conjunctive queries, the time complexity of the algorithm given cannot be improved unless the reachability problem for directed graphs can be solved in sublinear time. The algorithm is novel in that it combines separate decision procedures for the theory of functional dependencies and for the theory of dense orders. Also, it uses tableaux that are capable of representing all six comparison operators <, <=, =,>=, >, and #.

Copyright © 1989 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.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, March 29-31, 1989, Philadelphia, Pennsylvania. ACM Press 1989, ISBN 0-89791-308-6
Contents BibTeX

Online Edition: ACM Digital Library

References

[1]
Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979) BibTeX
[2]
José A. Blakeley, Neil Coburn, Per-Åke Larson: Updating Derived Relations: Detecting Irrelevant and Autonomously Computable Updates. ACM Trans. Database Syst. 14(3): 369-400(1989) BibTeX
[3]
José A. Blakeley, Per-Åke Larson, Frank Wm. Tompa: Efficiently Updating Materialized Views. SIGMOD Conference 1986: 61-71 BibTeX
[4]
Peter J. Downey, Ravi Sethi, Robert Endre Tarjan: Variations on the Common Subexpression Problem. J. ACM 27(4): 758-771(1980) BibTeX
[5]
...
[6]
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
[7]
Harry B. Hunt III, Daniel J. Rosenkrantz: The Complexity of Testing Predicate Locks. SIGMOD Conference 1979: 127-133 BibTeX
[8]
Anthony C. Klug: Locking Expressions for Increased Database Concurrency. J. ACM 30(1): 36-54(1983) BibTeX
[9]
Per-Åke Larson, H. Z. Yang: Computing Queries from Derived Relations. VLDB 1985: 259-269 BibTeX
[10]
David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
Contents BibTeX
[11]
Greg Nelson, Derek C. Oppen: Simplification by Cooperating Decision Procedures. ACM Trans. Program. Lang. Syst. 1(2): 245-257(1979) BibTeX
[12]
Derek C. Oppen: Complexity, Convexity and Combinations of Theories. Theor. Comput. Sci. 12: 291-302(1980) BibTeX
[13]
...
[14]
Robert Endre Tarjan: Efficiency of a Good But Not Linear Set Union Algorithm. J. ACM 22(2): 215-225(1975) 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. Sha Guo, Wei Sun, Mark Allen Weiss: Addendum to "On Satisfiability, Equivalence, and Implication Problems Involving Conjunctive Queries in Database Systems". IEEE Trans. Knowl. Data Eng. 10(5): 863(1998)
  3. Michael J. Maher, Divesh Srivastava: Chasing Constrained Tuple-Generating Dependencies. PODS 1996: 128-138
  4. Charles Elkan: Independence of Logic Database Queries and Updates. PODS 1990: 154-160
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:33:56 2009