On Satisfiability, Equivalence, and Impication Problems Involving Conjunctive Queries in Database Systems.

@article{DBLP:journals/tkde/GuoSW96,
  author    = {Sha Guo and
               Wei Sun and
               Mark Allen Weiss},
  title     = {On Satisfiability, Equivalence, and Impication Problems Involving
               Conjunctive Queries in Database Systems},
  journal   = {IEEE Trans. Knowl. Data Eng.},
  volume    = {8},
  number    = {4},
  year      = {1996},
  pages     = {604-616},
  ee        = {db/journals/tkde/GuoSW96.html, db/journals/tkde/GuoSW96.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 1996 by The Institute of Electrical and Electronic Engineers, Inc. (IEEE). Abstract used with permission.

CDROM Edition

References

[1]

Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: Data Structures and Algorithms. Addison-Wesley 1983, ISBN 0-201-00023-7
BibTeX

[2]

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

[3]

José A. Blakeley, Neil Coburn, Per-Åke Larson: Updating Derived Relations: Detecting Irrelevant and Autonomously Computable Updates. VLDB 1986: 457-466 BibTeX

[4]

José A. Blakeley, Per-Åke Larson, Frank Wm. Tompa: Efficiently Updating Materialized Views. SIGMOD Conference 1986: 61-71 BibTeX

[5]

Upen S. Chakravarthy, John Grant, Jack Minker: Logic-Based Approach to Semantic Query Optimization. ACM Trans. Database Syst. 15(2): 162-207(1990) BibTeX

[6]

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

[7]

...

[8]

...

[9]

Joxan Jaffar, Jean-Louis Lassez: Constraint Logic Programming. POPL 1987: 111-119 BibTeX

[10]

Joxan Jaffar, Spiro Michaylov, Peter J. Stuckey, Roland H. C. Yap: The CLP(R) Language and System. ACM Trans. Program. Lang. Syst. 14(3): 339-395(1992) BibTeX

[11]

Matthias Jarke: Common Subexpression Isolation in Multiple Query Optimization. Query Processing in Database Systems 1985: 191-205 BibTeX

[12]

David S. Johnson, Anthony C. Klug: Optimizing Conjunctive Queries that Contain Untyped Variables. SIAM J. Comput. 12(4): 616-640(1983) BibTeX

[13]

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

[14]

Paris C. Kanellakis, Gabriel M. Kuper, Peter Z. Revesz: Constraint Query Languages. PODS 1990: 299-313 BibTeX

[15]

Won Kim: Global Optimization of Relational Queries: A First Step. Query Processing in Database Systems 1985: 206-216 BibTeX

[16]

...

[17]

Anthony C. Klug: On conjunctive queries containing inequalities. J. ACM 35(1): 146-160(1988) BibTeX

[18]

David Maier, Jeffrey D. Ullman: Fragments of Relations. SIGMOD Conference 1983: 15-22 BibTeX

[19]

...

[20]

Daniel J. Rosenkrantz, Harry B. Hunt III: Processing Conjunctive Predicates and Queries. VLDB 1980: 64-72 BibTeX

[21]

Timos K. Sellis: Global Query Optimization. SIGMOD Conference 1986: 191-205 BibTeX

[22]

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

[23]

Wei Sun, Clement T. Yu: Semantic Query Optimization for Tree and Chain Queries. IEEE Trans. Knowl. Data Eng. 6(1): 136-151(1994) BibTeX

[24]

Xian-He Sun, Nabil Kamel, Lionel M. Ni: Processing Implication on Queries. IEEE Trans. Software Eng. 15(10): 1168-1175(1989) BibTeX

[25]

Robert Endre Tarjan: Depth-First Search and Linear Graph Algorithms. SIAM J. Comput. 1(2): 146-160(1972) BibTeX

[26]

...

[27]

Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX

[28]

Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX

[29]

Jeffrey D. Ullman, Allen Van Gelder: Efficient tests for top-down termination of logical rules. J. ACM 35(2): 345-373(1988) BibTeX

[30]

...

[31]

Eugene Wong, Karel Youssefi: Decomposition - A Strategy for Query Processing. ACM Trans. Database Syst. 1(3): 223-241(1976) BibTeX

[32]

Clement T. Yu, Keh-Chang Guh, David Brill, Arbee L. P. Chen: Partition Strategy for Distributed Query Processing in Fast Local Networks. IEEE Trans. Software Eng. 15(6): 780-793(1989) BibTeX

[33]

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. 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)
2. Ladjel Bellatreche, Kamalakar Karlapalem, Qing Li: Derived Horizontal Class Partitioning in OODBs: Design Strategies, Analytical Model and Evaluation. ER 1998: 465-479
3. Sha Guo, Wei Sun, Mark Allen Weiss: Solving Satisfiability and Implication Problems in Database Systems. ACM Trans. Database Syst. 21(2): 270-293(1996)