License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2015.161
URN: urn:nbn:de:0030-drops-49832
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/4983/
Go to the corresponding LIPIcs Volume Portal

ten Cate, Balder ; Dalmau, Victor

The Product Homomorphism Problem and Applications

pdf-format:
10.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{tencate_et_al:LIPIcs:2015:4983,
  author =	{Balder ten Cate and Victor Dalmau},
  title =	{{The Product Homomorphism Problem and Applications}},
  booktitle =	{18th International Conference on Database Theory (ICDT 2015)},
  pages =	{161--176},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-79-8},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{31},
  editor =	{Marcelo Arenas and Mart{\'i}n Ugarte},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/4983},
  URN =		{urn:nbn:de:0030-drops-49832},
  doi =		{10.4230/LIPIcs.ICDT.2015.161},
  annote =	{Keywords: Homomorphisms, Direct Product, Data Examples, Definability, Conjunctive Queries, Schema Mappings}
}

Keywords: Homomorphisms, Direct Product, Data Examples, Definability, Conjunctive Queries, Schema Mappings
Collection: 18th International Conference on Database Theory (ICDT 2015)
Issue Date: 2015
Date of publication: 19.03.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI