Databases Reference
In-Depth Information
We can apply existing technology in solving the OPT optimization problem.
Although finding maximum-entropy solutions in general is costly, the experiments
described in
Sarma et al.
(
2008
) show that the execution time is reasonable for a
one-time process.
3.5
Broader Classes of Mappings
In this section, we describe several practical extensions to the basic mapping lan-
guage. The query answering techniques and complexity results we have described
carry over to these techniques.
GLAV mappings:
The common formalism for schema mappings, GLAV (a.k.a.
tuple-generating dependencies), is based on expressions of the form
m
W8
x
.'.
x
/
!9
y
.
x
;
y
//:
S,and is the body of a
In the expression, ' is the body of a conjunctive query over
T . A pair of instances D
S
conjunctive query over
and D
T
satisfies
a GLAV mapping
m if for every assignment of
x
in D
S
that satisfies ' there exists an assignment of
y
in D
T
that satisfies .
We d e fi n e
general p-mappings
to be triples of the form
pGM
D
. S; T;
gm
/,
where
gm
is a set
, such that for each i
2
Œ1;n, gm
i
is a general GLAV mapping. The definition of by-table semantics for such mappings
is a simple generalization of Definition
6
, and query answering can be conducted in
PTIME. Extending by-tuple semantics to arbitrary GLAV mappings is much trickier
than by-table semantics and would involve considering mapping sequences whose
length is the product of the number of tuples in each source table, and the results are
much less intuitive.
Theorem 4.
Let pGM be a general p-mapping between a source schema
S
and a
target schema
T
.Let
D
S
be an instance of
S
.Let
Q
be an SPJ query with only
equality conditions over
T
. The problem of computing
Q
table
.D
S
/
with respect to
pGM is in PTIME in the size of the data and the mapping.
f
.gm
i
;Pr.gm
i
//
j
i
2
Œ1;n
g
t
Complex mappings:
Complex mappings map a set of attributes in the source to a
set of attributes in the target. For example, we can map the attribute
address
to the
concatenation of
street
,
city
,and
state
.
Formally, a
set correspondence
between S and T is a relationship between a
subset of attributes in S and a subset of attributes in T . Here, the function associated
with the relationship specifies a single value for each of the target attributes given a
value for each of the source attributes. Again, the actual functions are irrelevant to
our discussion. A
complex mapping
is a triple .S;T;cm/,wherecm is a set of set
correspondences, such that each attribute in S or T is involved in at most one set
correspondence. A
complex p-mapping
is of the form
pCM
Df
.cm
i
;Pr.cm
i
//
j
,where
P
i
D
1
i
2
Œ1;n
g
Pr
.cm
i
/
D
1.
