Paper Info
Title
The complexity of reusing and modifying rulebases
Abstract
This paper develops a method for reusing and modifying deductive databases. Such methods are needed when new rulebased applications differ only slightly from existing ones or when an application is to be incrementally updated. In order to facilitate reuse, we extend deductive databases by the concept of predicate substitution. In this way, during query evaluation, not only variables, but also predicates can be substituted. This paper continues our earlier work on predicate substitution in two directions: (i We extend the concept to a wider class of rulebase modifications, and (ii) we estblish tight bounds on the data complexity of Datalog augmented with substitution, showing it to be EXPTIME-complete. Predicate substitution thus increases the power of Datalog to express database queries. The paper presents a proof theory and model theory for the language, including a fixpoint semantics.
Year
DOI
Venue
1992
10.1145/137097.137900
PODS
Keywords
Field
DocType
deductive databases,new rulebased application,model theory,data complexity,predicate substitution,earlier work,database query,fixpoint semantics,modifying rulebases,modifying deductive databases,proof theory
Programming language,Reuse,Computer science,Proof theory,Theoretical computer science,Model theory,Database theory,Predicate (grammar),Datalog,Fixpoint semantics,Data complexity
Conference
ISBN
Citations 
PageRank 
0-89791-519-4
6
16.25
References 
Authors
5
1
Name
Order
Citations
PageRank
Anthony J. Bonner1733422.63