Solving satisfiability and implication problems in database systems

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, (XopY) and (X op C), where X and Y are attributes, C is a constant of the domain or X, and op ∈{<, ≤, =, ≠, >, ≥). 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. The C++ code can be obtained by an anonymous ftp from <archive.fiu.edu>.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft , Jeffrey Ullman , J. D. Ullman , J. E. Hopcroft, Data Structures and Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 2: AHO, A. V., SAGIV, Y., AND ULLMAN, J.n. 1979a. Equivalences among relational expressions. SIAM J. Comput. 8, 2 (May), 218-246.
• 3: A. V. Aho , Y. Sagiv , J. D. Ullman, Efficient optimization of a class of relational expressions, ACM Transactions on Database Systems (TODS), v.4 n.4, p.435-454, Dec. 1979 [doi>10.1145/320107.320112]
• 4: M. M. Astrahan , M. W. Blasgen , D. D. Chamberlin , K. P. Eswaran , J. N. Gray , P. P. Griffiths , W. F. King , R. A. Lorie , P. R. McJones , J. W. Mehl , G. R. Putzolu , I. L. Traiger , B. W. Wade , V. Watson, System R: relational approach to database management, ACM Transactions on Database Systems (TODS), v.1 n.2, p.97-137, June 1976 [doi>10.1145/320455.320457]
• 5: José A. Blakeley , Neil Coburn , Per-Åke Larson, Updating Derived Relations: Detecting Irrelevant and Autonomously Computable Updates, Proceedings of the 12th International Conference on Very Large Data Bases, p.457-466, August 25-28, 1986
• 6: Jose A. Blakeley , Per-Ake Larson , Frank Wm Tompa, Efficiently updating materialized views, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.61-71, May 28-30, 1986, Washington, D.C., United States
• 7: Stefano Ceri , Giuseppe Pelagatti, Distributed databases principles and systems, McGraw-Hill, Inc., New York, NY, 1984
• 8: Upen S. Chakravarthy , John Grant , Jack Minker, Logic-based approach to semantic query optimization, ACM Transactions on Database Systems (TODS), v.15 n.2, p.162-207, June 1990 [doi>10.1145/78922.78924]
• 9: D. Coppersmith , S. Winograd, Matrix multiplication via arithmetic progressions, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.1-6, January 1987, New York, New York, United States [doi>10.1145/28395.28396]
• 10: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 11: Robert W. Floyd, Algorithm 97: Shortest path, Communications of the ACM, v.5 n.6, p.345, June 1962 [doi>10.1145/367766.368168]
• 12: Herve Gallaire , Jack Minker , Jean-Marie Nicolas, Logic and Databases: A Deductive Approach, ACM Computing Surveys (CSUR), v.16 n.2, p.153-185, June 1984 [doi>10.1145/356924.356929]
• 13: GAREY, M., JOHNSON, D., AND STOCKMEYER, L. 1976. Some simplified NP-complete problems. Theor. Comput. Sci. 1, 237-267.
• 14: Sha Guo , Wei Sun , Mark A. Weiss, On Satisfiability, Equivalence, and Implication Problems Involving Conjunctive Queries in Database Systems, IEEE Transactions on Knowledge and Data Engineering, v.8 n.4, p.604-616, August 1996 [doi>10.1109/69.536253]
• 15: Matthias Jarke , Jurgen Koch, Query Optimization in Database Systems, ACM Computing Surveys (CSUR), v.16 n.2, p.111-152, June 1984 [doi>10.1145/356924.356928]
• 16: JOHNSON, D. AND KLUG, A. 1984. Testing containment of conjunctive queries under functional and inclusion dependencies. J. Comput. Syst. Sci. 28, I (Feb.), 167-189.
• 17: JOHNSON, D. AND KLUG, A. 1983. Optimizing conjunctive queries that contain untyped variables. SIAM J. Comput. 12, 4 (Nov.), 616-640.
• 18: KIM, W. 1984. Global optimization of relational queries: A first step. In Query Processing in Database Systems, W. Kim, D. Reiner, and D. Batory, Eds., Springer, New York.
• 19: KING, J.J. 1986. Quist: A system for semantic query optimization in relational databases. In Proceedings of the Seventh International Conference on Very Large Databases (Kyoto, Japan), 510-517.
• 20: Anthony Klug, On conjunctive queries containing inequalities, Journal of the ACM (JACM), v.35 n.1, p.146-160, Jan. 1988 [doi>10.1145/42267.42273]
• 21: Ravi Krishnamurthy , Haran Boral , Carlo Zaniolo, Optimization of Nonrecursive Queries, Proceedings of the 12th International Conference on Very Large Data Bases, p.128-137, August 25-28, 1986
• 22: Jorge Lobo , Jack Minker , Arcot Rajasekar, Foundations of disjunctive logic programming, MIT Press, Cambridge, MA, 1992
• 23: C. Meghini , C. Thanos, The complexity of operations on a fragmented relation, ACM Transactions on Database Systems (TODS), v.16 n.1, p.56-87, March 1991 [doi>10.1145/103140.103143]
• 24: ROSENKaANTZ, D. J. AND HUNT, H. B. III 1980. Processing conjunctive predicates and queries. In Proceedings of the Sixth International Conference on Very Large Databases, 64 -72.
• 25: Timos K. Sellis, Global query optimization, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.191-205, May 28-30, 1986, Washington, D.C., United States
• 26: Dennis Shasha , Tsong-Li Wang, Optimizing equijoin queries in distributed databases where relations are hash partitioned, ACM Transactions on Database Systems (TODS), v.16 n.2, p.279-308, June 1991 [doi>10.1145/114325.103713]
• 27: STONEBRAKER, M. AND NEUHOLD, E. 1977. A distributed database version of INGRES. In Proceedings of the Second Berkeley Workshop on Distributed Data Management and Computer Networks, (May), 19-36.
• 28: Xian-He Sun , Nabil N. Kamel, Processing Implication on Queries, IEEE Transactions on Software Engineering, v.15 n.10, p.1168-1175, October 1989 [doi>10.1109/TSE.1989.559764]
• 29: W. Sun , M. A. Weiss, An Improved Algorithm for Implication Testing Involving Arithmetic Inequalities, IEEE Transactions on Knowledge and Data Engineering, v.6 n.6, p.997-1001, December 1994 [doi>10.1109/69.334889]
• 30: W. Sun , C. Yu, Semantic Query Optimization for Tree and Chain Queries, IEEE Transactions on Knowledge and Data Engineering, v.6 n.1, p.136-151, February 1994 [doi>10.1109/69.273033]
• 31: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
• 32: TARJAN, R. 1972. Depth-first search and linear graph algorithms. SIAM J. Comput. 1, 2 (June), 146-160.
• 33: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 34: Mark Allen Weiss, Data structures and algorithm analysis (2nd ed.), Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1995
• 35: Eugene Wong , Karel Youssefi, Decomposition—a strategy for query processing, ACM Transactions on Database Systems (TODS), v.1 n.3, p.223-241, Sept. 1976 [doi>10.1145/320473.320479]
• 36: C. T. Yu , C. C. Chang, Distributed query processing, ACM Computing Surveys (CSUR), v.16 n.4, p.399-433, Dec. 1984 [doi>10.1145/3872.3874]
• 37: C. T. Yu , W. Sun, Automatic Knowledge Acquisition and Maintenance for Semantic Query Optimization, IEEE Transactions on Knowledge and Data Engineering, v.1 n.3, p.362-375, September 1989 [doi>10.1109/69.87981]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Complexity of proof procedures

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Deduction (e.g., natural, rule-based)

General Terms:
Algorithms, Languages, Theory

Keywords:
deduction, equivalence, implication, reasoning, satisfiabilty