Static estimation of query sizes in horn programs

Saumya K. Debray; Nai Wei Lin

doi:10.1007/3-540-53507-1_99

Static estimation of query sizes in horn programs

Saumya K. Debray, Nai Wei Lin

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

8 Scopus citations

Abstract

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 language	English (US)
Title of host publication	ICDT 1990 - 3rd International Conference on Database Theory, Proceedings
Editors	Serge Abiteboul, Paris C. Kanetlakis
Publisher	Springer-Verlag
Pages	514-528
Number of pages	15
ISBN (Print)	9783540535072
DOIs	https://doi.org/10.1007/3-540-53507-1_99
State	Published - 1990
Event	3rd International Conference on Database Theory, ICDT 1990 - Paris, France Duration: Dec 12 1990 → Dec 14 1990

Publication series

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

Other

Other	3rd International Conference on Database Theory, ICDT 1990
Country/Territory	France
City	Paris
Period	12/12/90 → 12/14/90

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-53507-1_99

Cite this

Debray, S. K., & Lin, N. W. (1990). Static estimation of query sizes in horn programs. In S. Abiteboul, & P. C. Kanetlakis (Eds.), ICDT 1990 - 3rd International Conference on Database Theory, Proceedings (pp. 514-528). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 470 LNCS). Springer-Verlag. https://doi.org/10.1007/3-540-53507-1_99

Static estimation of query sizes in horn programs. / Debray, Saumya K.; Lin, Nai Wei.
ICDT 1990 - 3rd International Conference on Database Theory, Proceedings. ed. / Serge Abiteboul; Paris C. Kanetlakis. Springer-Verlag, 1990. p. 514-528 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 470 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Debray, SK & Lin, NW 1990, Static estimation of query sizes in horn programs. in S Abiteboul & PC Kanetlakis (eds), ICDT 1990 - 3rd International Conference on Database Theory, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 470 LNCS, Springer-Verlag, pp. 514-528, 3rd International Conference on Database Theory, ICDT 1990, Paris, France, 12/12/90. https://doi.org/10.1007/3-540-53507-1_99

Debray SK, Lin NW. Static estimation of query sizes in horn programs. In Abiteboul S, Kanetlakis PC, editors, ICDT 1990 - 3rd International Conference on Database Theory, Proceedings. Springer-Verlag. 1990. p. 514-528. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-53507-1_99

Debray, Saumya K. ; Lin, Nai Wei. / Static estimation of query sizes in horn programs. ICDT 1990 - 3rd International Conference on Database Theory, Proceedings. editor / Serge Abiteboul ; Paris C. Kanetlakis. Springer-Verlag, 1990. pp. 514-528 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{37f5b2f0ec0a4594a229c5d48eb3f7c0,

title = "Static estimation of query sizes in horn programs",

abstract = "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.",

author = "Debray, {Saumya K.} and Lin, {Nai Wei}",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1990.; 3rd International Conference on Database Theory, ICDT 1990 ; Conference date: 12-12-1990 Through 14-12-1990",

year = "1990",

doi = "10.1007/3-540-53507-1_99",

language = "English (US)",

isbn = "9783540535072",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer-Verlag",

pages = "514--528",

editor = "Serge Abiteboul and Kanetlakis, {Paris C.}",

booktitle = "ICDT 1990 - 3rd International Conference on Database Theory, Proceedings",

}

TY - GEN

T1 - Static estimation of query sizes in horn programs

AU - Debray, Saumya K.

AU - Lin, Nai Wei

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1990.

PY - 1990

Y1 - 1990

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85020744072&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85020744072&partnerID=8YFLogxK

U2 - 10.1007/3-540-53507-1_99

DO - 10.1007/3-540-53507-1_99

M3 - Conference contribution

AN - SCOPUS:85020744072

SN - 9783540535072

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 514

EP - 528

BT - ICDT 1990 - 3rd International Conference on Database Theory, Proceedings

A2 - Abiteboul, Serge

A2 - Kanetlakis, Paris C.

PB - Springer-Verlag

T2 - 3rd International Conference on Database Theory, ICDT 1990

Y2 - 12 December 1990 through 14 December 1990

ER -

Static estimation of query sizes in horn programs

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this