Recursive Plans for Information Gathering

1 Introduction

The problem of information integration (a.k.a. informa­ tion gathering agents) has recently received considerable attention due to the growing number of structured infor­ mation sources available online. Information integration systems (e.g., the Internet Soft bot [Etzioni and Weld, 1994), SIMS [Arens et a/., 1996), TSIMMIS [Chawathe eta/., 1994], the Information Manifold [Levy eta/., 1996], Occam [Kwok and Weld, 1996], Infomaster [Duschka and Genesereth, 1997b]) provide a uniform query interface to the multiple information sources, thereby freeing the user from having to locate the relevant sources, query each one in isolation, and combine manually the infor­ mation from the different sources.

Alon Y. Levy U.S.A.

AT&T Laboratories 600 Mountain A venue Murray Hill, New Jersey 07974

Information integration systems are based . on the fol­ lowing general architecture. The user interacts with a uniform interface in the form of a set of virtual rela­ tion names that are used in formulating queries. The actual data is stored in external sources (called the source relations). In order for the system to be able to answer queries, we must specify a mapping between the virtual relations and the source relations. The most common method to specify these mappings (em­ ployed in [Levy et a/., 1996; Kwok and Weld, 1996; Duschka and Genesereth, 1997b]) is to describe each source relation as the result of a conjunctive query (i .e., a single Horn rule) over the virtual relations. For exam­ ple, an information source containing papers authored by AI researchers would be described as follows :

The relations paper, author and ai are virtual relations that can be used in formulating queries, and db1 is a source relation .

Given a query from the user, formulated in terms of the virtual relations, the system must translate it to a query that mentions only the source relations, because only those relations are actually available. That is, the system needs to find a query expression, (or, a set of conjunctive queries), that mentions only the source re­ lations, and is equivalent to the original query. The new query is called a query plan (or a query rewriting) , and the translation problem is known as the problem of rewriting queries using views. The views (a term used in database systems to refer to predefined queries) are the relations in the sources. The rewriting problem has also been investigated in the database literature because of its importance for query optimization and data ware­ housing [Yang and Larson, 1987; Chaudhuri et a/., 1995; Levy et a/., 1995; Rajaraman et a/., 1995; Qian, 1996; Duschka and Genesereth , 1997a].

Previous results on the rewriting problem are of lim­ ited practical use for several reasons. First, they have concentrated on showing a bound on the size of the resulting query plan [Levy et a/. , 1995; Rajaraman et a/., 1995]. These results establish the complexity of the rewriting problem, but yield only non-deterministic algo­ rithms for its solution. Second, they considered only the problem of finding an equivalent rewriting of the query using the source relations. In practice, the collection of available sources may not contain all the information needed to answer a query, and therefor:e, we need to re­ sort to maximally-contained rewritings. A maximally­ contained rewriting provides all the answers that are possible to obtain from the sources, but the expression describing the rewriting may not be equivalent to the original query. For example, if we only have the db1 source available, and our query asks for all papers by Computer Science researchers, then the following is a maximally-contained rewriting:

The third problem is that many sources encountered in practice have limitations on the binding patterns they support, or may satisfy certain functional dependencies. As an example of binding-pattern restrictions, a name server of an institution, holding the addresses of its em­ ployees, will not provide the list of all employees and their addresses. Instead, it will provide the address for a given name. In the case of equivalent rewritings, Ra­ jaraman et al. [Rajaraman et a/., 1995] describe a bound on the size of the query plans that need to be consid­ ered. However, Kwok and Weld [Kwok and Weld, 1996] show that if we restrict our plans to be sets of conjunc­ tive queries, then there may not be a finite maximally­ contained rewriting. As an example of a functional de­ pendency, the year of a conference functionally deter­ mines its location. The presence of functional dependen­ cies further complicates the rewriting problem because it allows rewritings that are not valid otherwise. By ignor­ ing the functional dependencies, we may miss answers to the query.

In this paper we introduce the new class of recursive query plans for information gathering. Instead of plans being only sets of conjunctive queries, they can now be recursive sets offunction-free Horn rules. Using recursive plans, we are able to settle two open problems. First, we describe an algorithm for finding the maximally­ contained rewriting in the presence of functional de­ pendencies. Second, we describe an algorithm for find­ ing the maximally-contained rewriting in the presence of binding-pattern restrictions, which was not possible without recursive plans.

