Functional Database Query Languages as Typed Lambda Calculi of Fixed Order (Extended Abstract)

Summary: Characterizes functional DB query languages as fixed-order typed lambda calculi (TLI_i/MLI_i) with list-based DBs (requiring order ≥3) where queries and databases are lambda terms evaluated by reduction. Proves expressivity/complexity correspondences FO ⊆ TLI_0 ⊆ MLI_0 ⊆ LOGSPACE ⊆ TLI_1=MLI_1=PTIME ⊆ TLI_2 and shows fixed-order ML type inference is polynomial, implying low-order ML-style programs suffice to express efficient queries. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h85635c7d3e74135a
Venue: PODS
Year: 1994
Pagerank: 5.7074984e-05
Overall Rank: 6,689 | 55.03%
DOI: 10.1145/182591.182615

Incoming Non-self Citations Over Time

Authors

1. Gerd G. Hillebrand (Brown University; INRIA)
2. Paris C. Kanellakis (Brown University)

BibTeX Citation

@inproceedings{hillebrand_pods94,
        address = {New York, NY, USA},
        series = {{PODS} '94},
        title = {{Functional Database Query Languages as Typed Lambda Calculi of Fixed Order (Extended Abstract)}},
        url = {https://dl.acm.org/doi/10.1145/182591.182615},
        doi = {10.1145/182591.182615},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Hillebrand, Gerd G. and Kanellakis, Paris C.},
        year = {1994}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,805	Positive Higher-Order Queries	2010	PODS	5.4501544e-05
13,264	On Genericity and Parametricity	1996	PODS	4.9793485e-05
13,312	Tutorial: Languages for Collection Types	1994	PODS	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1,919	The Expressiveness of a Family of Finite Set Languages	1991	PODS	9.3781849e-05
2,169	Normal Forms and Conservative Properties for Query Languages over Collection Types	1993	PODS	8.9247938e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,559	A Query Language for List-Based Complex Objects	1994	PODS
2	4,523	Functional and Predicative programming in OODB's	1992	PODS
3	4,426	Languages for Relational Databases over Interpreted Structures	1997	PODS
4	13,361	A Domain-theoretic Approach to Integrating Functional and Logic Database Languages	1993	VLDB
5	3,046	Tractable Query Languages for Complex Object Databases	1991	PODS
6	8,300	Formal Semantics and Analysis of Object Queries	2003	SIGMOD
7	13,330	Investigation of Algebraic Query Optimisation for Database Programming Languages	1994	VLDB
8	13,165	Fixed-Point Query Languages for Linear Constraint Databases	2000	PODS
9	7,805	Positive Higher-Order Queries	2010	PODS
10	1,919	The Expressiveness of a Family of Finite Set Languages	1991	PODS