Paper: Database query languages embedded in the typed lambda calculus (at LICS 1993)

Authors: Gerd G. Hillebrand Paris C. Kanellakis Harry G. Mairson

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

BibTeX

  @InProceedings{HillebrandKanellaki-Databasequerylangua,
    author = 	 {Gerd G. Hillebrand and Paris C. Kanellakis and Harry G. Mairson},
    title = 	 {Database query languages embedded in the typed lambda calculus},
    booktitle =  {Proceedings of the Eighth Annual IEEE Symposium on Logic in Computer Science (LICS 1993)},
    year =	 {1993},
    month =	 {June}, 
    pages =      {332--343},
    location =   {Montreal, Canada}, 
    publisher =	 {IEEE Computer Society Press}
  }