Database Reference
In-Depth Information
We can now characterize the CWA solutions as those CWA presolutions that satisfy
this last requirement. This finally allows us to connect the CWA solutions with a proper
intuition behind the CWA. This is done in the next theorem, which states that the following
two sets of solutions are the same:
Those that satisfy our initial semantic definition of CWA solution ( Definition 8.8 ); that
is, those universal solutions that are also homomorphic images of the canonical universal
solution; and
those that satisfy requirements (A1)-(A2)-(A3), which properly capture the intuition
behind the CWA.
Theorem 8.13
Let
M
=(R s , R t ,
Σ st ) be a mapping and S a source instance. Then
S OL CWA
M
( S ) is the set of CWA presolutions for S under
M
that satisfy the requirement
(A3) formalized above.
Proof Assume first that a target instance T belongs to S OL CWA
M
( S ).Weprovedin Propo-
sition 8.12 that T is a CWA presolution. We prove next that it also satisfies (A3). Indeed,
let Q be a statement over
(that is, a Boolean conjunctive query over R t ) that holds in
T . Also, let T be an arbitrary solution for S . We show that Q holds in T . Indeed, since
T S OL CWA
M
M
( S ), it is by definition a universal solution for S . Thus, there exists a homo-
morphism h : T T . But conjunctive queries are preserved under homomorphisms, and
hence Q holds in T .
Assume, on the other hand, that T is a CWA presolution for S that satisfies (A3). We
prove first that T is a universal solution for S under
M
. Take the Boolean conjunctive
= Q T , and hence T |
query Q T that has T as its tableaux. Clearly, T
|
= Q T for each solution
T for S under
(because T satisfies (A3)). But the latter holds if and only if there exists
a homomorphism h : T
M
T . This shows that T has homomorphisms into every possible
solution, and, therefore, that T is a universal solution for S .
We prove next that T is a homomorphic image of the canonical universal solution T can
for S under
.Since T is a CWA presolution, it is the case that T = j ∈J
M
M B α ( j ) for
S
S
M
some assignment
V AR . Recall that T can is also a CWA presolution,
and that this is witnessed by some assignment
α
:
K
C ONST
S
K
M
α
can :
C ONST
V AR that sends each
S
M
pair ( j , z ) in
K
into a distinct null value. But then it is not hard to see that T is the
homomorphic image of T can under homomorphism h defined as follows. Let
be a null
S
M
value in D OM ( T can ).Then
=
α can ( j , z ), for some pair ( j , z )
∈K
.Weset h (
) to be
α
( j , z ).
Query answering under CWA
Under both the usual certain answers and the universal certain answers semantics, we apply
queries Q to solutions as if solutions were ordinary relational instances without nulls. More
precisely, we treated nulls as ordinary database values. As we have mentioned earlier, this
corresponds to the naıve evaluation of queries, which leads to a naıve semantics. But the
dangers of treating nulls in this way have been known for a long time. The key drawback of
Search WWH ::




Custom Search