Abstract. A n umber of ideas concerning information-integration tools can be thought of as constructing answers to queries using views that represent the capabilities of information sources. We review the formal basis of these techniques, which are closely related to containment algorithms for conjunctive queries and/or Datalog programs. Then we compare the approaches taken by A T&T Labs' \Information Manifold" and the Stanford \Tsimmis" project in these terms. Before addressing information-integration issues, let us review some of the basic ideas concerning conjunctive queries, Datalog programs, and their containment. To begin, we use the logical rule notation from Ull88]. Example 1. The following: is a rule that talks about a, a n EDB predicate (\Extensional DataBase," or stored relation), and p, a n IDB predicate (\Intensional DataBase," or predicate whose relation is constructed by rules). In this and several other examples, it is useful to think of a as an \arc" predicate de ning a graph, while other predicates de ne certain structures that might exist in the graph. That is, a(X Y) m e a n s there is an arc from node X to node Y . In this case, the rule says \p(X Z) i s true if there is an arc from node X to node Y and also an arc from Y to Z." That is, p represents paths of length 2. In general, there is one atom, the head, on the left of the \if" sign, :-and zero of more atoms, called subgoals, o n t h e r i g h t side (the body). The head always has an IDB predicate the subgoals can have IDB or EDB predicates. Thus, here p(X Z) is the head, while a(X Y) and a(Y Z) are subgoals. We assume that each v ariable appearing in the head also appears somewhere in the body. This \safety" requirement assures that when we u s e a r u l e , w e a r e not left with unde ned variables in the head when we try to infer a fact about the head's predicate. We also assume that atoms consist of a predicate and zero or more arguments. An argument can be either a variable or a constant. However, we exclude function symbols from arguments.
See Ullman, REF , for a survey of work concerning information-integration tools to answer queries using views that represent the capabilities of information resources.
Information integration using logical views
Theor. Comput. Sci.
Computer Science