Dichotomies in Ontology-Mediated Querying with the Guarded Fragment

Summary: Classifies data complexity of ontology-mediated querying for guarded-fragment ontologies, identifying large GF fragments that admit a PTIME vs coNP dichotomy (some supporting counting) and showing most BioPortal ontologies fit or are easily rewritable into them. Shows impossibility of a dichotomy for other fragments via a Ladner-style NP-intermediate construction, ties a dichotomy for full GF to the Feder–Vardi CSP conjecture, and gives positive and negative results on Datalog-rewritability and decidability of PTIME query evaluation per ontology. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1720
Venue: PODS
Year: 2017
Pagerank: 4.1945683e-05
Overall Rank: 11,763 | 18.17%
DOI: 10.1145/3034786.3056108

Incoming Non-self Citations Over Time

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

Authors

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
698	The Chase Revisited	2008	PODS	0.00018030148
1,490	On the Decidability of Query Containment under Constraints	1998	PODS	0.00011699154
2,243	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS	9.2166927e-05
2,857	A Dichotomy in the Complexity of Deletion Propagation with Functional Dependencies	2012	PODS	8.0037703e-05
3,042	Dichotomies in the Complexity of Preferred Repairs	2015	PODS	7.669374e-05
4,361	The Complexity of Resilience and Responsibility for Self-Join-Free Conjunctive Queries	2016	VLDB	6.2559141e-05
4,553	View-Based Query Containment	2003	PODS	6.091702e-05
6,143	Ontology-based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP	2013	PODS	5.1889914e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,598	Polynomial-time program transformations in deductive databases	1990	PODS	4.7004867e-05
12,934	Complexity of Query Processing in Databases with OR-Objects	1989	PODS	4.1945683e-05
8,249	Optimizing Query Answering under Ontological Constraints	2011	VLDB	4.5508077e-05
4,298	Well-Founded Semantics for Extended Datalog and Ontological Reasoning	2013	PODS	6.2885419e-05
4,048	On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates	1998	PODS	6.4968603e-05
581	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS	0.00019767772
11,761	The Complexity of Ontology-Based Data Access with OWL 2 QL and Bounded Treewidth Queries	2017	PODS	4.1945683e-05
8,995	Efficiently Enumerating Answers to Ontology-Mediated Queries	2022	PODS	4.412512e-05
6,143	Ontology-based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP	2013	PODS	5.1889914e-05
11,556	The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs	2020	PODS	4.1945683e-05