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.00029390022
Overall Rank
274 | 98.10%
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.00041055843
391 Indexing and Querying XML Data for Regular Path Expressions 2001 VLDB 0.00024564567
1,037 Querying Graph Databases 2013 PODS 0.00014502493
1,370 Monadic Datalog and the Expressive Power of Languages for Web Information Extraction 2002 PODS 0.00012338027
1,897 Type Inference for Queries on Semistructured Data (Extended Abstract) 1999 PODS 0.00010178006
2,342 Rewriting of Regular Expressions and Regular Path Queries 1999 PODS 9.0015589e-05
2,594 On XML Integrity Constraints in the Presence of DTDs 2001 PODS 8.474176e-05
2,855 Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach 2003 VLDB 8.0059865e-05
2,957 Computing Label-Constraint Reachability in Graph Databases 2010 SIGMOD 7.8198686e-05
3,257 Path Constraints on Semistructured and Structured Data 1998 PODS 7.3151681e-05
3,652 The Complexity of Evaluating Path Expressions in SPARQL 2012 PODS 6.875313e-05
3,681 Queries with Incomplete Answers over Semistructured Data 1999 PODS 6.8492288e-05
3,960 Integrity Constraints for XML 2000 PODS 6.5882121e-05
4,010 A Web Odyssey: from Codd to XML 2001 PODS 6.5351699e-05
4,191 Efficiently Answering Regular Simple Path Queries on Large Labeled Networks 2019 SIGMOD 6.3735885e-05
4,553 View-Based Query Containment 2003 PODS 6.091702e-05
5,122 Providing Database-like Access to the Web Using Queries Based on Textual Similarity 1998 SIGMOD 5.6803757e-05
5,406 Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints 2003 PODS 5.5243825e-05
5,424 A Trichotomy for Regular Simple Path Queries on Graphs 2013 PODS 5.5126983e-05
5,694 OLAP Dimension Constraints 2002 PODS 5.3682155e-05
5,856 Distributed Computation of Web Queries using Automata 2002 PODS 5.3003676e-05
7,361 Extended Path Expressions for XML 2001 PODS 4.7524599e-05
9,280 A Theory of Regular Queries 2016 PODS 4.3636639e-05
9,535 Graph Data Models, Query Languages and Programming Paradigms 2018 VLDB 4.3265843e-05
9,668 Interaction between Path and Type Constraints 1999 PODS 4.3074872e-05
9,676 Schema-Based Query Optimisation for Graph Databases 2025 SIGMOD 4.3047774e-05
10,330 Sharp: Shared State Reduction for Efficient Matching of Sequential Patterns 2026 VLDB 4.1945683e-05
10,344 Circuits and Formulas for Datalog over Semirings 2025 PODS 4.1945683e-05
11,014 Efficient Regular Simple Path Queries under Transitive Restricted Expressions 2024 VLDB 4.1945683e-05
11,248 Scalable Reasoning on Document Stores via Instance-Aware Query Rewriting 2023 VLDB 4.1945683e-05
12,434 Reasoning about XML Update Constraints 2007 PODS 4.1945683e-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.0010066783
114 A Query Language and Optimization Techniques for Unstructured Data 1996 SIGMOD 0.00046339735
256 GraphLog: a Visual Formalism for Real Life Recursion 1990 PODS 0.00030259041
271 Querying Object-Oriented Databases 1992 SIGMOD 0.00029452935
437 W3QS: A Query System for the World-Wide Web 1995 VLDB 0.00023240203
673 One-Sided Recursions 1987 PODS 0.00018348841
844 Object Fusion in Mediator Systems 1996 VLDB 0.00016004956
1,669 Query Decomposition and View Maintenance for Query Languages for Unstructured Data 1996 VLDB 0.00010955767
1,712 Bounds on the Propagation of Selection into Logic Programs 1987 PODS 0.00010804573
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
7,848 Cost-Sensitive Reordering of Navigational Primitives 2005 SIGMOD 4.6362551e-05
2,401 Physical Data Independence, Constraints, and Optimization with Universal Plans 1999 VLDB 8.8954126e-05
13,050 Path Expressions in Databases (Extended Abstract) 1983 PODS 4.1945683e-05
12,681 Reachability and Connectivity Queries in Constraint Databases 2000 PODS 4.1945683e-05
9,668 Interaction between Path and Type Constraints 1999 PODS 4.3074872e-05
1,037 Querying Graph Databases 2013 PODS 0.00014502493
2,503 Evaluating Queries with Generalized Path Expressions 1996 SIGMOD 8.6379665e-05
2,826 Regular Path Query Evaluation on Streaming Graphs 2020 SIGMOD 8.056119e-05
5,406 Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints 2003 PODS 5.5243825e-05
3,257 Path Constraints on Semistructured and Structured Data 1998 PODS 7.3151681e-05