Functional dependencies in Horn clause queries

When a database query is expressed as a set of Horn clauses whose execution is by top-down resolution of goals, there is a need to improve the backtracking behavior of the interpreter. Rather than putting on the programmer the onus of using extra-logical operators such as cut to improve performance,...

Full description

Saved in:
Bibliographic Details
Published in:ACM transactions on database systems 1991-03, Vol.16 (1), p.31-55
Main Authors: Mendelzon, Alberto O., Wood, Peter T.
Format: Article
Language:English
Subjects:
Applied sciences
Artificial intelligence
Computer science
control theory
systems
Computing methodologies
Constraint and logic programming
Data management systems
Database management system engines
Database query processing
Database query processing and optimization (theory)
Database theory
Exact sciences and technology
Information systems
Information systems. Data bases
Knowledge representation and reasoning
Logic
Logic programming and answer set programming
Machine learning
Machine learning approaches
Memory organisation. Data processing
Rule learning
Software
Theory and algorithms for application domains
Theory of computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:When a database query is expressed as a set of Horn clauses whose execution is by top-down resolution of goals, there is a need to improve the backtracking behavior of the interpreter. Rather than putting on the programmer the onus of using extra-logical operators such as cut to improve performance, we show that some uses of the cut can be automated by inferring them from functional dependencies. This requires some knowledge of which variables are guaranteed to be bound at query execution time; we give a method for deriving such information using data flow analysis.
ISSN:0362-5915
1557-4644
DOI:10.1145/103140.103142