Solving Implication Problems in Database Applications.

Xian-He Sun, Nabil Kamel, Lionel M. Ni: Solving Implication Problems in Database Applications. SIGMOD Conference 1989: 185-192

@inproceedings{DBLP:conf/sigmod/SunKN89,
  author    = {Xian-He Sun and
               Nabil Kamel and
               Lionel M. Ni},
  editor    = {James Clifford and
               Bruce G. Lindsay and
               David Maier},
  title     = {Solving Implication Problems in Database Applications},
  booktitle = {Proceedings of the 1989 ACM SIGMOD International Conference on
               Management of Data, Portland, Oregon, May 31 - June 2, 1989},
  publisher = {ACM Press},
  year      = {1989},
  pages     = {185-192},
  ee        = {http://doi.acm.org/10.1145/67544.66943, db/conf/sigmod/SunKN89.html},
  crossref  = {DBLP:conf/sigmod/89},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

Computing queries from derived relations, optimizing queries from a group of queries, and updating materialized views are important database problems and have attracted much attention. One thing common to these problems is their demand to quickly solve the implication problem - given two predicates sigma_Q and sigma_T, can sigma_Q imply sigma_T (sigma_Q->sigma_T)? The implication problem has been solved by converting it into a satisfiability problem. Based on a graph representation, a detailed study of the general implication problem on its own is presented in this paper. We proved that the general implication problem, in which all six comparison operators: =, #, <, >, <=, >=, as well as conjunctions and disjunctions are allowed, is NP-hard. In the case when "#" operators are not allowed in sigma_Q and disjunctions are not allowed in sigma_T, a polynomial time algorithm is proposed to solve this restricted implication problem. The influence of the "#" operator and disjunctions are studied. Our theoretical results show that for some special cases the polynomial complexity algorithm can solve the implication problem which allows the "#" operator or disjunctions in the predicates. Necessary conditions for detecting when the "#" operator and disjunctions are allowed are also given. These results are very useful in creating heuristic methods.

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.

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

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/smod7592 or /cdrom

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

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

BibTeX

Printed Edition

James Clifford, Bruce G. Lindsay, David Maier (Eds.): Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data, Portland, Oregon, May 31 - June 2, 1989. ACM Press 1989 BibTeX , SIGMOD Record 18(2), June 1989
Contents

Online Edition: ACM Digital Library

References

[1]: Sheldon J. Finkelstein: Common Subexpression Analysis in Database Applications. SIGMOD Conference 1982: 235-245 BibTeX
[2]: Per-Åke Larson, H. Z. Yang: Computing Queries from Derived Relations. VLDB 1985: 259-269 BibTeX
[3]: Daniel J. Rosenkrantz, Harry B. Hunt III: Processing Conjunctive Predicates and Queries. VLDB 1980: 64-72 BibTeX
[4]: ...
[5]: Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984) BibTeX
[6]: ...
[7]: ...
[8]: ...
[9]: ...
[10]: ...
[11]: Timos K. Sellis: Global Query Optimization. SIGMOD Conference 1986: 191-205 BibTeX
[12]: Rudolf Munz, H.-J. Schneider, Frank Steyer: Application of Sub-Predicate Tests in Database Systems. VLDB 1979: 426-435 BibTeX
[13]: José A. Blakeley, Neil Coburn, Per-Åke Larson: Updating Derived Relations: Detecting Irrelevant and Autonomously Computable Updates. VLDB 1986: 457-466 BibTeX
[14]: José A. Blakeley, Per-Åke Larson, Frank Wm. Tompa: Efficiently Updating Materialized Views. SIGMOD Conference 1986: 61-71 BibTeX
[15]: Christos H. Papadimitriou, Kenneth Steiglitz: Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall 1982, ISBN 0-13-152462-3
BibTeX
[16]: David Maier, Jeffrey D. Ullman: Fragments of Relations. SIGMOD Conference 1983: 15-22 BibTeX
[17]: Jean-Pierre Cheiney, Pascal Faudemay, Rodolphe Michel: An Extension of Access Paths to Improve Joins and Selections. ICDE 1986: 270-280 BibTeX
[18]: Stefano Ceri, Mauro Negri, Giuseppe Pelagatti: Horizontal Data Partitioning in Database Design. SIGMOD Conference 1982: 128-136 BibTeX
[19]: Timos K. Sellis: Multiple-Query Optimization. ACM Trans. Database Syst. 13(1): 23-52(1988) BibTeX

Referenced by

Peter Scheuermann, Junho Shim, Radek Vingralek: WATCHMAN : A Data Warehouse Intelligent Cache Manager. VLDB 1996: 51-62
Nick Roussopoulos, Chung-Min Chen, Stephen Kelley, Alex Delis, Yannis Papakonstantinou: The ADMS Project: View R Us. IEEE Data Eng. Bull. 18(2): 19-28(1995)
Wei Sun, Mark Allen Weiss: An Improved Algorithm for Implication Testing Involving Arithmetic Inequalities. IEEE Trans. Knowl. Data Eng. 6(6): 997-1001(1994)
Arantza Illarramendi, José Miguel Blanco, Alfredo Goñi: Making the Knowledge Base System More Efficient: A Method to Detect Inconsistent Queries. IEEE Trans. Knowl. Data Eng. 6(4): 634-639(1994)
Nabil Kamel, Roger King: Intelligent Database Caching Through the Use of Page-Answers and Page-Traces. ACM Trans. Database Syst. 17(4): 601-646(1992)
T. Y. Cliff Leung, Richard R. Muntz: Temporal Query Processing and Optimization in Multiprocessor Database Machines. VLDB 1992: 383-394
Amit P. Sheth, Anthony B. O'Hare: The Architecture of BrAID: A System for Bridging AI/DB Systems. ICDE 1991: 570-581
Michael V. Mannino, Injun Choi: Object-Oriented Modelling and Reasoning. ER 1990: 455-464
Sreekumar T. Shenoy, Z. Meral Özsoyoglu: Design and Implementation of a Semantic Query Optimizer. IEEE Trans. Knowl. Data Eng. 1(3): 344-361(1989)

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]