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: hce82cd96a89a9918
Venue: PODS
Year: 2004
Pagerank: 8.0100392e-05
Overall Rank: 2,790 | 81.25%
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,447	Complete Yet Practical Search for Minimal Query Reformulations Under Constraints	2014	SIGMOD	7.2941472e-05
5,091	Towards Scalable Hybrid Stores: Constraint-Based Rewriting to the Rescue	2019	SIGMOD	6.2797352e-05
6,954	Querying Big Data by Accessing Small Data	2015	PODS	5.6350266e-05
7,610	On Scale Independence for Querying Big Data	2014	PODS	5.4844912e-05
8,846	Data Driven Approximation with Bounded Resources	2017	VLDB	5.2649328e-05
9,152	An Effective Syntax for Bounded Relational Queries	2016	SIGMOD	5.2177821e-05
9,266	Efficiently Ordering Subgoals with Access Constraints [Extended Abstract]	2006	PODS	5.2056825e-05
11,681	Distributed Consistency Beyond Queries	2023	PODS	4.9793485e-05
12,324	Bounded Query Rewriting Using Views	2016	PODS	4.9793485e-05
12,642	Querying Schemas With Access Restrictions	2012	VLDB	4.9793485e-05
12,655	Determining Relevance of Accesses at Runtime	2011	PODS	4.9793485e-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.00031630695
301	Answering Queries Using Templates With Binding Patterns (Extended Abstract)	1995	PODS	0.00021682744
869	Query Optimization in the Presence of Limited Access Patterns	1999	SIGMOD	0.00013348278
2,159	E-Services: A Look Behind the Curtain	2003	PODS	8.9372589e-05
3,095	Query Containment for Data Integration Systems	2000	PODS	7.6532922e-05
3,640	The Complexity Of Ordering Subgoals	1988	PODS	7.1439794e-05
14,242	BIRN-M: A Semantic Mediator for Solving Real-World Neuroscience Problems	2003	SIGMOD	-

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,452	Bounded Conjunctive Queries	2014	VLDB
2	9,169	Efficient Approximations of Conjunctive Queries	2012	PODS
3	3,000	Querying with Access Patterns and Integrity Constraints	2015	VLDB
4	5,096	Querying Graph Patterns	2011	PODS
5	7,338	Space-Time Tradeoffs for Conjunctive Queries with Access Patterns	2023	PODS
6	642	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS
7	7,230	On the First-order Expressibility of Computing Certain Answers to Conjunctive Queries over Uncertain Databases	2010	PODS
8	9,266	Efficiently Ordering Subgoals with Access Constraints [Extended Abstract]	2006	PODS
9	6,954	Querying Big Data by Accessing Small Data	2015	PODS
10	869	Query Optimization in the Presence of Limited Access Patterns	1999	SIGMOD