Another significant advantage of our method is that it is generative, rather than descriptive. Our algorithms generate the rewriting in time that is polynomial in the size of the query. In contrast, previous methods [Levy et al., 1995; Rajaraman et al., 1995] describe the space of possible candidate rewritings, and propose heuristics for searching this space [Kwok and Weld, 1996; Levy et al.,

1996).1 These methods combine the process of finding a rewriting with the process of checking whether it is equivalent to the original query (which is NP-hard) . In contrast , our method isolates the process of generating the maximally-contained rewriting, which can be done much more efficiently.

2 Preliminaries

Relations and queries: Our representation of the do­ main and of the information sources includes a set of relations. For every relation, we associate an attribute name to each of its arguments. For example, the at­ tribute names of the binary relation author may be Paper and Person. For a tuple t of a relation R, we denote by t .A the value of the attribute A in t.

A function-free Horn rule is an expression of the form

where p, and p1 , ... , Pn are relation names, and X , X 1 , . . . , Xn are tuples of variables and constants such that any variable appearing in X appears also in X1 U ... UXn. The head of the rule is p(X), and its body is Pl (Xl), . . . , Pn(Xn)· The base relations of a set of Horn rules are the relations that appear only in the bodies of the rules and not in the heads (and therefore their exten­ sion includes only explicitly stored tuples). Given a set of rules, we can define a dependency graph, whose nodes are the relations appearing in the rules. There is an arc from the node of relation p; to the node of predicate p if p; appears in the body of a rule whose head relation is p. The rules are said to be recursive if there is a cycle in the dependency graph.

A query is a set of function-free Horn rules. A con­ junctive query is a single non-recursive Horn rule. One of the relations in the query is distinguished as the query relation, and its extension is the answer to the query.

Query containment: In our discussion we will need to compare between different queries. We use the condi­ tion of containment to compare queries. Let us denote by q(D) the result of evaluating query q on database D. Given two queries q1 and q2 , we say that q1 is contained in q2 if for every database D, q1(D) ~ q2(D). The fun­ damental results on containment of conjunctive queries and function-free Horn rules are described in [Chan­ dra and Merlin, 1977; Sagiv and Yannakakis, 1980; Shmueli, 1993]

1 The algorithm in [Levy et al. , 1996] checks whether the plans can be executed given the binding-pattern restrictions, but is not guaranteed to produce the maximally-contained rewriting when these restrictions are present. The algorithm in [Kwok and Weld, 1996] produces only conjunctive plans that are guaranteed to adhere to the limitations on binding patterns, but is not guar~nteed to compute the maximally­ contained plan.

Functional dependencies: An instance of a relation p satisfies the functional dependency AI , ... , An -+ B if for every two tuples t and u in p with t .A; = u.A; for i = 1, .. . , n , also t .B = u.B. We will abbreviate a set of attributes AI, . . . , An by A.

When the relations satisfy a set of functional depen­ dencies :E, we refine our notion of containment to relative containment: Query qi is contained in query q2 relative to :E, denoted qi ~E q2 , iffor each database D satisfying the functional dependencies in :E, qi(D) ~ q2(D).

In order to decide containment of conjunctive queries in the presence of functional dependencies, Aho et al. [Aho et al. , 1979] show that it suffices to precede the containment algorithm by applying the chase algorithm to the contained query. The chase algorithm applies the following transformation to the body of a conjunctive query q until no changes can be made. If the functional dependency A -+ B holds for a relation p , and a con­ junctive query q has two sub goals of p, 9I and 92, with the same variables or values for the attributes A, and 9I has a variable X for attribute B, then we replace the occurrences of X in q by the value or variable for B in 92 ·

Modeling information sources and query plans: The domain model of an information agent is a set of virtual relations. The relations are virtual because they are only meant to provide the user a uniform interface to a multitude of information sources, and the agent does not actually store the extensions of these relations. In our discussion, we assume that a user query is a conjunc­ tive query over the virtual relations. 2

The agent models the contents of the external informa­ tion sources by a set of source relations, that are disjoint from the virtual relations. To answer user queries, the agent must also have a mapping between the virtual and source relations. The mappings, called source descrip­ tions, are specified by a set of conjunctive queries, whose bodies contain only virtual relations and their heads are source relations. The meaning of such a mapping is that all the tuples that are found in the information source satisfy the query over the virtual relations. 3 Given a query q from the user , the agent needs to formulate a query plan, which is a query that bottoms out in the source relations and produces answers to q. A query plan is a set of Horn rules whose base predicates include only the source relations.

