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: 1699
Venue: PODS
Year: 2016
Pagerank: 5.2704983e-05
Overall Rank: 9,430 | 35.31%
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,187	Transforming Property Graphs	2024	VLDB	5.3058708e-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
22	Data Integration: A Theoretical Perspective	2002	PODS	0.00056204792
97	Efficient Optimization of a Class of Relational Expressions	1978	SIGMOD	0.00034574497
290	An Overview of Query Optimization in Relational Systems	1998	PODS	0.0002227038
348	Regular Path Queries with Constraints	1997	PODS	0.00020518814
1,233	Semistructured Data	1997	PODS	0.00011562468
2,093	Reusing Invariants: A New Strategy for Correlated Queries	1998	SIGMOD	9.1831198e-05
2,268	Efficient Query Reformulation in Peer Data Management Systems	2004	SIGMOD	8.8370676e-05
3,103	View-Based Query Processing for Regular Path Queries with Inverse	2000	PODS	7.7562264e-05
4,880	An Incremental Anytime Algorithm for Multi-Objective Query Optimization	2015	SIGMOD	6.4656221e-05
6,098	The Impact of Virtual Views on Containment	2010	VLDB	5.9778168e-05

Semantically Similar Papers

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