Query Answering Algorithms for Information Agents

Abstract

The database theory community, centered around the PODS (Principles of Database Systems) conference has had a long-term interest in logic as a way to represent "data," "information," and "knowledge" (take your pick on the term -- it boils down to facts or atoms and rules, usually Horn The approach of this community has been "slow and steady," preferring to build up carefully from simple special cases to more general ideas, always paying attention to how effciently we can process queries and perform other operations on the facts and rules. A powerful theory has developed, and it is beginning to have some impact on applications, especially information-integration engines. Datalog The term Datalog has been coined to refer to Prolog-like rules without function symbols, treated as logic program. Unlike Prolog, however, the conventional leastfixed-point semantics of the rules is used whenever possible. Example 1: The rules for ancestors can be written as the following Datalog program. anc(X,Y) :par(X,Y) anc(X,Y) :anc(Z,Y) That is, Y is an ancestor of X if Y is a parent of X or if there is some Z that is an ancestor of X and a descendant of Y . Because of the least-fixed-point semantics, there is no question of this program entering a loop, as the corresponding Prolog program would.Generally, we divide predicates into two classes. EDB (extensional database) predicates are stored as relations, while IDB (intensional database) predicates are defined by the heads (left sides) of rules only. Either EDB or IDB predicates can appear in subgoals of the bodies (right sides) of rules. Sometimes, Datalog is extended to allow negated subgoals. That extension causes the least-fixed-point semantics to become problematic when the rules are recursive, and several approaches such as stratified negation and well-founded semantics have been developed to define suitable meanings for such Datalog programs.