Step 1: the algorithm
transforms every equality description into two inclusion mappings. It then
transforms every inclusion description of the form Q1
Ê Q2 into the pair:
V Ê Q2, and V : − Q1,
where V is a new predicate name that appears nowhere else in the peer mappings.
Step 2: The algorithm builds a rule-goal tree T . When a node n in T is a goal node, it has a label l(n) which is an atom whose arguments are variables or constants. The label l(n) of a rule node is a peer description (except that the child of the root is labeled with the rule defining the query). Finally, a rule node n that is labeled with an inclusion description also has a label unc(n): this label always includes at least the father of n, but may also include nodes that are siblings of its father goal node. As described earlier, the reason for this label is that an MCD can cover more that the subgoal for which it was created. The root of T is labeled with the atom Q(X) , and it has a single rule-node child whose children are the subgoals of the query.
The tree is constructed by iterating the
following step, until no leaf nodes can be expanded further.
Choose an arbitrary leaf goal node n in T whose label is l(n) = p(Y),
and p is not a stored relation. Perform all the expansions possible in
the following two cases. In either case, never expand a goal node n with a
peer description that was used on the path from the root to n. This
guarantees termination of the algorithm even in a cyclic PDMS.
1. Definitional expansion: this is the case where peer relations appear in GAV-style mappings. If p appears in the head of a definitional description r, expand n with the definition of p. Specifically, let r be the result of unifying p( Y ) with the head of r. Create a child rule nr, with l(nr) = r , and create one child goal-node for nr for every subgoal of r with the corresponding label. Existential variables in r should be renamed so they are fresh variables that do not occur anywhere else in the tree constructed thus far.
2.
Inclusion expansion: this is the case where peer relations appear in LAV-style
mappings. If p appears in the right-hand side of an inclusion description or
storage description r of the form V Ê
Q1 (or V = Q1), we do the following. Let n1, . . . , nm be
the children of the father node of n, and p1, . . . , pm
be their corresponding labels. Create an MCD for p(Y)
w.r.t. p1, . . . , pm and the description r. Recall that
the MCD contains an atom of the form V (Z)
and the set of atoms in p1, . , pm that it covers.
Create a child rule node nr for n labeled with r, and a child
goal node ng for nr labeled with V (Z).
Set unc(ng) to be the set of subgoals covered by the MCD.
Repeat this process for every MCD that can be created for p(Y)
w.r.t. p1, . , pm and the description r.
Step 3: we construct the solutions from T . The solution is a union of
conjunctive queries over the stored relations. Each of these conjunctive
queries represents one way of obtaining answers to the query from the relations
stored at peers. Each of them may yield different answers unless we know
that some sources are replicas of others. Let us consider the simple case, where
only definitional
mappings are used, first. The answer would be the union of
conjunctive queries, each with head Q( X) and a body that can be
constructed as follows. Let T' be a subset of T where we arbitrarily
choose a single child at every goal node, and for which all leaves are labeled
by stored relations. The body of a conjunctive query is the conjunction of all
the leaves of T' .
To accommodate inclusion expansions as well, we create the conjunctive queries as follows. In creating T's we still choose a single child for every goal node. This time, we do not necessarily have to choose all the children of a rule node n. Instead, given a rule node n, we need to choose a subset of the children n1, . . . , nl of n, such that unc(n1) .È . . È unc(nl) includes all of the children of n.