Database Reference
In-Depth Information
returns mappings that are specified by dependencies that extend st-tgds with disjunctions
in the right-hand side. Unfortunately, these types of mappings are difficult to use in the
data exchange context. In particular, it is not clear whether the standard chase procedure
could be used to produce a single canonical target database in this case, thus making the
process of exchanging data and answering target queries much more complicated. Second,
the output mapping of M AXIMUM R ECOVERY can be of exponential size in the size of
the input mapping. Thus, a natural question at this point is whether simpler and smaller
inverse mappings can be computed. In the rest of this section, we show an effort to lower
the complexity in a restricted case, and we briefly study what are the languages needed to
express inverses, quasi-inverses and maximum recoveries.
Recall that a st-tgd is called full if it does not include any existential quantifiers in its
right-hand side. Full st-tgds have been widely used in practice, and extensively studied in
the data integration and exchange contexts. For this reason, the issue of computing inverses
for the class of mappings specified by full st-tgds is considered to be a fundamental prob-
lem. Interestingly, next we show a modification of the algorithm M AXIMUM R ECOVERY
that works in quadratic time and computes maximum recoveries for this type of mapping.
It is important to notice that we assume in this procedure, without loss of generality, that
every full st-tgd has a single atom in its right-hand side. Besides, given tuples of vari-
ables x =( x 1 ,..., x k ) and y =( y 1 ,..., y k ), we use the notation x = y as a shorthand for
x 1 = y 1 ∧···∧
x k = y k .
Algorithm 20.2 M AXIMUM R ECOVERY F ULL
Require:
M 12 =(R 1 , R 2 ,
Σ
) with
Σ
a finite set of full st-tgds, and each dependency in
Σ
having a single atom in its right-hand side
Ensure:
M 21 =(R 2 , R 1 ,
Γ
) is a maximum recovery of
M
:= 0
2: for all predicate symbol P
Γ
1:
R 1 do
let u be a fresh tuple of pairwise distinct variables containing as many variables as
the arity of P
3:
Δ
:= 0
4:
for all
ϕ
( x )
P ( x ) in
Σ
do
5:
Δ ∪{∃
}
Δ
:=
x (
ϕ
( x )
x = u )
6:
end for
7:
let
α
( u ) be the disjunction of all the elements in
Δ
8:
Γ
:=
Γ ∪{
P ( u )
α
( u )
}
9:
10: end for
Theorem 20.35
Algorithm M AXIMUM R ECOVERY F ULL runs in quadratic time, and on
input M
) ,where Σ is a finite set of full st-tgds with each dependency in it
having a single atom in its right-hand side, it computes a maximum recovery of M .
=(R 1 , R 2 ,
Σ
AlgorithmM AXIMUM R ECOVERY F ULL can be considered as a specialization of algorithm
Search WWH ::




Custom Search