Processing First-Order Queries under Limited Access Patterns
Summary: Extends feasibility under access-patterns to full first-order queries, proving its decision complexity mirrors query-containment and is undecidable in many fragments. Offers an NP-checkable approximation (P for UCQs with negation) and sketches a practical processing strategy. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Alan Nash
- 2. Bertram Ludäscher
Incoming Citations (Sorted by Pagerank)
Showing 11 of 11 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 3,509 | Complete Yet Practical Search for Minimal Query Reformulations Under Constraints | 2014 | SIGMOD | 7.0263584e-05 |
| 5,402 | Towards Scalable Hybrid Stores: Constraint-Based Rewriting to the Rescue | 2019 | SIGMOD | 5.5278023e-05 |
| 7,085 | Querying Big Data by Accessing Small Data | 2015 | PODS | 4.8388174e-05 |
| 7,413 | On Scale Independence for Querying Big Data | 2014 | PODS | 4.7358047e-05 |
| 8,715 | Data Driven Approximation with Bounded Resources | 2017 | VLDB | 4.4619052e-05 |
| 8,937 | Efficiently Ordering Subgoals with Access Constraints [Extended Abstract] | 2006 | PODS | 4.427232e-05 |
| 8,961 | An Effective Syntax for Bounded Relational Queries | 2016 | SIGMOD | 4.4206115e-05 |
| 11,159 | Distributed Consistency Beyond Queries | 2023 | PODS | 4.1945683e-05 |
| 11,826 | Bounded Query Rewriting Using Views | 2016 | PODS | 4.1945683e-05 |
| 12,155 | Querying Schemas With Access Restrictions | 2012 | VLDB | 4.1945683e-05 |
| 12,168 | Determining Relevance of Accesses at Runtime | 2011 | PODS | 4.1945683e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 7 of 7 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 127 | Querying Heterogeneous Information Sources Using Source Descriptions | 1996 | VLDB | 0.00044642203 |
| 291 | Answering Queries Using Templates With Binding Patterns (Extended Abstract) | 1995 | PODS | 0.00028831632 |
| 870 | Query Optimization in the Presence of Limited Access Patterns | 1999 | SIGMOD | 0.00015771912 |
| 1,779 | E-Services: A Look Behind the Curtain | 2003 | PODS | 0.00010581176 |
| 2,187 | The Complexity Of Ordering Subgoals | 1988 | PODS | 9.3375092e-05 |
| 3,168 | Query Containment for Data Integration Systems | 2000 | PODS | 7.4508875e-05 |
| 13,730 | BIRN-M: A Semantic Mediator for Solving Real-World Neuroscience Problems | 2003 | SIGMOD | - |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 11,826 | Bounded Query Rewriting Using Views | 2016 | PODS | 4.1945683e-05 |
| 8,851 | Efficient Approximations of Conjunctive Queries | 2012 | PODS | 4.4363908e-05 |
| 2,936 | Querying with Access Patterns and Integrity Constraints | 2015 | VLDB | 7.8554347e-05 |
| 4,946 | Querying Graph Patterns | 2011 | PODS | 5.8149362e-05 |
| 7,761 | Space-Time Tradeoffs for Conjunctive Queries with Access Patterns | 2023 | PODS | 4.658708e-05 |
| 581 | The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version) | 1992 | PODS | 0.00019767772 |
| 7,063 | On the First-order Expressibility of Computing Certain Answers to Conjunctive Queries over Uncertain Databases | 2010 | PODS | 4.8461152e-05 |
| 8,937 | Efficiently Ordering Subgoals with Access Constraints [Extended Abstract] | 2006 | PODS | 4.427232e-05 |
| 7,085 | Querying Big Data by Accessing Small Data | 2015 | PODS | 4.8388174e-05 |
| 870 | Query Optimization in the Presence of Limited Access Patterns | 1999 | SIGMOD | 0.00015771912 |