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)

Paper ID: 1332
Venue: PODS
Year: 2004
Pagerank: 8.1927747e-05
Overall Rank: 2,733 | 81.26%
DOI: 10.1145/1055558.1055601

Incoming Non-self Citations Over Time

Authors

1. Alan Nash (University of California San Diego)
2. Bertram Ludäscher (San Diego Supercomputer Center; University of California San Diego)

BibTeX Citation

@inproceedings{nash_pods04,
        address = {New York, NY, USA},
        series = {{PODS} '04},
        title = {{Processing First-Order Queries under Limited Access Patterns}},
        url = {https://dl.acm.org/doi/10.1145/1055558.1055601},
        doi = {10.1145/1055558.1055601},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Nash, Alan and Ludäscher, Bertram},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,392	Complete Yet Practical Search for Minimal Query Reformulations Under Constraints	2014	SIGMOD	7.4515019e-05
4,968	Towards Scalable Hybrid Stores: Constraint-Based Rewriting to the Rescue	2019	SIGMOD	6.4206525e-05
6,841	Querying Big Data by Accessing Small Data	2015	PODS	5.7574257e-05
7,484	On Scale Independence for Querying Big Data	2014	PODS	5.6074278e-05
8,701	Data Driven Approximation with Bounded Resources	2017	VLDB	5.3828806e-05
9,002	An Effective Syntax for Bounded Relational Queries	2016	SIGMOD	5.3346995e-05
9,093	Efficiently Ordering Subgoals with Access Constraints [Extended Abstract]	2006	PODS	5.3251649e-05
11,365	Distributed Consistency Beyond Queries	2023	PODS	5.093636e-05
12,029	Bounded Query Rewriting Using Views	2016	PODS	5.093636e-05
12,351	Querying Schemas With Access Restrictions	2012	VLDB	5.093636e-05
12,364	Determining Relevance of Accesses at Runtime	2011	PODS	5.093636e-05

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
117	Querying Heterogeneous Information Sources Using Source Descriptions	1996	VLDB	0.00032192665
298	Answering Queries Using Templates With Binding Patterns (Extended Abstract)	1995	PODS	0.00022138018
851	Query Optimization in the Presence of Limited Access Patterns	1999	SIGMOD	0.00013611183
2,122	E-Services: A Look Behind the Curtain	2003	PODS	9.1402274e-05
3,039	Query Containment for Data Integration Systems	2000	PODS	7.8265533e-05
3,565	The Complexity Of Ordering Subgoals	1988	PODS	7.3058198e-05
13,931	BIRN-M: A Semantic Mediator for Solving Real-World Neuroscience Problems	2003	SIGMOD	-

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,029	Bounded Query Rewriting Using Views	2016	PODS
2	9,009	Efficient Approximations of Conjunctive Queries	2012	PODS
3	2,947	Querying with Access Patterns and Integrity Constraints	2015	VLDB
4	4,986	Querying Graph Patterns	2011	PODS
5	7,195	Space-Time Tradeoffs for Conjunctive Queries with Access Patterns	2023	PODS
6	633	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS
7	7,088	On the First-order Expressibility of Computing Certain Answers to Conjunctive Queries over Uncertain Databases	2010	PODS
8	9,093	Efficiently Ordering Subgoals with Access Constraints [Extended Abstract]	2006	PODS
9	6,841	Querying Big Data by Accessing Small Data	2015	PODS
10	851	Query Optimization in the Presence of Limited Access Patterns	1999	SIGMOD