Flag & Check: Data Access with Monadically Defined Queries

Summary: Introduce MODEQs and NEMODEQs, query formalisms that extend CQs, conjunctive two-way RPQs and monadic Datalog, expressible in Datalog/MSO but crucially enjoying decidable query containment. They have P data complexity, combined complexity NP (MODEQs)/PSPACE (NEMODEQs), and preserve decidable answering under broad classes of TGDs via (partial) rewriting techniques. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1609
Venue: PODS
Year: 2013
Pagerank: 5.6242786e-05
Overall Rank: 7,411 | 49.16%
DOI: 10.1145/2463664.2465227

Incoming Non-self Citations Over Time

Authors

1. Sebastian Rudolph (Technical University of Dresden)
2. Markus Krötzsch (University of Oxford)

BibTeX Citation

@inproceedings{rudolph_pods13,
        address = {New York, NY, USA},
        series = {{PODS} '13},
        title = {{Flag \& Check: Data Access with Monadically Defined Queries}},
        url = {https://dl.acm.org/doi/10.1145/2463664.2465227},
        doi = {10.1145/2463664.2465227},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Rudolph, Sebastian and Krötzsch, Markus},
        year = {2013}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,181	Expressive Languages for Querying the Semantic Web	2014	PODS	5.3064263e-05

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
525	The Chase Revisited	2008	PODS	0.00017118255
686	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.00014948634
1,541	Generalized Schema-Mappings: From Termination To Tractability	2009	PODS	0.00010427058
2,180	Monadic Datalog and the Expressive Power of Languages for Web Information Extraction	2002	PODS	9.0110009e-05
2,481	A General Datalog-Based Framework for Tractable Query Answering over Ontologies	2009	PODS	8.5196153e-05
2,544	Advanced Processing for Ontological Queries	2010	VLDB	8.4444438e-05
3,247	On Chase Termination Beyond Stratification	2009	VLDB	7.5993811e-05
8,779	Chase Termination: A Constraints Rewriting Approach	2010	VLDB	5.3748499e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,754	On Monotonic Determinacy and Rewritability For Recursive Queries and Views	2020	PODS
2	11,639	Deciding Boundedness of Monadic Sirups	2021	PODS
3	4,702	On the Complexity of Nonrecursive XQuery and Functional Query Languages on Complex Values	2005	PODS
4	13,027	Adding Disjunction to Datalog (Extended Abstract)	1994	PODS
5	633	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS
6	12,165	Does Query Evaluation Tractability Help Query Containment?	2014	PODS
7	1,630	On the Decidability of Query Containment under Constraints	1998	PODS
8	6,221	Well-Founded Semantics for Extended Datalog and Ontological Reasoning	2013	PODS
9	11,968	Stable Model Semantics for Tuple-Generating Dependencies Revisited	2017	PODS
10	11,525	Data Path Queries over Embedded Graph Databases	2022	PODS