Database Reference
In-Depth Information
9
Endnotes to Part Two
9.1 Summary
•
Without putting restrictions on schema mappings, all the key computational tasks are
undecidable in data exchange. Hence, one usually deals with the mappings in which:
1. the relationship between the source and the target schemas is specified by source-to-
target tuple generating dependencies (st-tgds), and
2. the target constraints are tuple-generating and equality-generating dependencies (tgds
and egds).
•
Even in this setting, the problem of checking whether a given source admits a solution
is undecidable. Hence, one usually imposes a further acyclicity condition on the target
constraints.
•
With this condition (called weak acyclicity), solutions - if they exist - can be constructed
in polynomial time by the chase procedure. If the chase fails, it means that there are no
solutions.
•
Solutions constructed by the chase are more general than others - they are so-called
universal solutions. There are several equivalent ways of stating that a solution is more
general than others. The result of the chase is usually referred to as the canonical uni-
versal solution.
•
There is a unique minimal universal solution, called the core. It can be constructed in
polynomial time under the weak acyclicity assumption, although the algorithm is quite
complicated. A simpler algorithm exists if target constraints contain only egds.
•
Certain answers for arbitrary conjunctive queries
Q
(or unions of conjunctive queries)
can be found if one has an arbitrary universal solution: this is done by means of answer-
ing another query, the rewriting of
Q
, over the solution.
•
Finding certain answers for arbitrary FO (relational algebra) queries is an undecidable
problem in general. But useful restrictions guaranteeing decidability, and even tractabil-
ity, can be found if one limits the amount of negation allowed in queries. In some cases,
tractable query answering extends even to fragments of Datalog.
•
Any relational calculus query that is rewritable over the core is rewritable over the canon-
ical universal solution, but not vice versa. Also, there is a simple condition that lets one
test whether a query is not rewritable over those solutions.
