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: 1032
Venue: PODS
Year: 1994
Pagerank: 5.8384765e-05
Overall Rank: 6,563 | 54.98%
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,654	Positive Higher-Order Queries	2010	PODS	5.5746273e-05
12,974	On Genericity and Parametricity	1996	PODS	5.093636e-05
13,022	Tutorial: Languages for Collection Types	1994	PODS	5.093636e-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,864	The Expressiveness of a Family of Finite Set Languages	1991	PODS	9.5928463e-05
2,130	Normal Forms and Conservative Properties for Query Languages over Collection Types	1993	PODS	9.1244275e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,467	A Query Language for List-Based Complex Objects	1994	PODS
2	4,422	Functional and Predicative programming in OODB's	1992	PODS
3	4,336	Languages for Relational Databases over Interpreted Structures	1997	PODS
4	13,071	A Domain-theoretic Approach to Integrating Functional and Logic Database Languages	1993	VLDB
5	2,986	Tractable Query Languages for Complex Object Databases	1991	PODS
6	8,120	Formal Semantics and Analysis of Object Queries	2003	SIGMOD
7	13,040	Investigation of Algebraic Query Optimisation for Database Programming Languages	1994	VLDB
8	12,875	Fixed-Point Query Languages for Linear Constraint Databases	2000	PODS
9	7,654	Positive Higher-Order Queries	2010	PODS
10	1,864	The Expressiveness of a Family of Finite Set Languages	1991	PODS