文章基本信息

标题：The Product Homomorphism Problem and Applications
本地全文：下载
作者：Balder ten Cate ; Victor Dalmau
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2015
卷号：31
页码：161-176
DOI：10.4230/LIPIcs.ICDT.2015.161
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Homomorphisms; Direct Product; Data Examples; Definability; Conjunctive Queries; Schema Mappings