LIPIcs.ICDT.2015.161.pdf
- Filesize: 481 kB
- 16 pages
Document
The Product Homomorphism Problem and Applications
Authors
-
Part of:
Volume:
18th International Conference on Database Theory (ICDT 2015)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Database Theory (ICDT) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2015-03-19
Cite As Get BibTex
Balder ten Cate and Victor Dalmau. The Product Homomorphism Problem and Applications. In 18th International Conference on Database Theory (ICDT 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 31, pp. 161-176, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.ICDT.2015.161
Abstract
The product homomorphism problem (PHP) takes as input a finite collection of structures A_1, ..., A_n and a structure B, and asks if there is a homomorphism from the direct product between A_1, A_2, ..., and A_n, to B. We pinpoint the computational complexity of this problem. Our motivation stems from the fact that PHP naturally arises in different areas of database theory. In particular, it is equivalent to the problem of determining whether a relation is definable by a conjunctive query, and the existence of a schema mapping that fits a given collection of positive and negative data examples. We apply our results to obtain complexity bounds for these problems.
Subject Classification
Keywords
- Homomorphisms
- Direct Product
- Data Examples
- Definability
- Conjunctive Queries
- Schema Mappings
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Bogdan Alexe, Balder ten Cate, Phokion G. Kolaitis, and Wang-Chiew Tan. Designing and refining schema mappings via data examples. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of data, SIGMOD '11, pages 133-144, New York, NY, USA, 2011. ACM.
-
Timos Antonopoulos, Frank Neven, and Frédéric Servais. Definability problems for graph query languages. In Proceedings of the 16th International Conference on Database Theory, ICDT '13, pages 141-152, New York, NY, USA, 2013. ACM.
-
F. Banchilon. On the completeness of query languages for relational databases. In Proceedings of MFCS, pages 112-123, 1978.
-
Egon Börger, Erich Grädel, and Yuri Gurevich. The Classical Decision Problem. Perspectives in Mathematical Logic. Springer, 1997.
-
Nadia Creignou, Phokion G. Kolaitis, and Bruno Zanuttini. Structure identification of boolean relations and plain bases for co-clones. J. Comput. Syst. Sci., 74(7):1103-1115, 2008.
-
Victor Dalmau. Computational Complexity of Problems over Generalized Formulas. PhD thesis, Universitat Politècnica de Catalunya, 2000.
-
Rina Dechter and Judea Pearl. Structure identification in relational data. Artif. Intell., 58(1-3):237-270, 1992.
-
Ronald Fagin, Phokion G. Kolaitis, Renée J. Miller, and Lucian Popa. Data exchange: semantics and query answering. Theoretical Computer Science, 336(1):89 - 124, 2005. Database Theory.
-
G.H.L. Fletcher, M. Gyssens, J. Paredaens, and D. Van Gucht. On the expressive power of the relational algebra on finite sets of relation pairs. Knowledge and Data Engineering, IEEE Transactions on, 21(6):939 -942, june 2009.
-
Peter Jeavons, David A. Cohen, and Marc Gyssens. How to determine the expressive power of constraints. Constraints, 4(2):113-131, 1999.
-
Phokion G. Kolaitis. Schema mappings, data exchange, and metadata management. In Proceedings of the Twenty-fourth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS '05, pages 61-75, New York, NY, USA, 2005. ACM.
-
J. Paredaens. On the expressive power of the relational algebra. Information Processing Letters, 7(2):107 - 111, 1978.
-
Ross Willard. Testing expressibility is hard. In David Cohen, editor, CP, volume 6308 of Lecture Notes in Computer Science, pages 9-23. Springer, 2010.