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: h24ae240a6ac74114
Venue: PODS
Year: 1997
Pagerank: 0.00020103855
Overall Rank: 356 | 97.61%
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
162	Integration of Heterogeneous Databases Without Common Domains Using Queries Based on Textual Similarity	1998	SIGMOD	0.00027536748
351	Indexing and Querying XML Data for Regular Path Expressions	2001	VLDB	0.00020251513
719	Querying Graph Databases	2013	PODS	0.00014529156
2,041	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS	9.1421879e-05
2,223	Monadic Datalog and the Expressive Power of Languages for Web Information Extraction	2002	PODS	8.8092332e-05
2,317	Type Inference for Queries on Semistructured Data (Extended Abstract)	1999	PODS	8.6477878e-05
2,534	Computing Label-Constraint Reachability in Graph Databases	2010	SIGMOD	8.3335732e-05
2,565	On XML Integrity Constraints in the Presence of DTDs	2001	PODS	8.2910005e-05
2,680	Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach	2003	VLDB	8.1432169e-05
3,365	Path Constraints on Semistructured and Structured Data	1998	PODS	7.3728818e-05
3,474	The Complexity of Evaluating Path Expressions in SPARQL	2012	PODS	7.2718547e-05
3,523	Efficiently Answering Regular Simple Path Queries on Large Labeled Networks	2019	SIGMOD	7.2343247e-05
4,248	Integrity Constraints for XML	2000	PODS	6.704016e-05
4,266	A Web Odyssey: from Codd to XML	2001	PODS	6.6972871e-05
4,514	View-Based Query Containment	2003	PODS	6.5650143e-05
4,592	Queries with Incomplete Answers over Semistructured Data	1999	PODS	6.513694e-05
5,109	A Trichotomy for Regular Simple Path Queries on Graphs	2013	PODS	6.2695208e-05
5,226	Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints	2003	PODS	6.2207517e-05
5,762	Providing Database-like Access to the Web Using Queries Based on Textual Similarity	1998	SIGMOD	6.0035937e-05
6,016	OLAP Dimension Constraints	2002	PODS	5.9134174e-05
6,983	Distributed Computation of Web Queries using Automata	2002	PODS	5.6285752e-05
8,043	Extended Path Expressions for XML	2001	PODS	5.4011538e-05
8,831	Graph Data Models, Query Languages and Programming Paradigms	2018	VLDB	5.2681194e-05
9,611	A Theory of Regular Queries	2016	PODS	5.1522425e-05
9,980	Schema-Based Query Optimisation for Graph Databases	2025	SIGMOD	5.1013913e-05
10,067	Interaction between Path and Type Constraints	1999	PODS	5.0873692e-05
11,074	Sharp: Shared State Reduction for Efficient Matching of Sequential Patterns	2026	VLDB	4.9793485e-05
11,083	Circuits and Formulas for Datalog over Semirings	2025	PODS	4.9793485e-05
11,561	Efficient Regular Simple Path Queries under Transitive Restricted Expressions	2024	VLDB	4.9793485e-05
11,760	Scalable Reasoning on Document Stores via Instance-Aware Query Rewriting	2023	VLDB	4.9793485e-05
12,918	Reasoning about XML Update Constraints	2007	PODS	4.9793485e-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
18	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.00059023577
130	A Query Language and Optimization Techniques for Unstructured Data	1996	SIGMOD	0.00030320165
297	GraphLog: a Visual Formalism for Real Life Recursion	1990	PODS	0.00021840374
413	Querying Object-Oriented Databases	1992	SIGMOD	0.00018681401
586	W3QS: A Query System for the World-Wide Web	1995	VLDB	0.00015944965
1,190	Object Fusion in Mediator Systems	1996	VLDB	0.00011590876
1,682	Bounds on the Propagation of Selection into Logic Programs	1987	PODS	9.8850863e-05
2,065	One-Sided Recursions	1987	PODS	9.0940924e-05
2,147	Query Decomposition and View Maintenance for Query Languages for Unstructured Data	1996	VLDB	8.9576491e-05

Semantically Similar Papers

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