Title :
Database query languages embedded in the typed lambda calculus
Author :
Hillebrand, Gerd G. ; Kanellakis, Paris C. ; Mairson, Harry G.
Author_Institution :
Brown Univ., Providence, RI, USA
Abstract :
It is shown how to naturally embed, in the typed λ-calculus with equality, many database query languages, including the relational calculus/algebra, inflationary Datalog, and the complex object calculus/algebra. The embeddings considered are such that a database is a λ-term coding list of tuples and a query is a λ-term which when applied to the input database normalizes to the output database. In addition, if the query expressed is a PTIME query, then the normal form can be computed in a number of reduction steps polynomial in the size of the input database. It is also shown that, for all PTIME queries, there is such an embedding in the order-three typed λ-calculus with equality
Keywords :
database theory; lambda calculus; query languages; relational algebra; PTIME query; complex object calculus/algebra; database query languages; inflationary Datalog; input database; lambda term coding list; order-three typed lambda calculus; output database; relational calculus/algebra; tuples; typed lambda calculus; Algebra; Calculus; Contracts; Database languages; Embedded computing; Instruments; Polynomials; Relational databases; Robustness;
Conference_Titel :
Logic in Computer Science, 1993. LICS '93., Proceedings of Eighth Annual IEEE Symposium on
Conference_Location :
Montreal, Que.
Print_ISBN :
0-8186-3140-6
DOI :
10.1109/LICS.1993.287575