2 0ur results apply also to the case in which user queries are recursive [Duschka and Genesereth, 1997a] .

3 Several authors have distinguished the case in· which the source contains all the tuples that satisfy the query from the case in which some tuples may be missing from the source [Et­ zioni et al., 1994; Levy, 1996]. For our discussion this distinc­ tion does not matter.

Example 2.1: Consider a domain model where parent , male and female are virtual relations. The mappings below say that the source relations VI and v2 store the father and mother relation, respectively.

The following query plan determines all grandparents of ann from the available sources:

The expansion of a query plan P , denoted pexp , is obtained from P by replacing all source-relation literals by their definitions. Existentially quantified variables in a source description are replaced by fresh variables in the expansion.

A query plan P is maximally-contained in a query q, relative to a set of functional dependencies :E, if pexp ~E q, and for every query plan PI, if P:xp ~E q then P:xp ~E pexp .

3 Functional Dependencies

We use the following example throughout this section to illustrate the difficulties introduced by functional depen­ dencies and to present our algorithm. Suppose we have the virtual relations

describing the conference at which a paper was pre­ sented, the publication year of a paper, and the location a conference was held at in a given year. A paper is only presented at one conference and published in one year. Also, in a given year a conference is held at a specific location. Therefore we have three functional dependen­ cies:

conference: Paper-+ Conference year: Paper -+ Year location: Conference, Year-+ Location

We have the following information sources:

VI tells us in which conference and year a paper was presented, and v2 stores the location of the presentation of a paper directly with the paper. Assume a user wants to know where IJCAI '91 was held :

The following plan would answer the query:

The query plan finds some paper presented at IJCAI '91 using v1, and then finds the location of the conference this paper was presented at using v2 . This plan is correct only because every paper is presented at one conference and in one year. In fact, if these dependencies would not hold, there would be no way of answering this query using the sources. It is also important to note that view v1 is needed in the query plan even though the predicates in v1 , conference and year, don't appear in the query q at all. Without functional dependencies, only views that contain predicates appearing in the user query need to be considered [Levy et al., 1995].

In the following we are going to give a construction of query plans that is guaranteed to be maximally­ contained in the given queries, even in the presence of functional dependencies. The key to the construction is a set of inverse rules, whose purpose is to recover tu­ ples of the virtual relations from the source relations. In the following definition we use a set of function symbols; for every source relation v with variables X1, ... , Xn in the body but not in the head of the source description, we have a function symbol fv,i· These function symbols can later be removed from the query plan 4 [Duschka and Genesereth, 1997a].

Definition 3.1: {inverse rules) Let v be a source de­ scription

is an inverse rule of v. We modify Xj to obtain the tuple Xj as follows: if X is a constant or is a variable in X, then X is unchanged in Xj. Otherwise, X is one of the variables X; appearing in the body of v but not in X, and X is replaced by fv,;(X) in Xj,

We denote the set of inverse rules of the views in V by v-1. .

Continuing with our example, the inverse rules for v1 and v2 are:

For example, rule r5 extracts from v2 that some con­ ference in some year was held in location L. Suppose that v1 stores the information that the paper "Fuzzy Dynamic Systems" was presented at IJCAI '91, and v2 stores the information that "Fuzzy Dynamic Systems" was presented in Sydney. The inverse rules derive the following facts:

4 It is not necessary to remove function symbols. Function symbols are only introduced in inverse rules, and can never become nested. Therefore, termination of bottom-up evalua­ tion is guaranteed even in the presence of function symbols. Only tuples not containing function symbols are considered answers to a query plan.

year

location

The inverse rules don't take into account the presence of the functional dependencies. For example, because of the functional dependency in relation conference, Paper --+ Conference, it is possible to conclude that the function term !I (fuzzy, sydney) must actually be the same as the constant ijcai. We model this inference by introducing a new binary relation e. The intended meaning of e is that e( c1 , c2) holds if and only if c1 and c2 must be equal under the given functional dependen­ cies. Hence, the extension of e includes the extension of = (i.e., for every X, e(X, X)), and the tuples that can be derived by the following chase rules (e(A, A') is a shorthand for e(A1,Ai), ... ,e(An,A~)): 5

Definition 3.2: (chase rules) Let A --+ B be a func­ tional dependency satisfied by a virtual relation p. Let C be the attributes of p that are not in A, B. The chase rule corresponding to A --+ B, denoted chase(A --+ B) , is the following rule:

We denote by chase(E) the set of chase rules corre­ sponding to the functional dependencies in E.

