Regular Path Queries with Constraints

Summary: Optimizes regular path queries over semistructured data in distributed asynchronous settings by exploiting local path constraints. Establishes decidability and complexity bounds for the implication problem for these constraints, enabling principled use of local info in query planning. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1109
Venue: PODS
Year: 1997
Pagerank: 0.00020518814
Overall Rank: 348 | 97.62%
DOI: 10.1145/263661.263676

Incoming Non-self Citations Over Time

Authors

1. Serge Abiteboul (INRIA; Stanford University)
2. Victor Vianu (University of California San Diego)

BibTeX Citation

@inproceedings{abiteboul_pods97,
        address = {New York, NY, USA},
        series = {{PODS} '97},
        title = {{Regular Path Queries with Constraints}},
        url = {https://dl.acm.org/doi/10.1145/263661.263676},
        doi = {10.1145/263661.263676},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Abiteboul, Serge and Vianu, Victor},
        year = {1997}
}

Incoming Citations (Sorted by Pagerank)

Showing 31 of 31 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
160	Integration of Heterogeneous Databases Without Common Domains Using Queries Based on Textual Similarity	1998	SIGMOD	0.0002802209
341	Indexing and Querying XML Data for Regular Path Expressions	2001	VLDB	0.00020704572
747	Querying Graph Databases	2013	PODS	0.00014400452
2,066	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS	9.2348082e-05
2,180	Monadic Datalog and the Expressive Power of Languages for Web Information Extraction	2002	PODS	9.0110009e-05
2,261	Type Inference for Queries on Semistructured Data (Extended Abstract)	1999	PODS	8.846133e-05
2,490	Computing Label-Constraint Reachability in Graph Databases	2010	SIGMOD	8.5090456e-05
2,515	On XML Integrity Constraints in the Presence of DTDs	2001	PODS	8.4811795e-05
2,625	Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach	2003	VLDB	8.3300135e-05
3,308	Path Constraints on Semistructured and Structured Data	1998	PODS	7.5381026e-05
3,452	The Complexity of Evaluating Path Expressions in SPARQL	2012	PODS	7.4007472e-05
3,473	Efficiently Answering Regular Simple Path Queries on Large Labeled Networks	2019	SIGMOD	7.3864987e-05
4,167	Integrity Constraints for XML	2000	PODS	6.8578387e-05
4,178	A Web Odyssey: from Codd to XML	2001	PODS	6.849218e-05
4,445	View-Based Query Containment	2003	PODS	6.699172e-05
4,495	Queries with Incomplete Answers over Semistructured Data	1999	PODS	6.6623097e-05
4,981	A Trichotomy for Regular Simple Path Queries on Graphs	2013	PODS	6.4127882e-05
5,146	Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints	2003	PODS	6.3470184e-05
5,642	Providing Database-like Access to the Web Using Queries Based on Textual Similarity	1998	SIGMOD	6.1383189e-05
5,892	OLAP Dimension Constraints	2002	PODS	6.0488431e-05
6,838	Distributed Computation of Web Queries using Automata	2002	PODS	5.757764e-05
7,876	Extended Path Expressions for XML	2001	PODS	5.5249028e-05
9,430	A Theory of Regular Queries	2016	PODS	5.2704983e-05
9,682	Graph Data Models, Query Languages and Programming Paradigms	2018	VLDB	5.2353888e-05
9,811	Schema-Based Query Optimisation for Graph Databases	2025	SIGMOD	5.214913e-05
9,877	Interaction between Path and Type Constraints	1999	PODS	5.2041072e-05
10,628	Sharp: Shared State Reduction for Efficient Matching of Sequential Patterns	2026	VLDB	5.093636e-05
10,640	Circuits and Formulas for Datalog over Semirings	2025	PODS	5.093636e-05
11,225	Efficient Regular Simple Path Queries under Transitive Restricted Expressions	2024	VLDB	5.093636e-05
11,448	Scalable Reasoning on Document Stores via Instance-Aware Query Rewriting	2023	VLDB	5.093636e-05
12,628	Reasoning about XML Update Constraints	2007	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
16	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.00060089598
124	A Query Language and Optimization Techniques for Unstructured Data	1996	SIGMOD	0.00030950263
300	GraphLog: a Visual Formalism for Real Life Recursion	1990	PODS	0.00022046803
403	Querying Object-Oriented Databases	1992	SIGMOD	0.0001907249
573	W3QS: A Query System for the World-Wide Web	1995	VLDB	0.00016290377
1,167	Object Fusion in Mediator Systems	1996	VLDB	0.00011845214
1,653	Bounds on the Propagation of Selection into Logic Programs	1987	PODS	0.000101081
2,033	One-Sided Recursions	1987	PODS	9.2819369e-05
2,118	Query Decomposition and View Maintenance for Query Languages for Unstructured Data	1996	VLDB	9.1419103e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,864	Cost-Sensitive Reordering of Navigational Primitives	2005	SIGMOD
2	2,189	Physical Data Independence, Constraints, and Optimization with Universal Plans	1999	VLDB
3	13,249	Path Expressions in Databases (Extended Abstract)	1983	PODS
4	12,874	Reachability and Connectivity Queries in Constraint Databases	2000	PODS
5	9,877	Interaction between Path and Type Constraints	1999	PODS
6	747	Querying Graph Databases	2013	PODS
7	3,067	Evaluating Queries with Generalized Path Expressions	1996	SIGMOD
8	2,209	Regular Path Query Evaluation on Streaming Graphs	2020	SIGMOD
9	5,146	Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints	2003	PODS
10	3,308	Path Constraints on Semistructured and Structured Data	1998	PODS