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.132775e-05
Overall Rank: 9,647 | 35.34%
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,401	Transforming Property Graphs	2024	VLDB	5.1672232e-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.00055201845
104	Efficient Optimization of a Class of Relational Expressions	1978	SIGMOD	0.00033799916
259	An Overview of Query Optimization in Relational Systems	1998	PODS	0.00022881075
358	Regular Path Queries with Constraints	1997	PODS	0.00020030407
1,258	Semistructured Data	1997	PODS	0.00011301839
2,132	Reusing Invariants: A New Strategy for Correlated Queries	1998	SIGMOD	8.9837489e-05
2,333	Efficient Query Reformulation in Peer Data Management Systems	2004	SIGMOD	8.6088875e-05
3,169	View-Based Query Processing for Regular Path Queries with Inverse	2000	PODS	7.557345e-05
5,006	An Incremental Anytime Algorithm for Multi-Objective Query Optimization	2015	SIGMOD	6.3057396e-05
6,244	The Impact of Virtual Views on Containment	2010	VLDB	5.8219706e-05

Semantically Similar Papers

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