Generalized Bottom-Up Query Evaluation

authored by: Stefan Brass, Udo W. Lipeck
Abstract: Our goal is to generalize the well known bottom-up, set-oriented query evaluation for deductive databases in two aspects: First, we consider arbitrary danses as rules in the database, not only Horn clauses or clauses with stratified negation. This allows to represent disjunctive information, in the database as well as in answers to queries. We utilize NF² relations for modelling sets of disjunctive facts and operations of the corresponding relational algebra for computing consequences and answers. Thus our algorithm should be of practical importance for applying database techniques in generalized deductions. Second, we parameterize the implicit database completion which underlies query evaluation. The classical rule for Horn clause databases, which only assumes the negation of facts not implied by the database, is not applicable to disjunctive databases. Moreover, the choice of completion often depends on the intended application. Therefore we allow the specification of arbitrary clauses as defaults, and we extend our algorithm to consider such general defaults.
Organisation(s): Institute of Practical Computer Science
Type: Conference contribution
Pages: 88-103
No. of pages: 16
Publication date: 1992
Publication status: Published
Peer reviewed: Yes
ASJC Scopus subject areas: Theoretical Computer Science, General Computer Science
Electronic version(s): https://doi.org/10.1007/BFb0032425 (Access: Closed)

BibTeX

@inproceedings{b598d5b9caee46aea1670008f4489f68,
title = "Generalized Bottom-Up Query Evaluation",
abstract = "Our goal is to generalize the well known bottom-up, set-oriented query evaluation for deductive databases in two aspects: First, we consider arbitrary danses as rules in the database, not only Horn clauses or clauses with stratified negation. This allows to represent disjunctive information, in the database as well as in answers to queries. We utilize NF2 relations for modelling sets of disjunctive facts and operations of the corresponding relational algebra for computing consequences and answers. Thus our algorithm should be of practical importance for applying database techniques in generalized deductions. Second, we parameterize the implicit database completion which underlies query evaluation. The classical rule for Horn clause databases, which only assumes the negation of facts not implied by the database, is not applicable to disjunctive databases. Moreover, the choice of completion often depends on the intended application. Therefore we allow the specification of arbitrary clauses as defaults, and we extend our algorithm to consider such general defaults.",
author = "Stefan Brass and Lipeck, {Udo W.}",
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/BFb0032425",
language = "English",
isbn = "9783540552703",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "88--103",
editor = "Alain Pirotte and Georg Gottlob and Claude Delobel",
booktitle = "Advances in Database Technology",
address = "Germany",
}