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.00020030407
Overall Rank: 358 | 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
164	Integration of Heterogeneous Databases Without Common Domains Using Queries Based on Textual Similarity	1998	SIGMOD	0.00027451323
352	Indexing and Querying XML Data for Regular Path Expressions	2001	VLDB	0.00020179814
719	Querying Graph Databases	2013	PODS	0.00014493767
2,043	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS	9.1266211e-05
2,238	Monadic Datalog and the Expressive Power of Languages for Web Information Extraction	2002	PODS	8.7761804e-05
2,331	Type Inference for Queries on Semistructured Data (Extended Abstract)	1999	PODS	8.6151201e-05
2,541	Computing Label-Constraint Reachability in Graph Databases	2010	SIGMOD	8.3021057e-05
2,571	On XML Integrity Constraints in the Presence of DTDs	2001	PODS	8.2596816e-05
2,691	Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach	2003	VLDB	8.1124785e-05
3,377	Path Constraints on Semistructured and Structured Data	1998	PODS	7.3455463e-05
3,483	The Complexity of Evaluating Path Expressions in SPARQL	2012	PODS	7.2450764e-05
3,530	Efficiently Answering Regular Simple Path Queries on Large Labeled Networks	2019	SIGMOD	7.2070034e-05
4,267	Integrity Constraints for XML	2000	PODS	6.6786936e-05
4,281	A Web Odyssey: from Codd to XML	2001	PODS	6.6721591e-05
4,533	View-Based Query Containment	2003	PODS	6.540906e-05
4,609	Queries with Incomplete Answers over Semistructured Data	1999	PODS	6.4891057e-05
5,133	A Trichotomy for Regular Simple Path Queries on Graphs	2013	PODS	6.2458323e-05
5,249	Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints	2003	PODS	6.1979445e-05
5,776	Providing Database-like Access to the Web Using Queries Based on Textual Similarity	1998	SIGMOD	5.981183e-05
6,030	OLAP Dimension Constraints	2002	PODS	5.8911268e-05
7,005	Distributed Computation of Web Queries using Automata	2002	PODS	5.607308e-05
8,069	Extended Path Expressions for XML	2001	PODS	5.3807682e-05
8,858	Graph Data Models, Query Languages and Programming Paradigms	2018	VLDB	5.248343e-05
9,647	A Theory of Regular Queries	2016	PODS	5.132775e-05
10,024	Schema-Based Query Optimisation for Graph Databases	2025	SIGMOD	5.082116e-05
10,106	Interaction between Path and Type Constraints	1999	PODS	5.0681497e-05
11,144	Sharp: Shared State Reduction for Efficient Matching of Sequential Patterns	2026	VLDB	4.9605343e-05
11,153	Circuits and Formulas for Datalog over Semirings	2025	PODS	4.9605343e-05
11,616	Efficient Regular Simple Path Queries under Transitive Restricted Expressions	2024	VLDB	4.9605343e-05
11,810	Scalable Reasoning on Document Stores via Instance-Aware Query Rewriting	2023	VLDB	4.9605343e-05
12,966	Reasoning about XML Update Constraints	2007	PODS	4.9605343e-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.00058816744
131	A Query Language and Optimization Techniques for Unstructured Data	1996	SIGMOD	0.000302173
299	GraphLog: a Visual Formalism for Real Life Recursion	1990	PODS	0.00021766741
416	Querying Object-Oriented Databases	1992	SIGMOD	0.00018613776
589	W3QS: A Query System for the World-Wide Web	1995	VLDB	0.00015887069
1,196	Object Fusion in Mediator Systems	1996	VLDB	0.00011548322
1,688	Bounds on the Propagation of Selection into Logic Programs	1987	PODS	9.8481921e-05
2,078	One-Sided Recursions	1987	PODS	9.0607099e-05
2,159	Query Decomposition and View Maintenance for Query Languages for Unstructured Data	1996	VLDB	8.9259899e-05

Semantically Similar Papers

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