A note on the product homomorphism problem and CQ-definability

Balder ten Cate, Víctor DalmauarXiv 2012 · arXiv

Abstract

The Product Homomorphism Problem (PHP) involves determining the existence of a homomorphism from a direct product of finite relational structures $A_1, \dots, A_n$ to a target structure $B$. While the problem is naturally contained in NExpTime, existing proofs of its NExpTime-completeness have traditionally relied on structures with unbounded arity. This paper provides a self-contained proof that PHP remains NExpTime-complete even under significant structural restrictions, such as for directed graphs or structures with bounded domain sizes. Furthermore, these results are applied to demonstrate that the Conjunctive Query (CQ) definability problem is coNExpTime-hard even for basic database schemas.

Introduction

In the study of relational structures and database theory, homomorphisms provide a fundamental framework for understanding query evaluation and constraint satisfaction. The Product Homomorphism Problem (PHP) asks whether there exists a mapping from the direct product of a collection of structures $\mathcal{A} = \{A_1, \dots, A_n\}$ to a target structure $B$ that preserves all relations.

Because the domain of the direct product $A_1 \times \dots \times A_n$ grows exponentially relative to the size of the input structures, PHP is inherently a high-complexity problem. Specifically, it is contained in NExpTime. Previous literature established its NExpTime-completeness, but these proofs utilized relations of unbounded arity—meaning the number of elements involved in a single relationship could grow with the input size. This research investigates whether the problem's hardness persists when the "complexity" of individual structures is strictly limited.

Hardness of Simple Structures

The core contribution of this work is proving that the exponential explosion of the direct product is sufficient to drive NExpTime-completeness, even when the individual components are remarkably simple.

Reduction from Exponential Tiling

The authors establish NExpTime-hardness through a reduction from the exponential tiling problem. By mapping the tiling constraints to a PHP instance where each structure $A_i$ has a domain size of only two elements (e.g., $\{0, 1\}$), they demonstrate that the interaction across the product space can simulate a $2^m \times 2^m$ grid. This proves that bounded domain size does not mitigate the problem's complexity.

Arity Reduction and Directed Graphs

A significant portion of the paper is dedicated to "arity reduction." The authors show how complex, high-arity relations can be encoded into a single binary relation (an edge in a graph). This is achieved through:

  1. Encoding Relations: Transforming multiple relations into a smaller set of relations without losing the hardness of the homomorphism problem.
  2. Gadget Construction: To prove the case for directed graphs, the authors use a gadget-based approach. Tuples of arity $r$ are represented as paths of length $r$, and "sink nodes" are introduced to ensure that any homomorphism from the product structure to the target structure preserves the intended logic.

These methods culminate in the finding that PHP is NExpTime-complete even for directed graphs (a single binary relation).

Application to CQ-Definability

The hardness results for PHP have direct implications for database theory, specifically the Conjunctive Query (CQ) definability problem (also known as the PP-definability problem). This problem asks whether a given relation can be defined by a Conjunctive Query—a standard "JOIN-SELECT-PROJECT" query—over a specific schema.

The paper establishes that CQ-definability is coNExpTime-hard even for the simplest possible database schema: a single table with two columns (a single binary relation). This improves upon earlier results that required relations of unbounded arity to prove similar hardness levels.

Conclusion

The findings of this paper suggest that the complexity of the Product Homomorphism Problem is robust against simplifications of the input structures. Whether the input consists of high-arity relations or simple directed graphs, the exponential nature of the direct product remains the dominant factor in computational difficulty.

For practitioners, these results highlight the inherent difficulty of certain meta-querying tasks in databases. For theorists, the paper identifies the "tractability frontier": PHP only becomes solvable in polynomial time when the number of relations, their arity, and the domain size are all simultaneously bounded. Future work may further refine these boundaries to identify specific subclasses of structures where the problem might be more manageable.

Summary updated

Abstract

The product homomorphism problem (PHP) takes as input a finite collection of relational structures A1, ..., An and another relational structure B, all over the same schema, and asks whether there is a homomorphism from the direct product A1 x ... x An to B. This problem is clearly solvable in non-deterministic exponential time. It follows from results in [1] that the problem is NExpTime-complete. The proof, based on a reduction from an exponential tiling problem, uses structures of bounded domain size but with relations of unbounded arity. In this note, we provide a self-contained proof of NExpTime-hardness of PHP, and we show that it holds already for directed graphs, as well as for structures of bounded arity with a bounded domain size (but without a bound on the number of relations). We also present an application to the CQ-definability problem (also known as the PP-definability problem). [1] Ross Willard. Testing expressibility is hard. In David Cohen, editor, CP, volume 6308 of Lecture Notes in Computer Science, pages 9-23. Springer, 2010.
BibTeX
@misc{cate2012note,
  author = {Balder ten Cate and Víctor Dalmau},
  title = {{A note on the product homomorphism problem and CQ-definability}},
  year = {2012},
  eprint = {1212.3534},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1212.3534},
}
Figure