Compilation-based list processing in deductive databases

Jiawei Han

doi:10.1007/BFb0032426

Compilation-based list processing in deductive databases

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

Abstract

List functions occur frequently in deductive database applications. We study efficient evaluation of linear recursions with list functions in deductive databases. Since most linear recursions can be compiled into chain forms, a chain-based query evaluation method is developed, which selects an efficient query evaluation algorithm based on the analysis of compiled forms and finiteness, termination and query constraints. Interesting techniques, such as chain-split, existence checking and constraint-based evaluation, are developed to improve the performance. Moreover, chain-based evaluation can be generalized to the complex recursions compilable to chain forms.

Original language	English (US)
Title of host publication	Advances in Database Technology — EDBT 1992 - 3rd International Conference on Extending Database Technology, Proceedings
Editors	Alain Pirotte, Georg Gottlob, Claude Delobel
Publisher	Springer
Pages	104-119
Number of pages	16
ISBN (Print)	9783540552703
DOIs	https://doi.org/10.1007/BFb0032426
State	Published - 1992
Externally published	Yes
Event	3rd International Conference on Extending Database Technology, EDBT 1992 - Vienna, Austria Duration: Mar 23 1992 → Mar 27 1992

Publication series

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

Other

Other	3rd International Conference on Extending Database Technology, EDBT 1992
Country/Territory	Austria
City	Vienna
Period	3/23/92 → 3/27/92

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Online availability

10.1007/BFb0032426

Library availability

Discover UIUC Full Text

Cite this

Han, J. (1992). Compilation-based list processing in deductive databases. In A. Pirotte, G. Gottlob, & C. Delobel (Eds.), Advances in Database Technology — EDBT 1992 - 3rd International Conference on Extending Database Technology, Proceedings (pp. 104-119). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 580 LNCS). Springer. https://doi.org/10.1007/BFb0032426

Compilation-based list processing in deductive databases. / Han, Jiawei.

Advances in Database Technology — EDBT 1992 - 3rd International Conference on Extending Database Technology, Proceedings. ed. / Alain Pirotte; Georg Gottlob; Claude Delobel. Springer, 1992. p. 104-119 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 580 LNCS).

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

Han, J 1992, Compilation-based list processing in deductive databases. in A Pirotte, G Gottlob & C Delobel (eds), Advances in Database Technology — EDBT 1992 - 3rd International Conference on Extending Database Technology, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 580 LNCS, Springer, pp. 104-119, 3rd International Conference on Extending Database Technology, EDBT 1992, Vienna, Austria, 3/23/92. https://doi.org/10.1007/BFb0032426

Han J. Compilation-based list processing in deductive databases. In Pirotte A, Gottlob G, Delobel C, editors, Advances in Database Technology — EDBT 1992 - 3rd International Conference on Extending Database Technology, Proceedings. Springer. 1992. p. 104-119. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/BFb0032426

Han, Jiawei. / Compilation-based list processing in deductive databases. Advances in Database Technology — EDBT 1992 - 3rd International Conference on Extending Database Technology, Proceedings. editor / Alain Pirotte ; Georg Gottlob ; Claude Delobel. Springer, 1992. pp. 104-119 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{2176cb1637b7483a86b83a5a2885d3ba,

title = "Compilation-based list processing in deductive databases",

abstract = "List functions occur frequently in deductive database applications. We study efficient evaluation of linear recursions with list functions in deductive databases. Since most linear recursions can be compiled into chain forms, a chain-based query evaluation method is developed, which selects an efficient query evaluation algorithm based on the analysis of compiled forms and finiteness, termination and query constraints. Interesting techniques, such as chain-split, existence checking and constraint-based evaluation, are developed to improve the performance. Moreover, chain-based evaluation can be generalized to the complex recursions compilable to chain forms.",

author = "Jiawei Han",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1992.; 3rd International Conference on Extending Database Technology, EDBT 1992 ; Conference date: 23-03-1992 Through 27-03-1992",

year = "1992",

doi = "10.1007/BFb0032426",

language = "English (US)",

isbn = "9783540552703",

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

publisher = "Springer",

pages = "104--119",

editor = "Alain Pirotte and Georg Gottlob and Claude Delobel",

booktitle = "Advances in Database Technology — EDBT 1992 - 3rd International Conference on Extending Database Technology, Proceedings",

address = "Germany",

}

TY - GEN

T1 - Compilation-based list processing in deductive databases

AU - Han, Jiawei

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

PY - 1992

Y1 - 1992

N2 - List functions occur frequently in deductive database applications. We study efficient evaluation of linear recursions with list functions in deductive databases. Since most linear recursions can be compiled into chain forms, a chain-based query evaluation method is developed, which selects an efficient query evaluation algorithm based on the analysis of compiled forms and finiteness, termination and query constraints. Interesting techniques, such as chain-split, existence checking and constraint-based evaluation, are developed to improve the performance. Moreover, chain-based evaluation can be generalized to the complex recursions compilable to chain forms.

AB - List functions occur frequently in deductive database applications. We study efficient evaluation of linear recursions with list functions in deductive databases. Since most linear recursions can be compiled into chain forms, a chain-based query evaluation method is developed, which selects an efficient query evaluation algorithm based on the analysis of compiled forms and finiteness, termination and query constraints. Interesting techniques, such as chain-split, existence checking and constraint-based evaluation, are developed to improve the performance. Moreover, chain-based evaluation can be generalized to the complex recursions compilable to chain forms.

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

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

U2 - 10.1007/BFb0032426

DO - 10.1007/BFb0032426

M3 - Conference contribution

AN - SCOPUS:0039611133

SN - 9783540552703

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

SP - 104

EP - 119

BT - Advances in Database Technology — EDBT 1992 - 3rd International Conference on Extending Database Technology, Proceedings

A2 - Pirotte, Alain

A2 - Gottlob, Georg

A2 - Delobel, Claude

PB - Springer

T2 - 3rd International Conference on Extending Database Technology, EDBT 1992

Y2 - 23 March 1992 through 27 March 1992

ER -

Compilation-based list processing in deductive databases

Abstract

Publication series

Other

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this