four properties are the only properties one needs to use
in reasoning about schema mappings specified by LAV
dependencies. On the computational side, the complex-ity-theoretic results in Section 5 quantify in precise terms
the difficulty of determining whether a schema mapping
specified in one language can also be specified in a different language.
There has also been an extensive study of schema mappings specified using languages richer than the language
of s-t tgds. Consider, for instance, schema mappings
specified by s-t tgds and target tgds, which were studied
in Fagin et al.,
7 or schema mappings specified by second-order tgds (SO tgds), which arise when composing schema
mappings specified by s-t tgds.
9 These languages are
known to be strictly more expressive than the language of
s-t tgds. Our results then predict that these languages lack
at least one of the structural properties considered here.
Indeed, schema mappings specified by s-t tgds and target
tgds are closed under target homomorphisms and admit
universal solutions, but need not allow for conjunctive
query rewriting. Likewise, schema mappings specified by
SO tgds admit universal solutions and allow for conjunctive query rewriting, but need not be closed under target
homomorphisms. It remains an open problem to establish structural characterizations for such richer languages
of dependencies. A particularly interesting question is
whether there is a natural way to characterize weakly acyclic sets of target tgds,
7 a class of target dependencies that
is of central importance in data exchange, as they guarantee termination of the chase procedure within a polynomial number of steps.
Among the properties of schema mappings considered
here, closure under target homomorphisms, admitting
universal solutions, and allowing for conjunctive query
rewriting are arguably the most fundamental ones for data
exchange and data integration. Proposition 4. 4 tells that
there are schema mappings satisfying these properties that
cannot be defined by any finite set of s-t tgds. Is there a natural extension of the language of s-t tgds that is characterized
by these three properties? In order to express transformations involving grouping and data merging, a proper extension of the language of s-t tgds, called nested s-t tgds, was
proposed in Fuxman et al.
11 In the previous version of this
17 we showed that schema mappings specified by a
finite set of nested s-t tgds are closed under target homomorphisms, admit universal solutions, allow for conjunctive
query rewriting (but may not be n-modular for any n > 0). It
is an open problem to determine whether all schema mappings satisfying these properties can be defined by nested
1. abiteboul, s., duschka, o.M.
Complexity of answering queries
using materialized views. In
ACM Symposium on Principles of
Database Systems (PODS) (1998)
2. avigad, J., dean, e., Mumma,
J. a formal system for euclid’s
elements. Rev. Symb. Logic (2009).
3. bernstein, P.a., Haas, l. M.
Information integration in the
enterprise. Commun. ACM 51, 9
4. Codd, e.F. a relational model for large
shared data banks. Commun. ACM 13
5. Codd, e.F. relational completeness
of data base sublanguages. Database
Systems. r. rustin, ed. Prentice-Hall,
6. duschka, o.M., Genesereth, M.r.
answering recursive queries using
views. ACM Symposium on Principles
of Database Systems (PODS) (1997),
7. Fagin, r., Kolaitis, P.G., Miller, r. J.,
Popa, l. data exchange: semantics
and query answering. Theor. Comp.
Sci. 336, 1 (2005), 89–124.
8. Fagin, r., Kolaitis, P.G., Popa, l. data
exchange: getting to the core. ACM
Trans. Database Syst. 30, 1 (2005),
9. Fagin, r., Kolaitis, P.G., Popa, l.,
tan, W.-C. Composing schema
dependencies to the rescue. ACM
Trans. Database Syst. 30, 4 (2005),
10. Fagin r., Vardi, M.y. the theory
of data dependencies—a survey.
Mathematics of Information
Processing, volume 34 of Proceedings
of Symposia in Applied Mathematics,
american Mathematical society,
11. Fuxman, a., Hernandez, M.a., Ho, H.,
Miller, r.J., Papotti, P., Popa, l. nested
mappings: schema mapping reloaded.
International Conference on Very
Large Data Bases (VLDB) (2006),
12. Haas, l. M. beauty and the
beast: the theory and practice
of information integration.
International Conference on
Database Theory (ICDT) (2007),
13. Haas, l.M., Hernández, M.a.,
Ho, H., Popa, l., roth, M. Clio
grows up: from research prototype
to industrial t. ACM International
Conference on Management
of Data (SIGMOD) (2005),
14. Kolaitis, P.G. schema mappings,
data exchange, and metadata
management. ACM Symposium
on Principles of Database Systems
(PODS) (2005), 61–75.
15. lenzerini, M. data integration:
a theoretical perspective. ACM
Symposium on Principles of
Database Systems (PODS) (2002),
16. rossman, b. existential
positive types and preservation
Symposium on Logic in
Computer Science (LICS) (2005),
17. ten Cate, b., Kolaitis, P. G.
structural characterizations of
International Conference on
Database Theory (ICDT) (2009),
18. trakhtenbrot, b. Impossibility of
an algorithm for the decision
problem on finite classes. Dokl.
Akad. Nauk. SSSR, 70 (1950),
19. van der Meyden, r. logical
approaches to incomplete
information: a survey. Logics for
Databases and Information Systems.
Kluwer, 1998, 307–356.
Balder ten Cate ( email@example.com),
InrIa and ens Cachan.
Phokion G. Kolaitis ( firstname.lastname@example.org),
university of California, santa Cruz and
Research on this paper was partially supported by NSF
grants IIS-0430994 and ARRA 0905276, the Netherlands
Organization for Scientific Research (NWO) grant
639.021.508, and the ERC Advanced Grant Webdam on
Foundations of Web data management. Part of the work was
carried out during a visit by Balder ten Cate at UC Santa Cruz
and the IBM Almaden Research Center.