Testability of Homomorphism Inadmissibility: Property Testing Meets Database Theory

Summary: Apply property testing to homomorphism inadmissibility for conjunctive queries: with constant queries and one-sided error, distinguish A→B from B that is far (needs deleting a constant fraction of tuples) from admitting a homomorphism. Main result: constant-query one-sided testability iff core(A) is α-acyclic; injective variant also testable for α-acyclic A, subsuming subgraph-freeness results. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1773
Venue: PODS
Year: 2019
Pagerank: 5.093636e-05
Overall Rank: 11,832 | 18.83%
DOI: 10.1145/3294052.3319679

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Hubie Chen (Birkbeck, University of London)
2. Yuichi Yoshida (National Institute of Informatics)

BibTeX Citation

@inproceedings{chen_pods19,
        address = {New York, NY, USA},
        series = {{PODS} '19},
        title = {{Testability of Homomorphism Inadmissibility: Property Testing Meets Database Theory}},
        url = {https://dl.acm.org/doi/10.1145/3294052.3319679},
        doi = {10.1145/3294052.3319679},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Chen, Hubie and Yoshida, Yuichi},
        year = {2019}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
309	Optimization of Real Conjunctive Queries	1993	PODS	0.00021768596
414	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00018893507
12,229	The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity	2013	PODS	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,166	Classification of Annotation Semirings over Query Containment	2012	PODS
2	382	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS
3	1,467	The Complexity of Evaluating Relational Queries	1983	PODS
4	5,113	Test Data for Relational Queries (Extended abstract)	1986	PODS
5	33	Consistent Query Answers in Inconsistent Databases	1999	PODS
6	7,706	Conjunctive Queries on Probabilistic Graphs: Combined Complexity	2017	PODS
7	13,199	Adaptive Predicate Managers in Database Systems	1986	VLDB
8	7,214	Schema Mappings for Data Graphs	2017	PODS
9	9,483	Local Transformations and Conjunctive-Query Equivalence	2012	PODS
10	4,184	On Preservation under Homomorphisms and Unions of Conjunctive Queries	2004	PODS