Consistency of schema mappings - Foundations of Data Exchange - page 242

K ∃ = f ( K ), which only uses data values from C and nulls (not more than k of them). It is
easy to check that f ( S ) is a solution of T .
Now, assume that there is no K ∃ that provides a solution for each tree agreeing with K ∀ .
Then there exists a tree agreeing with K ∀ for which there is no solution at all, contradict-
ing absolute consistency. To see this, reason as follows. For each possible response K to
K ∀ ,let S K beatreeagreeingwith K ∀ for which there is no solution agreeing with K .By
Lemma 12.24 there is a tree S ( a , b ) whenever one of the T K 's

satisfies π( a , b ) for every source side pattern π . That means that no K ∃ provides a solution
for S , which contradicts the previously proved claim.

∈ L ( K ∀ ) such that S | = π

Precise complexity
We presented the algorithm solving A B C ONS as a two-round game between ,in

which moves are made by the choice of an object of size exponential during the first round
and polynomial during the second round, and the winning condition is a polynomial-time
property of these objects.
The second round of the game can be eliminated. Since the played objects are polyno-
mial (in the size of the input), a strategy is an exponential object: it maps each object that
can be played by

∀ and ∃

can
simply extend the object played in the first round with a winning strategy for the second
round.
This means that the algorithm can be viewed as a single round game in which

∀ to an answer of ∃ . Thus, instead of playing the second round, ∃

∃
play exponential-size objects and the winning condition is a polynomial-time property of
these objects.
The class of problems that can be solved by such algorithms is denoted by

∀ and

Π 2 E XP .

It is easy to see that

N EXPTIME ⊆ Π 2 E XP ⊆ E XPSPACE .

We argued the second inclusion informally in the proof of Theorem 18.8 . To justify the first
inclusion, observe that a N EXPTIME algorithm can be seen as a game in which the rules tell
∀ is supposed to play the whole accepting computation

of the algorithm as a single object (it does have single-exponential size).
A B C ONS happens to be complete for

to play some trivial object, and ∃

Π 2 E XP . To show this we provide a reduction from

the following Π 2 E XP -complete problem:

P ROBLEM : n - UNIVERSALITY
I NPUT : Nondeterministic Turing machine M ,
number n in unary
Q UESTION : D s M accept every word of length 2 n
in at most 2 n steps?

We give a reduction from 2 n - UNIVERSALITY to A B C ONS for a very restricted class of
mappings.