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.1522425e-05
Overall Rank: 9,611 | 35.39%
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,366	Transforming Property Graphs	2024	VLDB	5.1868213e-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.00055043581
102	Efficient Optimization of a Class of Relational Expressions	1978	SIGMOD	0.00033914384
272	An Overview of Query Optimization in Relational Systems	1998	PODS	0.00022509573
356	Regular Path Queries with Constraints	1997	PODS	0.00020103855
1,251	Semistructured Data	1997	PODS	0.00011337126
2,114	Reusing Invariants: A New Strategy for Correlated Queries	1998	SIGMOD	9.0158191e-05
2,321	Efficient Query Reformulation in Peer Data Management Systems	2004	SIGMOD	8.6413639e-05
3,155	View-Based Query Processing for Regular Path Queries with Inverse	2000	PODS	7.5858519e-05
4,980	An Incremental Anytime Algorithm for Multi-Objective Query Optimization	2015	SIGMOD	6.3293674e-05
6,230	The Impact of Virtual Views on Containment	2010	VLDB	5.844043e-05

Semantically Similar Papers

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