Alternative semantics - Foundations of Data Exchange - page 121

On the other hand, we know from Corollary 8.19 that the problem of computing CWA
certain answers for Boolean conjunctive queries with inequalities is CO NP-hard, even in
the absence of target dependencies.

Summary
We can summarize the query answering behavior of the CWA semantics, in the presence
of target dependencies, as follows:

• Computing CWA certain answers of arbitrary relational calculus queries is an undecid-

able problem.
• Computing CWA certain answers of (unions of) conjunctive queries can be done in
polynomial time, under mappings with a weakly acyclic set of tgds, but extending this
class with inequalities immediately leads to intractability (even in the absence of target
dependencies).

8.4 Clopen-world semantics

We have seen that the closed-world semantics lets us avoid some of the problems that
arise under the open-world semantics of data exchange solutions. But is the closed-world
semantics free of problems itself? It is not, as the following example shows.
Suppose the source schema has a relation Papers(paper#,title) with the list of
papers, say submitted to a journal, so that the id of each paper and its title are recorded.
Suppose that in the target we have a relation Assignments(paper#,reviewer) , with
assignments of papers to reviewers. The natural st-tgd in this case is

Papers ( x , y )

→∃ z Assignments ( x , z ) .

But now assume that paper# is a key for S , and consider the target query asking whether
every paper has exactly one reviewer. Under the CWA semantics, the certain answer
to this query is true . This is because of the minimalistic CWA, which creates just one
(paper#,reviewer) tuple for each paper id.
This is clearly unsatisfactory, but it also suggests that some attributes in a mapping may
correspond to the CWA, while others correspond to the OWA. In the case of the reviewer
attribute, it is clear that the intention is not to limit it to having a single value for each paper.
We capture this intuition by annotating variables in the target part of the mapping with
cl or op , depending on whether they correspond to the closed- or open-world semantics.
For instance, in the above example, we shall use an annotated st-tgd:

z Assignments ( x cl , z op )

Papers ( x , y )

→∃

saying that for each submitted paper, several tuples can be created in the target: they will
all have the same paper id, since x is annotated as cl , but reviewer names can be different,
since z is annotated as op .