ACM SIGMOD Anthology TKDE dblp.uni-trier.de

Constraint-Based Query Evaluation in Deductive Databases.

Jiawei Han: Constraint-Based Query Evaluation in Deductive Databases. IEEE Trans. Knowl. Data Eng. 6(1): 96-107(1994)
@article{DBLP:journals/tkde/Han94,
  author    = {Jiawei Han},
  title     = {Constraint-Based Query Evaluation in Deductive Databases},
  journal   = {IEEE Trans. Knowl. Data Eng.},
  volume    = {6},
  number    = {1},
  year      = {1994},
  pages     = {96-107},
  ee        = {db/journals/tkde/Han94.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Constraints play an important role in the efficient query evaluation in deductive databases. In this paper, constraint-based query evaluation in deductive databases is investigated, with the emphasis on linear recursions with function symbols. Constraints are classified into three classes: (i) rule constraints, (ii) integrity constraints, and (iii) query constraints. Techniques are developed for the maximal use of different kinds of constraints in rule compilation and query evaluation. Our study on the roles of different classes of constraints in set-oriented evaluation of linear recursions shows that (i) rule constraints should be integrated with their corresponding deduction rules in the compilation of recursions; (ii) integrity constraints, including finiteness constraints and monotonicity constraints, should be used in the analysis of finite evaluability and termination for specific queries; and (iii) query constraints, which are often useful in search space reduction and termination, should be transformed, when necessary and be pushed into the compiled chains as deeply as possible for efficient evaluation. Our constraint-based query processing technique integrates query-independent compilation and chain-based query evaluation methods and demonstrates its great promise in deductive query evaluation.

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

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 3, TKDE 1993-1995" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

References

[1]
François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52 BibTeX
[2]
François Bancilhon, David Maier, Yehoshua Sagiv, Jeffrey D. Ullman: Magic Sets and Other Strange Ways to Implement Logic Programs. PODS 1986: 1-15 BibTeX
[3]
Catriel Beeri, Paris C. Kanellakis, François Bancilhon, Raghu Ramakrishnan: Bounds on the Propagation of Selection into Logic Programs. PODS 1987: 214-226 BibTeX
[4]
Alexander Brodsky, Yehoshua Sagiv: On Termination of Datalog Programs. DOOD 1989: 47-64 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]
Jiawei Han, Wenyu Lu: Asynchronous Chain Recursions. IEEE Trans. Knowl. Data Eng. 1(2): 185-195(1989) BibTeX
[7]
Jiawei Han, Qiang Wang: Evaluation of functional linear recursions: a compilation approach. Inf. Syst. 16(4): 463-469(1991) BibTeX
[8]
Jiawei Han, Kangsheng Zeng: Automatic generation of compiled forms for linear recursions. Inf. Syst. 17(4): 299-322(1992) BibTeX
[9]
Jiawei Han: Compilation-Based List Processing in Deductive Databases. EDBT 1992: 104-119 BibTeX
[10]
Jiawei Han: Chain-Split Evaluation in Deductive Databases. ICDE 1992: 376-384 BibTeX
[11]
Lawrence J. Henschen, Shamim A. Naqvi: On compiling queries in recursive first-order databases. J. ACM 31(1): 47-85(1984) BibTeX
[12]
Tomasz Imielinski: Intelligent Query Answering in Rule Based Systems. J. Log. Program. 4(3): 229-257(1987) BibTeX
[13]
Joxan Jaffar, Jean-Louis Lassez: Constraint Logic Programming. POPL 1987: 111-119 BibTeX
[14]
Bin Jiang: A Suitable Algorithm for Computing Partial Transitive Closures in Databases. ICDE 1990: 264-271 BibTeX
[15]
Paris C. Kanellakis, Gabriel M. Kuper, Peter Z. Revesz: Constraint Query Languages. PODS 1990: 299-313 BibTeX
[16]
David B. Kemp, Kotagiri Ramamohanarao, Isaac Balbin, Krishnamurthy Meenakshi: Propagating Constraints in Recusive Deduction Databases. NACLP 1989: 981-998 BibTeX
[17]
Ravi Krishnamurthy, Raghu Ramakrishnan, Oded Shmueli: A Framework for Testing Safety and Effective Computability of Extended Datalog (Extended Abstract). SIGMOD Conference 1988: 154-163 BibTeX
[18]
Laks V. S. Lakshmanan, Rokia Missaoui: On Semantic Query Optimization in Deductive Databases. ICDE 1992: 368-375 BibTeX
[19]
Sanggoo Lee, Jiawei Han: Semantic Query Optimization in Recursive Databases. ICDE 1988: 444-451 BibTeX
[20]
Michael J. Maher, Peter J. Stuckey: Expanding Query Power in Constraint Logic Programming Languages. NACLP 1989: 20-36 BibTeX
[21]
David Maier, David Scott Warren: Computing with Logic: Logic Programming with Prolog. Benjamin/Cummings 1988, ISBN 0-8053-6681-4
BibTeX
[22]
Raghu Ramakrishnan, François Bancilhon, Abraham Silberschatz: Safety of Recursive Horn Clauses With Infinite Relations. PODS 1987: 328-339 BibTeX
[23]
Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan: CORAL - Control, Relations and Logic. VLDB 1992: 238-250 BibTeX
[24]
Arnon Rosenthal, Sandra Heiler, Umeshwar Dayal, Frank Manola: Traversal Recursion: A Practical Approach to Supporting Recursive Applications. SIGMOD Conference 1986: 166-176 BibTeX
[25]
Yehoshua Sagiv, Moshe Y. Vardi: Safety of Datalog Queries over Infinite Databases. PODS 1989: 160-171 BibTeX
[26]
Leon Sterling, Ehud Y. Shapiro: The Art of Prolog - Advanced Programming Techniques. MIT Press 1986, ISBN 0-262-19250-0
BibTeX
[27-1]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX
[27-2]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX

Referenced by

  1. Jiawei Han: Chain-Split Evaluation in Deductive Databases. IEEE Trans. Knowl. Data Eng. 7(2): 261-273(1995)
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
IEEE Transactions on Data and Knowledge Engineering: Copyright © by IEEE,
Joint ACM SIGMOD / IEEE Computer Society Anthology: Copyright © by ACM (info@acm.org) and IEEE, Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sun May 17 00:27:58 2009