Machiavelli(ID:1496/mac010)Fucntional database languagePeter Buneman & Atsushi Ohori, U Pennsylvania, 1989. An extension of Standard ML based on orthogonal persistence. Related languages
References: in [ACM] Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data, Portland, OR, May 1989 view details semantic simplicity of relational algebra, and the expressive power of unrestricted programming languages. Its main computational engine is structural recursion on sets. All programming is done within a "nicely" typed lambda calculus, as in Machiavelli. A guiding principle is that how queries are implemented is as important as whether they can be implemented. As in relational algebra, the meaning of any relation transformer is guaranteed to be a total map taking finite relations to finite relations. A naturally restricted class of programs written with structural recursion has precisely the expressive power of the relational algebra. The same programming paradigm scales up, yielding query languages for the complex-object model. Beyond that, there are, for example, efficient programs for transitive closure and we are also able to write programs that move out of sets, and then perhaps back to sets, as long as we stay within a (quite flexible) type system. The uniform paradigm of the language suggests positive expectations for the optimization problem. In fact, structural recursion yields finer grain programming therefore we expect that lower-level, and therefore better optimizations will be feasible. in Proceedings of 3rd International Workshop on Database Programming Languages (1991) view details over non-free datatypes such as lists, bags and sets. Programs written in this style can lack a meaning in the sense that their outputs may be sensitive to the choice of input expression. We are, thus, naturally lead to a set-theoretic denotational semantics with partial functions. We set up a logic for reasoning about the definedness of terms and a deterministic and terminating evaluator. The logic is shown to be sound in the model, and its recursion free fragment is shown to be complete for proving definedness of recursion free programs. The logic is then shown to be as strong as the evaluator, and this implies that the evaluator is compatible with the provable equivalence between different set (or bag, or list) expressions. Oftentimes, the same non-free datatype may have different presentations, and it is not clear a priori whether programming and reasoning with the two presentations are equivalent. We formulate these questions, precisely, in the context of alternative presentations of the list, bag, and set datatypes and study some aspects of these questions. In particular, we establish back-and-forth translations between the two presentations, from which it follows that they are equally expressive, and prove results relating proofs of program properties, in the two presentations. in Proceedings of 3rd International Workshop on Database Programming Languages (1991) view details in Proceedings of 3rd International Workshop on Database Programming Languages (1991) view details with the relational algebra expresses exactly the queries over ordered relational databases which are NC-computable. At a finer level, we relate k nested uses of recursion exactly to ACk, k >= 1. We also give corresponding results for complex objects. in Proceedings of ACM Symposium on Principles of Database Systems (PODS) 1994 view details Collection types such as sets, bags (multisets), lists, complex objects, nested relations, arrays, and certain kinds of trees are widely used in non-traditional database applications and must therefore be properly supported by modern database systems. The study of languages for these structures has only recently received serious attention. Can we find languages that naturally support these structures in the same way that relational languages support relational databases? Practical database languages are based on first-order logic, and much research has been devoted to augmentations of first-order logic to produce languages of increased expressive power, but with the added demands of dealing with collection types, we must ask whether we are stretching this computational paradigm beyond its breaking point. This tutorial will suggest that we can cope with a rich variety of collection type semantics by looking at the operations that are "naturally'' (in the sense of category theory) associated with the data structures involved. Surprisingly, category theory concepts that one might dismiss as too esoteric lead to a succession of useful languages for collection types, that includes equivalents of familiar languages for relational databases, such as relational algebra, nested relational algebra and datalog. As an extra bonus, this approach provides a basis for language syntax that is closely related to that of practical database query languages such as SQL. Moreover, this approach provides equational logics which serve to study certain classes of query optimizations. Finally, there are some intriguing connections between these languages and query complexity classes, both sequential and parallel. in Proceedings of ACM Symposium on Principles of Database Systems (PODS) 1994 view details in Proceedings of ACM Symposium on Principles of Database Systems (PODS) 1994 view details in Proceedings of ACM Symposium on Principles of Database Systems (PODS) 1994 view details in Proceedings of ACM Symposium on Principles of Database Systems (PODS) 1994 view details in Proceedings of ACM Symposium on Principles of Database Systems (PODS) 1994 view details in Proceedings of ACM Symposium on Principles of Database Systems (PODS) 1994 view details |