Database Paper Browser

Back to papers

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
1110
Venue
PODS
Year
1997
Pagerank
0.00029365217
Overall Rank
276 | 98.09%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 31 of 31 citing papers.

Rank Citing Paper Year Venue Pagerank
150 Integration of Heterogeneous Databases Without Common Domains Using Queries Based on Textual Similarity 1998 SIGMOD 0.00041081536
392 Indexing and Querying XML Data for Regular Path Expressions 2001 VLDB 0.00024546229
1,040 Querying Graph Databases 2013 PODS 0.00014483577
1,374 Monadic Datalog and the Expressive Power of Languages for Web Information Extraction 2002 PODS 0.00012325543
1,900 Type Inference for Queries on Semistructured Data (Extended Abstract) 1999 PODS 0.00010168127
2,345 Rewriting of Regular Expressions and Regular Path Queries 1999 PODS 8.9933611e-05
2,598 On XML Integrity Constraints in the Presence of DTDs 2001 PODS 8.4660607e-05
2,862 Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach 2003 VLDB 7.9982917e-05
2,958 Computing Label-Constraint Reachability in Graph Databases 2010 SIGMOD 7.8126329e-05
3,262 Path Constraints on Semistructured and Structured Data 1998 PODS 7.3081091e-05
3,659 The Complexity of Evaluating Path Expressions in SPARQL 2012 PODS 6.8684407e-05
3,683 Queries with Incomplete Answers over Semistructured Data 1999 PODS 6.84255e-05
3,962 Integrity Constraints for XML 2000 PODS 6.581926e-05
4,014 A Web Odyssey: from Codd to XML 2001 PODS 6.5300582e-05
4,191 Efficiently Answering Regular Simple Path Queries on Large Labeled Networks 2019 SIGMOD 6.3676619e-05
4,552 View-Based Query Containment 2003 PODS 6.0856349e-05
5,123 Providing Database-like Access to the Web Using Queries Based on Textual Similarity 1998 SIGMOD 5.6747761e-05
5,415 Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints 2003 PODS 5.5188622e-05
5,435 A Trichotomy for Regular Simple Path Queries on Graphs 2013 PODS 5.5074113e-05
5,707 OLAP Dimension Constraints 2002 PODS 5.363144e-05
5,862 Distributed Computation of Web Queries using Automata 2002 PODS 5.295278e-05
7,357 Extended Path Expressions for XML 2001 PODS 4.7479042e-05
9,285 A Theory of Regular Queries 2016 PODS 4.3594818e-05
9,536 Graph Data Models, Query Languages and Programming Paradigms 2018 VLDB 4.3225428e-05
9,668 Interaction between Path and Type Constraints 1999 PODS 4.3033855e-05
9,676 Schema-Based Query Optimisation for Graph Databases 2025 SIGMOD 4.3006524e-05
10,342 Sharp: Shared State Reduction for Efficient Matching of Sequential Patterns 2026 VLDB 4.1905499e-05
10,356 Circuits and Formulas for Datalog over Semirings 2025 PODS 4.1905499e-05
11,017 Efficient Regular Simple Path Queries under Transitive Restricted Expressions 2024 VLDB 4.1905499e-05
11,250 Scalable Reasoning on Document Stores via Instance-Aware Query Rewriting 2023 VLDB 4.1905499e-05
12,443 Reasoning about XML Update Constraints 2007 PODS 4.1905499e-05
Previous Page 1 / 1 Next

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.00099936325
115 A Query Language and Optimization Techniques for Unstructured Data 1996 SIGMOD 0.00046301137
256 GraphLog: a Visual Formalism for Real Life Recursion 1990 PODS 0.00030241337
272 Querying Object-Oriented Databases 1992 SIGMOD 0.0002942487
438 W3QS: A Query System for the World-Wide Web 1995 VLDB 0.00023220283
840 Object Fusion in Mediator Systems 1996 VLDB 0.000159889
1,611 One-Sided Recursions 1987 PODS 0.00011146101
1,636 Bounds on the Propagation of Selection into Logic Programs 1987 PODS 0.00011058643
1,667 Query Decomposition and View Maintenance for Query Languages for Unstructured Data 1996 VLDB 0.00010947593
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
7,852 Cost-Sensitive Reordering of Navigational Primitives 2005 SIGMOD 4.631832e-05
2,398 Physical Data Independence, Constraints, and Optimization with Universal Plans 1999 VLDB 8.8871067e-05
13,061 Path Expressions in Databases (Extended Abstract) 1983 PODS 4.1905499e-05
12,690 Reachability and Connectivity Queries in Constraint Databases 2000 PODS 4.1905499e-05
9,668 Interaction between Path and Type Constraints 1999 PODS 4.3033855e-05
1,040 Querying Graph Databases 2013 PODS 0.00014483577
2,506 Evaluating Queries with Generalized Path Expressions 1996 SIGMOD 8.6273062e-05
2,832 Regular Path Query Evaluation on Streaming Graphs 2020 SIGMOD 8.048358e-05
5,415 Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints 2003 PODS 5.5188622e-05
3,262 Path Constraints on Semistructured and Structured Data 1998 PODS 7.3081091e-05