Generating Low-cost Plans From Proofs

Summary: Reduce plan search to proof search: map proofs of query answerability (via interpolation) to restricted-interface access plans, exploiting integrity constraints and TGDs to answer queries without direct relation access. Provide algorithms to generate and cost-optimize alternative proof-derived plans, generalizing preservation/interpolation links in reformulation problems. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1625
Venue: PODS
Year: 2014
Pagerank: 5.5957787e-05
Overall Rank: 7,565 | 48.10%
DOI: 10.1145/2594538.2594550

Incoming Non-self Citations Over Time

Authors

1. Michael Benedikt (University of Oxford)
2. Balder ten Cate (LogicBlox Inc.; University of California Santa Cruz)
3. Efthymia Tsamoura (University of Oxford)

BibTeX Citation

@inproceedings{benedikt_pods14,
        address = {New York, NY, USA},
        series = {{PODS} '14},
        title = {{Generating Low-cost Plans From Proofs}},
        url = {https://dl.acm.org/doi/10.1145/2594538.2594550},
        doi = {10.1145/2594538.2594550},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Benedikt, Michael and Cate, Balder ten and Tsamoura, Efthymia},
        year = {2014}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,947	Querying with Access Patterns and Integrity Constraints	2015	VLDB	7.9325276e-05
8,098	Designing a Query Language for RDF: Marrying Open and Closed Worlds	2016	PODS	5.4874656e-05
8,236	PDQ: Proof-driven Query Answering over Web-based Data	2014	VLDB	5.460452e-05
11,867	Block as a Value for SQL over NoSQL	2019	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
69	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.00038090878
851	Query Optimization in the Presence of Limited Access Patterns	1999	SIGMOD	0.00013611183
2,189	Physical Data Independence, Constraints, and Optimization with Universal Plans	1999	VLDB	8.9856333e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,733	Processing First-Order Queries under Limited Access Patterns	2004	PODS
2	8,007	Complete Approximations of Incomplete Queries	2013	VLDB
3	8,236	PDQ: Proof-driven Query Answering over Web-based Data	2014	VLDB
4	1,530	Multiple Query Processing in Deductive Databases using Query Graphs	1986	VLDB
5	851	Query Optimization in the Presence of Limited Access Patterns	1999	SIGMOD
6	5,225	Approximate Lifted Inference with Probabilistic Databases	2015	VLDB
7	9,093	Efficiently Ordering Subgoals with Access Constraints [Extended Abstract]	2006	PODS
8	7,830	When Can We Answer Queries Using Result-Bounded Data Interfaces?	2018	PODS
9	6,540	Generating Efficient Plans for Queries Using Views	2001	SIGMOD
10	2,947	Querying with Access Patterns and Integrity Constraints	2015	VLDB