ACM SIGMOD Anthology TODS dblp.uni-trier.de

Solving Satisfiability and Implication Problems in Database Systems.

Sha Guo, Wei Sun, Mark Allen Weiss: Solving Satisfiability and Implication Problems in Database Systems. ACM Trans. Database Syst. 21(2): 270-293(1996)
@article{DBLP:journals/tods/GuoSW96,
  author    = {Sha Guo and
               Wei Sun and
               Mark Allen Weiss},
  title     = {Solving Satisfiability and Implication Problems in Database Systems},
  journal   = {ACM Trans. Database Syst.},
  volume    = {21},
  number    = {2},
  year      = {1996},
  pages     = {270-293},
  ee        = {http://doi.acm.org/10.1145/232616.232692, db/journals/tods/GuoSW96.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Satisfiability, implication, and equivalence problems involving conjunctive inequalities are important and widely encountered database problems that need to be efficiently and effectively processed. In this article we consider two popular types of arithmetic inequalities, (X op Y) and (X op C), where X and Y are attributes, C is a constant of the domain or X, and op in{<, <=, =, !=, >, >=). These inequalities are most frequently used in a database system, inasmuch as the former type of inequality represents a 0-join, and the latter is a selection. We study the satisfiability and implication problems under the integer domain and the real domain, as well as under two different operator sets ({<, <=, =, >=, >} and {<, <=, =, !=, >=, >}). Our results show that solutions under different domains and/or different operator sets are quite different. Out of these eight cases, excluding two cases that had been shown to be NP-hard, we either report the first necessary and sufficient conditions for these problems as well as their efficient algorithms with complexity analysis (for four cases), or provide an improved algorithm (for two cases). These iff conditions and algorithms are essential to database designers, practitioners, and researchers. These algorithms have been implemented and an experimental study comparing the proposed algorithms and those previously known is conducted. Our experiments show that the proposed algorithms are more efficient than previously known algorithms even for small input.

Copyright © 1996 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

CDROM Version: Load the CDROM "Volume 4 Issue 1, Books, VLDB-j, TODS, ..." and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

Online Edition: ACM Digital Library

[Abstract, Index Terms and Review]
[Full Text in PDF Format, 387 KB]

References

[Aho et al. 1983]
Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: Data Structures and Algorithms. Addison-Wesley 1983, ISBN 0-201-00023-7
BibTeX
[Aho et al. 1979a]
Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979) BibTeX
[Aho et al. 1979b]
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
[Astrahan et al. 1976]
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
[Blakeley et al 1986a]
José A. Blakeley, Neil Coburn, Per-Åke Larson: Updating Derived Relations: Detecting Irrelevant and Autonomously Computable Updates. VLDB 1986: 457-466 BibTeX
[Blakeley et al 1986b]
José A. Blakeley, Per-Åke Larson, Frank Wm. Tompa: Efficiently Updating Materialized Views. SIGMOD Conference 1986: 61-71 BibTeX
[Ceri and Pelagatti 1984]
Stefano Ceri, Giuseppe Pelagatti: Distributed Databases: Principles and Systems. McGraw-Hill Book Company 1984, ISBN 0-07-010829-3
BibTeX
[Chakravarthy et al. 1990]
Upen S. Chakravarthy, John Grant, Jack Minker: Logic-Based Approach to Semantic Query Optimization. ACM Trans. Database Syst. 15(2): 162-207(1990) BibTeX
[Coppersmith and Winograd 1987]
Don Coppersmith, Shmuel Winograd: Matrix Multiplication via Arithmetic Progressions. STOC 1987: 1-6 BibTeX
[Cormen et al. 1990]
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest: Introduction to Algorithms. The MIT Press and McGraw-Hill Book Company 1989, ISBN 0-262-03141-8,0-07-013143-0
BibTeX
[Floyd 1962]
...
[Gallaire et al. 1984]
Hervé Gallaire, Jack Minker, Jean-Marie Nicolas: Logic and Databases: A Deductive Approach. ACM Comput. Surv. 16(2): 153-185(1984) BibTeX
[Garey et al. 1976]
M. R. Garey, David S. Johnson, Larry J. Stockmeyer: Some Simplified NP-Complete Graph Problems. Theor. Comput. Sci. 1(3): 237-267(1976) BibTeX
[Guo et al. 1996]
Sha Guo, Wei Sun, Mark Allen Weiss: On Satisfiability, Equivalence, and Impication Problems Involving Conjunctive Queries in Database Systems. IEEE Trans. Knowl. Data Eng. 8(4): 604-616(1996) BibTeX
[Jarke and Koch 1984]
Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984) BibTeX
[Johnson and Klug 1984]
David S. Johnson, Anthony C. Klug: Testing Containment of Conjunctive Queries under Functional and Inclusion Dependencies. J. Comput. Syst. Sci. 28(1): 167-189(1984) BibTeX
[Johnson and Klug 1983]
David S. Johnson, Anthony C. Klug: Optimizing Conjunctive Queries that Contain Untyped Variables. SIAM J. Comput. 12(4): 616-640(1983) BibTeX
[Kim 1984]
...
[King 1986]
Jonathan J. King: QUIST: A System for Semantic Query Optimization in Relational Databases. VLDB 1981: 510-517 BibTeX
[Klug 1988]
Anthony C. Klug: On conjunctive queries containing inequalities. J. ACM 35(1): 146-160(1988) BibTeX
[Krishnamurthy et al. 1986]
Ravi Krishnamurthy, Haran Boral, Carlo Zaniolo: Optimization of Nonrecursive Queries. VLDB 1986: 128-137 BibTeX
[Lobo et al. 1992]
...
[Meghini and Thanos 1991]
Carlo Meghini, Costantino Thanos: The Complexity of Operations on a Fragmented Relation. ACM Trans. Database Syst. 16(1): 56-87(1991) BibTeX
[Rosenkrantz and Hunt III 1980]
Daniel J. Rosenkrantz, Harry B. Hunt III: Processing Conjunctive Predicates and Queries. VLDB 1980: 64-72 BibTeX
[Sellis 1986]
Timos K. Sellis: Global Query Optimization. SIGMOD Conference 1986: 191-205 BibTeX
[Shasha and Wang 1991]
Dennis Shasha, Jason Tsong-Li Wang: Optimizing Equijoin Queries In Distributed Databases Where Relations Are Hash Partitioned. ACM Trans. Database Syst. 16(2): 279-308(1991) BibTeX
[Stonebraker and Neuhold 1977]
Michael Stonebraker, Erich J. Neuhold: A Distributed Database Version of INGRES. Berkeley Workshop 1977: 19-36 BibTeX
[Sun et al. 1989]
Xian-He Sun, Nabil Kamel, Lionel M. Ni: Processing Implication on Queries. IEEE Trans. Software Eng. 15(10): 1168-1175(1989) BibTeX
[Sun and Weiss 1994]
Wei Sun, Mark Allen Weiss: An Improved Algorithm for Implication Testing Involving Arithmetic Inequalities. IEEE Trans. Knowl. Data Eng. 6(6): 997-1001(1994) BibTeX
[Sun and Yu 1994]
Wei Sun, Clement T. Yu: Semantic Query Optimization for Tree and Chain Queries. IEEE Trans. Knowl. Data Eng. 6(1): 136-151(1994) BibTeX
[Tarjan 1983]
...
[Tarjan 1972]
Robert Endre Tarjan: Depth-First Search and Linear Graph Algorithms. SIAM J. Comput. 1(2): 146-160(1972) BibTeX
[Ullman 1989-1]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX
[Ullman 1989-2]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX
[Weiss 1995]
...
[Wong and Youssefi 1976]
Eugene Wong, Karel Youssefi: Decomposition - A Strategy for Query Processing. ACM Trans. Database Syst. 1(3): 223-241(1976) BibTeX
[Yu and Chang 1984]
Clement T. Yu, C. C. Chang: Distributed Query Processing. ACM Comput. Surv. 16(4): 399-433(1984) BibTeX
[Yu and Sun 1989]
Clement T. Yu, Wei Sun: Automatic Knowledge Acquisition and Maintenance for Semantic Query Optimization. IEEE Trans. Knowl. Data Eng. 1(3): 362-375(1989) BibTeX

Referenced by

  1. Xun Cheng, Guozhu Dong, Tzekwan Lau, Jianwen Su: Data Integration by Describing Sources with Constraint Databases. ICDE 1999: 374-381
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:39:19 2008