A Time Bound on the Materialization of some Recursively Defined Views.
Yannis E. Ioannidis:
A Time Bound on the Materialization of some Recursively Defined Views.
VLDB 1985: 219-226@inproceedings{DBLP:conf/vldb/Ioannidis85,
author = {Yannis E. Ioannidis},
editor = {Alain Pirotte and
Yannis Vassiliou},
title = {A Time Bound on the Materialization of some Recursively Defined
Views},
booktitle = {VLDB'85, Proceedings of 11th International Conference on Very
Large Data Bases, August 21-23, 1985, Stockholm, Sweden},
publisher = {Morgan Kaufmann},
year = {1985},
pages = {219-226},
ee = {db/conf/vldb/Ioannidis85.html},
crossref = {DBLP:conf/vldb/85},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
Abstract
A virtual relation (or view) can be defined with a
recursive statement that is a function of one or
more base relations. In general, the number of
times such a statement must be applied in order to
retrieve all the tuples in the virtual relation
depends on the contents of the base relations
involved in the definition. However, there exist
statements for which there is an upper bound on
the number of applications necessary to form the
virtual relation, independent of the contents of the
base relations. Considering a restricted class of
recursive statements, we give necessary and
sufficient conditions for statements in the class to
have this bound.
Copyright © 1985 by the VLDB Endowment.
Permission to copy without fee all or part of this material is granted provided that the copies are not made or
distributed for direct commercial advantage, the VLDB
copyright notice and the title of the publication and
its date appear, and notice is given that copying
is by the permission of the Very Large Data Base
Endowment. To copy otherwise, or to republish, requires
a fee and/or special permission from the Endowment.
Online Paper
CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ...
DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...
BibTeX
Printed Edition
Alain Pirotte, Yannis Vassiliou (Eds.):
VLDB'85, Proceedings of 11th International Conference on Very Large Data Bases, August 21-23, 1985, Stockholm, Sweden.
Morgan Kaufmann 1985
Contents BibTeX
References
- [Bond76]
- ...
- [Chan81]
- Chin-Liang Chang:
On Evaluation of Queries Containing Derived Relations in a Relational Data Base.
Advances in Data Base Theory 1979: 235-260 BibTeX
- [Codd70]
- E. F. Codd:
A Relational Model of Data for Large Shared Data Banks.
Commun. ACM 13(6): 377-387(1970) BibTeX
- [Date82]
- ...
- [Ende72]
- ...
- [Gall78]
- ...
- [Gall81]
- ...
- [GAll84]
- Hervé Gallaire, Jack Minker, Jean-Marie Nicolas:
Logic and Databases: A Deductive Approach.
ACM Comput. Surv. 16(2): 153-185(1984) BibTeX
- [Ioan85]
- ...
- [Naqv84]
- Lawrence J. Henschen, Shamim A. Naqvi:
On compiling queries in recursive first-order databases.
J. ACM 31(1): 47-85(1984) BibTeX
- [Reit78]
- Raymond Reiter:
Deductive Question-Answering on Relational Data Bases.
Logic and Data Bases 1977: 149-177 BibTeX
- [Robi65]
- John Alan Robinson:
A Machine-Oriented Logic Based on the Resolution Principle.
J. ACM 12(1): 23-41(1965) BibTeX
Referenced by
- Ke Wang:
Some Positive Results for Boundedness of Multiple Recursive Rules.
ICDT 1995: 383-396
- Guozhu Dong, Jianwen Su:
Increment Boundedness and Nonrecursive Incremental Evaluation of Datalog Queries.
ICDT 1995: 397-410
- Serge Abiteboul, Richard Hull, Victor Vianu:
Foundations of Databases.
Addison-Wesley 1995, ISBN 0-201-53771-0
Contents - Wenyu Lu, Dik Lun Lee, Jiawei Han:
A Study on the Structure of Linear Recursion.
IEEE Trans. Knowl. Data Eng. 6(5): 723-737(1994)
- Jiawei Han, Kangsheng Zeng, Tong Lu:
Normalization of Linear Recursions in Deductive Databases.
ICDE 1993: 559-567
- Guozhu Dong, Jianwen Su:
First-Order Incremental Evaluation of Datalog Queries.
DBPL 1993: 295-308
- Cheong Youn, Hyoung-Joo Kim, Lawrence J. Henschen, Jiawei Han:
Classification and Compilation of Linear Recursive Queries in Deductive Databases.
IEEE Trans. Knowl. Data Eng. 4(1): 52-67(1992)
- Laks V. S. Lakshmanan, Héctor J. Hernández:
Structural Query Optimization - A uniform Framework for Semantic Query Optimization in Deductive Databases.
PODS 1991: 102-114
- Weining Zhang, Clement T. Yu, Daniel Troy:
Necessary and Sufficient Conditions to Linearize Double Recursive Programs in Logic Databases.
ACM Trans. Database Syst. 15(3): 459-482(1990)
- Michael Kifer, Eliezer L. Lozinskii:
On Compile-Time Query Optimization in Deductive Databases by Means of Static Filtering.
ACM Trans. Database Syst. 15(3): 385-426(1990)
- Irène Guessarian:
Deciding Boundedness for Uniformly Connected Datalog Programs.
ICDT 1990: 395-405
- Bin Jiang:
A Suitable Algorithm for Computing Partial Transitive Closures in Databases.
ICDE 1990: 264-271
- Jiawei Han, Wenyu Lu:
Asynchronous Chain Recursions.
IEEE Trans. Knowl. Data Eng. 1(2): 185-195(1989)
- Rakesh Agrawal, Premkumar T. Devanbu:
Moving Selections into Linear Least Fixpoint Queries.
IEEE Trans. Knowl. Data Eng. 1(4): 424-432(1989)
- Yannis E. Ioannidis:
Commutativity and its Role in the Processing of Linear Recursion.
VLDB 1989: 155-163
- Guozhu Dong:
On Distributed Processibility of Datalog Queries by Decomposing Databases.
SIGMOD Conference 1989: 26-35
- Moshe Y. Vardi:
Automata Theory for Database Theoreticans.
PODS 1989: 83-92
- Yehoshua Sagiv, Moshe Y. Vardi:
Safety of Datalog Queries over Infinite Databases.
PODS 1989: 160-171
- Stavros S. Cosmadakis:
On the First-Order Expressibility of Recursive Queries.
PODS 1989: 311-323
- Cheong Youn, Lawrence J. Henschen, Jiawei Han:
Classification of Recursive Formulas in Deductive Databases.
SIGMOD Conference 1988: 320-328
- Moshe Y. Vardi:
Decidability and Undecidability Results for Boundedness of Linear Recursive Queries.
PODS 1988: 341-351
- Peter T. Wood, Alberto O. Mendelzon, Paolo Atzeni:
Idempotent Single-Predicate Horn Clauses.
ICDT 1988: 129-143
- Guozhu Dong:
On the Composition and Decomposition of Datalog Program Mappings.
ICDT 1988: 87-101
- Rakesh Agrawal, Premkumar T. Devanbu:
Moving Selections into Linear Least Fixpoint Queries.
ICDE 1988: 452-461
- Jiawei Han, Ghassan Z. Qadah, Chinying Chaou:
The Processing and Evaluation of Transitive Closure Queries.
EDBT 1988: 49-75
- Weining Zhang, Clement T. Yu:
A Necessary Condition for a Doubly Recursive Rule to be Equivalent to a Linear Recursive Rule.
SIGMOD Conference 1987: 345-356
- H. V. Jagadish, Rakesh Agrawal, Linda Ness:
A Study of Transitive Closure As a Recursion Mechanism.
SIGMOD Conference 1987: 331-344
- Clement T. Yu, Weining Zhang:
Efficient Recursive Query Processing using Wavefront Methods.
ICDE 1987: 652-657
- Stéphane Lafortune, Eugene Wong:
A State Transition Model for Distributed Query Processing.
ACM Trans. Database Syst. 11(3): 294-322(1986)
- Arnon Rosenthal, Sandra Heiler, Umeshwar Dayal, Frank Manola:
Traversal Recursion: A Practical Approach to Supporting Recursive Applications.
SIGMOD Conference 1986: 166-176
- Stavros S. Cosmadakis, Paris C. Kanellakis:
Parallel Evaluation of Recursive Rule Queries.
PODS 1986: 280-293
- Paris C. Kanellakis:
Logic Programming and Parallel Complexity.
ICDT 1986: 1-30
BibTeX
ACM SIGMOD Anthology - DBLP:
[Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:45:25 2009