M. Stockmeyer, M. Bertossi, L. , C. , and J. , Let ? = ? 1 x 1 . . . ? n x n ?(x 1 . . . x n ) be an instance of REFERENCES Arenas Consistent query answers in inconsistent databases, Proceedings of PODS, 1973.

C. Beeri, R. Fagin, D. Maier, A. Mendelzon, J. Ullman et al., Properties of acyclic database schemes, Proceedings of the thirteenth annual ACM symposium on Theory of computing , STOC '81, 1981.
DOI : 10.1145/800076.802489

P. Bernstein, Applying model management to classical meta data, Proceedings of CIDR, 2003.

P. A. Bernstein and D. W. Chiu, Using Semi-Joins to Solve Relational Queries, Journal of the ACM, vol.28, issue.1, pp.25-40, 1981.
DOI : 10.1145/322234.322238

A. K. Chandra and P. M. Merlin, Optimal implementation of conjunctive queries in relational data bases, Proceedings of the ninth annual ACM symposium on Theory of computing , STOC '77, 1977.
DOI : 10.1145/800105.803397

V. Crescenzi, G. Mecca, and P. Merialdo, RoadRunner, Proceedings of the 2002 ACM SIGMOD international conference on Management of data , SIGMOD '02, 2001.
DOI : 10.1145/564691.564778

D. Paola and R. A. , The Recursive Unsolvability of the Decision Problem for the Class of Definite Formulas, Journal of the ACM, vol.16, issue.2, pp.324-327, 1969.
DOI : 10.1145/321510.321524

R. Diestel, Graph Theory, 2005.

R. Fagin, P. G. Kolaitis, R. J. Miller, and L. Popa, Data exchange: Semantics and query answering, Proceedings of ICDT, 2003.
DOI : 10.1016/j.tcs.2004.10.033
URL : http://doi.org/10.1016/j.tcs.2004.10.033

R. Fagin, P. G. Kolaitis, L. Popa, and W. C. Tan, Quasi-inverses of schema mapping, Proceedings of PODS, 2007.

R. Fagin, P. G. Kolaitis, W. Tan, and L. Popa, Composing schema mappings: Second-order dependencies to the rescue, Proceedings of PODS, 2004.

G. H. Fletcher, On the data mapping problem, 2007.

M. R. Garey and D. S. Johnson, Computers And Intractability. A Guide to the Theory of NP-completeness, 1979.

G. Gottlob, N. Leone, and F. Scarcello, On the complexity of some inductive logic programming problems, Proceedings of ILP, 1997.

G. Gottlob, N. Leone, and F. Scarcello, Hypertree decompositions and tractable queries, Proceedings of PODS, 1999.
DOI : 10.1145/303976.303979
URL : http://arxiv.org/abs/cs/9812022

L. M. Haas, M. A. Hernández, H. Ho, L. Popa, R. et al., Clio grows up, Proceedings of the 2005 ACM SIGMOD international conference on Management of data , SIGMOD '05, pp.805-810, 2005.
DOI : 10.1145/1066157.1066252

L. Ilie, R. Solis-oba, Y. , and S. , Reducing the Size of NFAs by Using Equivalences and Preorders, Combinatorial Pattern Matching, 2002.
DOI : 10.1007/11496656_27

P. G. Kolaitis, Schema mappings, data exchange, and metadata management, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems , PODS '05, 2005.
DOI : 10.1145/1065167.1065176
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.102.3663

D. K?nig, Theorie der endlichen und unendlichen Graphen, 1936.

N. Lavra? and S. D?eroski, Inductive Logic Programming: Techniques and Applications, 1994.
DOI : 10.1007/3-540-63514-9

M. Lenzerini, Data integration, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems , PODS '02, 2002.
DOI : 10.1145/543613.543644

M. Li and P. Vitányi, An Introduction to Kolmogorov Complexity and Its Applications, second ed, 1997.

C. H. Papadimitriou, Computational Complexity, 1994.

E. Rahm and P. A. Bernstein, A survey of approaches to automatic schema matching, The VLDB Journal, vol.10, issue.4, pp.334-350, 2001.
DOI : 10.1007/s007780100057

M. Schaefer and C. Umans, Completeness in the polynomial hierarchy, a compendium, SIGACT News, vol.33, issue.3, pp.32-49, 2002.

P. Senellart and G. Gottlob, On the complexity of deriving schema mappings from database instances, Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems , PODS '08, pp.23-32, 2008.
DOI : 10.1145/1376916.1376921

L. J. Stockmeyer and A. R. Meyer, Word problems requiring exponential time, Proceedings of STOC, 1973.
DOI : 10.1145/800125.804029
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.116.4618

R. E. Tarjan and M. Yannakakis, Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs, SIAM Journal on Computing, vol.13, issue.3, pp.566-579, 1984.
DOI : 10.1137/0213035

B. A. Trakhtenbrot, Impossibility of an algorithm for the decision problem in finite classes, pp.1-5, 1963.

C. Wrathall, Complete sets and the polynomial-time hierarchy, Theoretical Computer Science, vol.3, issue.1, pp.23-33, 1976.
DOI : 10.1016/0304-3975(76)90062-1

M. Yannakakis, Algorithms for acyclic database schemes, Proceedings of VLDB. VLDB Endowment, 1981.