In our example, the chase rules are

The chase rules allow us to derive the following facts in relation e:

5 We only require relation e to be reflexive for ease of ex­ position. For every rule r having a subgoal e(X, Y) in its body, we could add a modified version of rule r with subgoal e(X, Y) removed and X replaced by Y . The resulting set of rules wouldn't require e to be reflexive.

The extension of e is reflexive by construction, and is symmetric because of the symmetry in the chase rules . To guarantee that e is an equivalence relation, it is still needed to enforce transitivity of e. The following rule, denoted by T , is sufficient for guaranteeing transitivity of relation e:

The final step in the construction is to rewrite query q in a way that it can use the equivalences derived in relation e.

We define the query ij by modifying q iteratively as follows. If c is a constant in one of the subgoals of q, we replace it by a new variable Z, and add the sub goal e(Z, c). If X is a variable in the head of q, we replace X in the body of q by a new variable X', and add the subgoal e(X', X). If a variable Y that is not in the head of q appears in two subgoals of q, we replace one of its occurrences by Y', and add the subgoal e(Y', Y). We continue until we cannot apply this rule anymore. Our example query would be rewritten to

Note that evaluating query ij on the reconstructed virtual relations and the derived equivalence relation e yields the desired result: IJCAI '91 was held in Sydney.

Given a query q, a set of source descriptions V, and a set of functional dependencies ~ , the constructed query plan includes ij, the inverse rules v- 1 ' the chase rules chase(~) and the transitivity rule T. The following the­ orem shows that this query plan is maximally-contained in q relative to ~ .

Theorem 3.1: Let ~ be a set of functional dependen­ cies, V a set of conjunctive source descriptions, and let q be a conjunctive query over the virtual relations. Let R denote the set of rules v- 1 U chase(~) U T . Then, ij U R is maximally-contained in q relative to ~. Furthermore, ij U R can be constructed in time polynomial in the size of q, V, and~. 0

Proof: The key to the proof is to show that for every conjunctive query plan P ~E q, p exp ~E (ij U R)exp . Because recursive query plans can be seen as an encoding of the union of infinitely many conjunctive query plans, it suffices to prove the claim for all conjunctive query plans. We prove the following statement by induction on k: if q is a query, P is a conjunctive query plan, and e1, .. . , ek is a sequence of queries with e1 = p exp, ek ~ q, and ei+1 results from e; by applying a chase step, then pexp ~E (ij U R)exp. This would prove that ij U R is maximally-contained in q relative to ~.

