A Theory of Regular Queries

Summary: Introduces RQ (regular queries), a natural, operation-closed class for graph/relational queries supporting disjunction, conjunction, projection and transitive closure while retaining decidable query-containment. Shows RQ = a Datalog fragment where recursion is restricted to transitive closure, yielding an expressive yet containment-decidable fragment that enables decidable query optimization. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h4dfa4ba65b16bee9
Venue: PODS
Year: 2016
Pagerank: 5.1498035e-05
Overall Rank: 9,618 | 35.36%
DOI: 10.1145/2902251.2902305

Incoming Non-self Citations Over Time

Authors

1. Moshe Y. Vardi (Rice University)

BibTeX Citation

@inproceedings{vardi_pods16,
        address = {New York, NY, USA},
        series = {{PODS} '16},
        title = {{A Theory of Regular Queries}},
        url = {https://dl.acm.org/doi/10.1145/2902251.2902305},
        doi = {10.1145/2902251.2902305},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Vardi, Moshe Y.},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,375	Transforming Property Graphs	2024	VLDB	5.1843659e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
24	Data Integration: A Theoretical Perspective	2002	PODS	0.00055018384
102	Efficient Optimization of a Class of Relational Expressions	1978	SIGMOD	0.00033899077
272	An Overview of Query Optimization in Relational Systems	1998	PODS	0.0002251422
356	Regular Path Queries with Constraints	1997	PODS	0.0002009439
1,254	Semistructured Data	1997	PODS	0.00011331788
2,115	Reusing Invariants: A New Strategy for Correlated Queries	1998	SIGMOD	9.0119103e-05
2,323	Efficient Query Reformulation in Peer Data Management Systems	2004	SIGMOD	8.637314e-05
3,156	View-Based Query Processing for Regular Path Queries with Inverse	2000	PODS	7.582275e-05
4,982	An Incremental Anytime Algorithm for Multi-Objective Query Optimization	2015	SIGMOD	6.3264052e-05
6,233	The Impact of Virtual Views on Containment	2010	VLDB	5.8412765e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,395	Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases	1991	PODS
2	1,952	Relational Expressive Power of Constraint Query Languages	1996	PODS
3	2,152	Theory of Database Queries (Extended Abstract)	1988	PODS
4	12,462	Does Query Evaluation Tractability Help Query Containment?	2014	PODS
5	8,142	On the First-Order Expressibility of Recursive Queries	1989	PODS
6	720	Querying Graph Databases	2013	PODS
7	2,110	A Study of Transitive Closure As a Recursion Mechanism	1987	SIGMOD
8	7,066	On the Decidability of Containment of Recursive Datalog Queries - Preliminary report	2004	PODS
9	1,661	On the Decidability of Query Containment under Constraints	1998	PODS
10	305	A Graphical Query Language Supporting Recursion	1987	SIGMOD