Static estimation of query sizes in horn programs

Saumya K. Debray, Nai Wei Lin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations


Knowledge about relation sizes for queries can be used to improve the performance of deductive database programs, e.g. to plan the order in which body goals are evaluated, or to “map” predicates to processors in distributed systems. For Horn programs, the analysis is complicated by the presence of function symbols and recursion. This paper describes an approach for statically computing upper bound estimates for relation sizes in Horn programs. The techniques axe applicable to a wide class of programs that use structural recursion.

Original languageEnglish (US)
Title of host publicationICDT 1990 - 3rd International Conference on Database Theory, Proceedings
EditorsSerge Abiteboul, Paris C. Kanetlakis
Number of pages15
ISBN (Print)9783540535072
StatePublished - 1990
Externally publishedYes
Event3rd International Conference on Database Theory, ICDT 1990 - Paris, France
Duration: Dec 12 1990Dec 14 1990

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume470 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other3rd International Conference on Database Theory, ICDT 1990

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Static estimation of query sizes in horn programs'. Together they form a unique fingerprint.

Cite this