For k = 1, pexp is contained in q. As shown in [Duschka and Genesereth, 1997al, this implies that pexp is contained in ( q u v-1 yxp 0 It follows that p exp is con­ tained in ( ij U R) exp relative to ~.

For the induction step, let k > 1 and assume ek- 1 Cl q. Let A -+ B be the functional dependency that holds for relation p and that is applied from ek- 1 to ek. Then ek-1 contains two subgoals of p, g1 and g2 , with the same values/variables for the attributes in A, and g1 contains a variable X for attribute B that is replaced by some value/variable in ek. Let h be the containment mapping [Chandra and Merlin, 1977] that shows that q contains ek. Replace every value/variable X; in an argu­ ment position in q that is mapped by h to an argument position in ek that used to be variable X in ek-1 by a new variable XI. For each of the new variables Xi, add two subgoals of p to q with the identical new variables for the corresponding attributes A, X; and Xi for attribute B respectively, and new variables for the remaining at­ tributes. We can now find a containment mapping from query q' to query ek-1· This shows that ek-1 is con­ tained in q'. Therefore, pexp = e1, ... , ek-1 is a chase sequence with ek_ 1 ~ q'. By the induction hypothesis we have that pexp ~ (ij' U R)exp. Using the chase rule chase(A -+ B) , the transitivity rule, and the reflexivity of relation e, we can show that ij' U R ~ ij U R . It follows that pexp ~E ( ij U R )exp.

Query ij contains all subgoals in q, and at most as many additional subgoals of e as the sum of all arities of the subgoals in q. Also, there are as many inverse rules as there are subgoals in all source descriptions in V to­ gether. Finally, there are exactly as many chase rules as there are functional dependencies in ~. We can conclude that ij U R can be constructed in time polynomial in the size of q, V and ~ . 0

4 Limitations on binding patterns

Some information sources cannot answer arbitrary atomic queries on the relation they contain. To model source capabilities, we attach to each source relation an adornment (see [Ullman, 1989], Chap. 12), specifying which binding patterns the source supports. 6 An adorn­ ment of a source relation v is a string of b's and f's of length n, where n is the arity of v. The meaning of the adornment is that the source only supports queries in which the arguments with b adornments are bound. The other arguments may be either bound or free . For ex­ ample, the adornment vhf means that the first argument must be bound in queries on v. We define an executable Horn rule as follows.

Definition 4.1: (executable Horn rule) Let V be a set of relations with binding adornment, and let r be the following Horn rule whose body relations are in V:

6 For simplicity of exposition, we assume that each source relation has a single adornment .

The rule r is executable if the following holds for i = 1, . .. , n: let j be an argument position of v; that has a b adornment, and let a be the j 'th element in X;. Then, either a is a constant, or a appears in X1 u ... u X;_1 .

A query plan includes source relations and other rela­ tions, which we model as having the all-free adornment (i.e., r, where n is the relation's arity). A query plan P is executable if for every rule r E P, r is executable.

When sources have limitations on binding patterns, it turns out that there may not be a finite maximally­ contained plan, if we restrict ourselves to plans without recursion. The following example, adapted from [Kwok and Weld, 1996], illustrates the point.

Example 4.1: Consider the following sources:

The first source stores IJCAI papers, the second is a citation database, but only accepts queries where the first argument is bound, and the third source will tell us whether a, given paper won an award. Suppose our query is to find all the award papers:

For each n, the following is an executable conjunctive query plan that is contained in q:

Furthermore, for each n, qn may produce ariswers that are not obtained by any other q;, for any i . Intuitively, a paper will be in the answer to q; if the number of links that need to be followed from an IJCAI paper is i. Therefore, there is no bound on the size of the conjunc­ tive queries in the maximally-contained plan.

We now show that by allowing recursive plans we can produce a maximally-contained plan. On our example, the construction will yield the following query plan. The construction is based on im;enting a new recursively­ defined relation, papers, whose extension will be the set of all papers that can be reached from the papers in v1 .

We now describe the construction for a given set of adorned source relations V and a query q. The recur­ sive plan includes a unary relation dom whose intended extension is the set of all constants that appear in the query or in the source descriptions, or that can be ob­ tained by iteratively querying the sources. The rules involving dom are the following .

Definition 4.2: (domain rules) Let v E V be a source relation of arity n. Suppose the adornment of v says that the arguments in positions 1, ... , I need to be bound, and the arguments I + 1, .. . , n can be free. Then for i =I+ 1, ... , n , the following rule is a domain rule:

Also,., if c is a constant appearing in the source descrip­ tions in V or in query q, then the fact dom( c) is a domain rule.

We denote by domain(V, q) the set of rules described above for defining the predicate dom. Notice that all domain rules are executable, and that relation dom has adornment f. Every query plan P can be transformed to an executable query plan by inserting the literal dom(X) before subgoals g in P. that have a variable X in an ar­ gument position that is required to be bound, and X does not appear in the subgoals to the left of g in the body. The resulting query plan, denoted by pexec, is ex­ ecutable. Moreover , we can show that p exec is equivalent to P. Combining this result with the one of the previous section, we can conclude with the following theorem:

Theorem 4.1: Let :E be a set of functional dependen­ cies, V a set of conjunctive source descriptions with bind­ ing adornments, and let q be a conjunctive query over the virtual relations. Then qUchase(:E)UT Udomain(V, q)U (V- 1 )exec is maximally-contained in q relative to :E. 0

Finally, we note that the query plan can be con­ structed in time polynomial in the size of q, V and :E.

5 Conclusions

We introduced a novel approach to creating informa­ tion gathering plans, that allows for recursive plans. We have shown that recursive plans enable us to solve two open problems. We described algorithms for obtaining a maximally-contained query plan in the presence of func­ tional dependencies and in the presence of limitations on binding patterns. Our results are also of practical importance because functional dependencies and limita­ tions on binding patterns occur very frequently in infor­ mation sources in practice (e.g., the WWW).

Recursive information gathering plans have another important methodological advantage. Query plans can be constructed by describing a set of inferences that the information agent needs to make in order to ob­ tain data from its sources. We are currently extend­ ing our algorithms to deal with order predicates (e.g., ::;, <,#)and with local completeness information about the sources [Etzioni et al., 1994; Duschka, 1997].

Acknowledgements

We thank Harish Devarajan and Dan Weld for discus­ sions and comments on earlier versions of the paper.