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