Database Reference
In-Depth Information
9.2 Bibliographic comments
The basics of data exchange were described by
Fagin et al.
(
2005a
). That paper presented
the notions of schema mappings as we use them, adapted the chase procedure to the data
exchange setting, and introduced universal solutions (using the definition based on homo-
morphisms). The choice of schema mappings one normally considers in data exchange
was justified by
ten Cate and Kolaitis
(
2009
). Complexity of the key tasks associated with
data exchange, such as the existence of (universal) solutions, was studied by
Kolaitis et al.
(
2006
).
The central notion of weak acyclicity was first formulated by Deutsch and Popa, and later
independently used by
Fagin et al.
(
2005a
), and
Deutsch and Tannen
(
2003
). Given the role
of chase in data exchange, finding conditions for its termination is an active research topic.
Recent results show that chase can be pushed beyond weak acyclicity (
Deutsch et al.
,
2008
;
Marnette
,
2009
;
Meier et al.
,
2009
).
The notion of core originates in graph theory (
Hell and Nesetril
,
1992
). Its usefulness
in data exchange was shown by
Fagin et al.
(
2005c
), who gave the simple algorithm for
computing cores. The polynomial-time algorithm for the general case was developed by
Gottlob and Nash
(
2008
).
The algorithm for answering conjunctive queries based on naıve evaluation (
Imieli nski
and Lipski
,
1984
)wasgivenby
Fagin et al.
(
2005a
). It was already shown by
Fagin et al.
(
2005a
) that the extension of the algorithm for all of FO is impossible. In the case of
unions of conjunctive queries with inequalities, they showed that finding certain answers
remains tractable with one inequality per disjunct; however,
M¸dry
(
2005
) showed that
with two inequalities per disjunct, query answering becomes
CO
NP-complete. Extensions
to Datalog with predicates for constant and inequalities are by
Arenas et al.
(
2011c
).
The notions of rewritings over the core and the canonical universal solution were studied
by
Fagin et al.
(
2005a
,
c
). The result showing the exact relationship between them is by
Arenas et al.
(
2013
). The notion of being locally source-dependent, and its applications in
proving that some queries are not rewritable, comes from the work of
Arenas et al.
(
2013
)
as well. An alternative notion of locality for schema mappings based on conjunctive queries
was studied by
Fagin and Kolaitis
(
2012
).
It was also shown by
Arenas et al.
(
2013
) that query answering in data exchange may
exhibit unnatural behavior. It was argued by
Libkin
(
2006a
) that this is due to the openness
of solutions to adding new facts. The closed world semantics was proposed in that paper too
and later extended to schemas with target constraints by
Hernich and Schweikardt
(
2007
);
these semantics avoid some of the unwanted behavior noticed by
Arenas et al.
(
2013
). A
combined account of the closed world semantics is given by
Hernich et al.
(
2011
), who
also presented a version of chase that led to easy proofs of some older results by
Deutsch
et al.
(
2008
). The clopen semantics was proposed by
Libkin and Sirangelo
(
2011
); further
extensions are given by
Afrati and Kolaitis
(
2008
), who considered aggregate queries in a
data exchange scenario, and
Hernich
(
2011
), who dealt with a relaxed version of closed-
world semantics.
