Database Reference
In-Depth Information
Combined complexity
Until now, the complexity analysis of the problemof checking for the existence of solutions
has been carried out under the assumption that the mapping is fixed. In other words, we
looked at the
data complexity
of the problem. However, while data complexity makes sense
in a lot of data exchange scenarios, a more refined complexity analysis should consider both
source instances and mappings as the input. This corresponds to the combined complexity
of the problem, which we study next.
PROBLEM
:
OL
E
XISTENCE
.
INPUT:
M
=(R
s
,
R
t
,
st
,
A relational mapping
Σ
Σ
t
) and a
source instance
S
.
QUESTION
: Does there exist a solution for
S
under
M
?
We study this problem for the class of mappings
M
=(R
s
,
R
t
,
Σ
st
,
Σ
t
) such that
Σ
t
consists of a set of egds and a weakly-acyclic set of tgds. This is because for them, as we
know, the existence of solutions problem is decidable (indeed, even if
M
is not considered
to be fixed).
Let
M
=(R
s
,
R
t
,
Σ
st
,
Σ
t
) be a mapping such that Σ
t
consists of a set of edgs and a weakly
acyclic set of tgds. A close inspection of the proof of
Theorem 5.11
shows that the length
of every chase sequence for a source instance
S
under
)
.This
provides us with an E
XPTIME
(exponential time) upper bound for the combined complexity
of the problem of existence of solutions. Furthermore, this bound is tight even for restricted
classes of mappings.
O
(
M
M
is bounded by
S
Theorem 5.15
The problem
S
OL
E
XISTENCE
is
E
XPTIME
-complete, if restricted to the
class of mappings
M
=(R
s
,
R
t
,
Σ
st
,
Σ
t
)
such that
Σ
t
consists of a set of egds and a weakly
acyclicsetoftgds.
Moreover, the problem remains
E
XPTIME
-hard even if restricted to the class of mappings
such that
Σ
st
consists of a set of full st-tgds and
Σ
t
consists of a set of egds and a set of full
tgds.
Proof
We only prove the lower bound, since we already sketched the proof of the upper
bound. We provide a reduction from the complement of the problem of checking whether
a fact
R
(
c
1
,...,
c
k
) belongs to the evaluation of a D
ATALOG
program
over an instance
S
, which is known to be E
XPTIME
-hard. (The reader not familiar with datalog can find the
definition of D
ATALOG
in
Section 7.4
.)
Basedonthefact
R
(
c
1
,...,
c
k
), the program
Π
Π
, and the instance
S
, we construct a map-
Σ
t
) and a source instance
S
as follows:
ping
M
=(R
s
,
R
t
,
Σ
st
,
•
R
s
consists of all the extensional and intensional relation symbols
U
1
,...,
U
m
mentioned
in
Π
, plus a new symbol
W
of arity
k
+1;
R
t
is a copy of R
s
.Thatis,R
t
consists of relation symbols
U
1
,...,
U
m
and
W
,wherethe
arities are the same as in R
s
;
•
