Positive Higher-Order Queries

Summary: Embeds positive relational algebra into a simply-typed lambda-calculus to express CQs/UCQs and higher-order, syntax-independent query functionals. Shows decidability and gives exact complexity for equivalence/containment when variables range over positive RA, identifies tractable fragments and provides upper bounds for other target classes. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1503
Venue: PODS
Year: 2010
Pagerank: 5.5746273e-05
Overall Rank: 7,654 | 47.49%
DOI: 10.1145/1807085.1807091

Incoming Non-self Citations Over Time

Authors

1. Michael Benedikt (University of Oxford)
2. Gabriele Puppis (University of Oxford)
3. Huy Vu (University of Oxford)

BibTeX Citation

@inproceedings{benedikt_pods10,
        address = {New York, NY, USA},
        series = {{PODS} '10},
        title = {{Positive Higher-Order Queries}},
        url = {https://dl.acm.org/doi/10.1145/1807085.1807091},
        doi = {10.1145/1807085.1807091},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Benedikt, Michael and Puppis, Gabriele and Vu, Huy},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,155	Query Shredding: Efficient Relational Evaluation of Queries over Nested Multisets	2014	SIGMOD	7.695861e-05
6,098	The Impact of Virtual Views on Containment	2010	VLDB	5.9778168e-05
12,390	HOMES: A Higher-Order Mapping Evaluation System	2011	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
97	Efficient Optimization of a Class of Relational Expressions	1978	SIGMOD	0.00034574497
134	Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies (Extended Abstract)	1982	PODS	0.00030343737
162	Inclusion dependencies and their interaction with functional dependencies (Extended abstract)	1982	PODS	0.00027886326
1,031	Answering Queries Using Limited External Query Processors	1996	PODS	0.0001253927
1,636	Relaxing Join and Selection Queries	2006	VLDB	0.00010156479
1,777	Deciding Containment for Queries with Complex Objects (Extended Abstract)	1997	PODS	9.7849758e-05
1,928	Relations with Relation Names as Arguments: Algebra and Calculus	1992	PODS	9.4692029e-05
2,248	Database Programming in Machiavelli - a Polymorphic Language with Static Type Inference	1989	SIGMOD	8.8703718e-05
4,702	On the Complexity of Nonrecursive XQuery and Functional Query Languages on Complex Values	2005	PODS	6.5549225e-05
6,563	Functional Database Query Languages as Typed Lambda Calculi of Fixed Order (Extended Abstract)	1994	PODS	5.8384765e-05
6,661	Complexity of Nonrecursive Logic Programs with Complex Values	1998	PODS	5.8101181e-05
7,196	Typed Query Languages for Databases Containing Queries	1998	PODS	5.6764289e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,620	A Dichotomy in the Intensional Expressive Power of Nested Relational Calculi augmented with Aggregate Functions and a Powerset Operator	2013	PODS
2	1,630	On the Decidability of Query Containment under Constraints	1998	PODS
3	2,897	On the Expressive Power of Database Queries with Intermediate Types	1988	PODS
4	414	On the Complexity of Database Queries (Extended Abstract)	1997	PODS
5	1,777	Deciding Containment for Queries with Complex Objects (Extended Abstract)	1997	PODS
6	174	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS
7	2,296	Containment and Minimization of Positive Conjunctive Queries in OODB's (Extended Abstract)	1992	PODS
8	6,563	Functional Database Query Languages as Typed Lambda Calculi of Fixed Order (Extended Abstract)	1994	PODS
9	1,890	Relational Expressive Power of Constraint Query Languages	1996	PODS
10	4,336	Languages for Relational Databases over Interpreted Structures	1997	PODS