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
  author    = {Yannis E. Ioannidis},
  editor    = {Alain Pirotte and
               Yannis Vassiliou},
  title     = {A Time Bound on the Materialization of some Recursively Defined
  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,}


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

ACM SIGMOD Anthology

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


Chin-Liang Chang: On Evaluation of Queries Containing Derived Relations in a Relational Data Base. Advances in Data Base Theory 1979: 235-260 BibTeX
E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX
Hervé Gallaire, Jack Minker, Jean-Marie Nicolas: Logic and Databases: A Deductive Approach. ACM Comput. Surv. 16(2): 153-185(1984) BibTeX
Lawrence J. Henschen, Shamim A. Naqvi: On compiling queries in recursive first-order databases. J. ACM 31(1): 47-85(1984) BibTeX
Raymond Reiter: Deductive Question-Answering on Relational Data Bases. Logic and Data Bases 1977: 149-177 BibTeX
John Alan Robinson: A Machine-Oriented Logic Based on the Resolution Principle. J. ACM 12(1): 23-41(1965) BibTeX

Referenced by

  1. Ke Wang: Some Positive Results for Boundedness of Multiple Recursive Rules. ICDT 1995: 383-396
  2. Guozhu Dong, Jianwen Su: Increment Boundedness and Nonrecursive Incremental Evaluation of Datalog Queries. ICDT 1995: 397-410
  3. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
  4. 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)
  5. Jiawei Han, Kangsheng Zeng, Tong Lu: Normalization of Linear Recursions in Deductive Databases. ICDE 1993: 559-567
  6. Guozhu Dong, Jianwen Su: First-Order Incremental Evaluation of Datalog Queries. DBPL 1993: 295-308
  7. 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)
  8. 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
  9. 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)
  10. 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)
  11. Irène Guessarian: Deciding Boundedness for Uniformly Connected Datalog Programs. ICDT 1990: 395-405
  12. Bin Jiang: A Suitable Algorithm for Computing Partial Transitive Closures in Databases. ICDE 1990: 264-271
  13. Jiawei Han, Wenyu Lu: Asynchronous Chain Recursions. IEEE Trans. Knowl. Data Eng. 1(2): 185-195(1989)
  14. Rakesh Agrawal, Premkumar T. Devanbu: Moving Selections into Linear Least Fixpoint Queries. IEEE Trans. Knowl. Data Eng. 1(4): 424-432(1989)
  15. Yannis E. Ioannidis: Commutativity and its Role in the Processing of Linear Recursion. VLDB 1989: 155-163
  16. Guozhu Dong: On Distributed Processibility of Datalog Queries by Decomposing Databases. SIGMOD Conference 1989: 26-35
  17. Moshe Y. Vardi: Automata Theory for Database Theoreticans. PODS 1989: 83-92
  18. Yehoshua Sagiv, Moshe Y. Vardi: Safety of Datalog Queries over Infinite Databases. PODS 1989: 160-171
  19. Stavros S. Cosmadakis: On the First-Order Expressibility of Recursive Queries. PODS 1989: 311-323
  20. Cheong Youn, Lawrence J. Henschen, Jiawei Han: Classification of Recursive Formulas in Deductive Databases. SIGMOD Conference 1988: 320-328
  21. Moshe Y. Vardi: Decidability and Undecidability Results for Boundedness of Linear Recursive Queries. PODS 1988: 341-351
  22. Peter T. Wood, Alberto O. Mendelzon, Paolo Atzeni: Idempotent Single-Predicate Horn Clauses. ICDT 1988: 129-143
  23. Guozhu Dong: On the Composition and Decomposition of Datalog Program Mappings. ICDT 1988: 87-101
  24. Rakesh Agrawal, Premkumar T. Devanbu: Moving Selections into Linear Least Fixpoint Queries. ICDE 1988: 452-461
  25. Jiawei Han, Ghassan Z. Qadah, Chinying Chaou: The Processing and Evaluation of Transitive Closure Queries. EDBT 1988: 49-75
  26. 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
  27. H. V. Jagadish, Rakesh Agrawal, Linda Ness: A Study of Transitive Closure As a Recursion Mechanism. SIGMOD Conference 1987: 331-344
  28. Clement T. Yu, Weining Zhang: Efficient Recursive Query Processing using Wavefront Methods. ICDE 1987: 652-657
  29. Stéphane Lafortune, Eugene Wong: A State Transition Model for Distributed Query Processing. ACM Trans. Database Syst. 11(3): 294-322(1986)
  30. Arnon Rosenthal, Sandra Heiler, Umeshwar Dayal, Frank Manola: Traversal Recursion: A Practical Approach to Supporting Recursive Applications. SIGMOD Conference 1986: 166-176
  31. Stavros S. Cosmadakis, Paris C. Kanellakis: Parallel Evaluation of Recursive Rule Queries. PODS 1986: 280-293
  32. Paris C. Kanellakis: Logic Programming and Parallel Complexity. ICDT 1986: 1-30
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:45:25 2009