Loading...
Please wait, while we are loading the content...
Similar Documents
Database Query Languages Embedded in the Typed Lambda Calculus (1993)
| Content Provider | CiteSeerX |
|---|---|
| Author | Mairson, Harry G. Hillebrand, Gerd G. Kanellakis, Paris C. |
| Abstract | We investigate the expressive power of the typed -calculus when expressing computations over finite structures, i.e., databases. We show that the simply typed -calculus can express various database query languages such as the relational algebra, fixpoint logic, and the complex object algebra. In our embeddings, inputs and outputs are -terms encoding databases, and a program expressing a query is a -term which types when applied to an input and reduces to an output. Our embeddings have the additional property that PTIME computable queries are expressible by programs that, when applied to an input, reduce to an output in a PTIME sequence of reduction steps. Under our database input-output conventions, all elementary queries are expressible in the typed -calculus and the PTIME queries are expressible in the order-5 (order-4) fragment of the typed -calculus (with equality). |
| File Format | |
| Journal | PROCEEDINGS 8TH IEEE LICS |
| Publisher Date | 1993-01-01 |
| Access Restriction | Open |
| Subject Keyword | Finite Structure Typed Lambda Calculus Typed Calculus Ptime Computable Query Relational Algebra Reduction Step Ptime Query Expressive Power Fixpoint Logic Elementary Query Database Input-output Convention Complex Object Algebra Ptime Sequence Database Query Language Embedded Various Database Query Language Additional Property |
| Content Type | Text |
| Resource Type | Proceeding |
