Machiavelli(ID:1496/mac010)

Fucntional database language 


Peter Buneman & Atsushi Ohori, U Pennsylvania, 1989. An extension of Standard ML based on orthogonal persistence.


Related languages
SML => Machiavelli   Extension of
Machiavelli => CPL   Influence

References:
  • Ohori, Atsushi; Buneman, Peter; Tannen, Val "Database Programming in Machiavelli, a Polymorphic Language with Static Type Inference" view details Abstract: Machiavelli is a polymorphically typed programming language in the spirit of ML, but supports an extended method of type inferencing that makes its polymorphism more general and appropriate for database applications. In particular, a function that selects a field ƒ of a records is polymorphic in the sense that it can be applied to any record which contains a field ƒ with the appropriate type. When combined with a set data type and database operations including join and projection, this provides a natural medium for relational database programming. Moreover, by implementing database objects as reference types and generating the appropriate views — sets of structures with “identity” — we can achieve a degree of static type checking for object-oriented databases.

          in [ACM] Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data, Portland, OR, May 1989 view details
  • Tannen, Val; Buneman, Peter; Naqvi, S. "Structural Recursion as a Query Language" view details Abstract: We propose a programming paradigm that tries to get close to both the
    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
  • Tannen, Val; Subrahmanyam, R. "Logical and Computational Aspects of Programming with Sets/Bags/Lists" Proceedings of 18th International Colloquium on Automata, Languages, and Programming LNCS 510 1991 view details Abstract: We study issues that arise in programming with primitive recursion
    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
  • Tannen, Val; Buneman, Peter; Wong, Limsoon "Naturally Embedded Query Languages" International Conference on Database Theory (ICDT) 1992 view details Abstract: We investigate the properties of a simple programming language whose main computational engine is structural recursion on sets. We describe a progression of sublanguages in this paradigm that (1) have increasing expressive power, and (2) illustrate robust conceptual restrictions thus exhibiting interesting additional properties. These properties suggest that we consider our sublanguages as candidates for "query languages''. Viewing query languages as restrictions of our more general programming language has several advantages. First, there is no "impedance mismatch'' problem; the query languages are already there, so they share common semantic foundation with the general language. Second, we suggest a uniform characterization of nested relational and complex-object algebras in terms of some surprisingly simple operators; and we can make comparisons of expressiveness in a general framework. Third, we exhibit differences in expressive power that are not always based on complexity arguments, but use the idea that a query in one language may not be polymorphically expressible in another. Fourth, ideas of category theory can be profitably used to organize semantics and syntax, in particular our minimal (core) language is a well-understood categorical construction: a cartesian category with a strong monad on it. Finally, we bring out an algebraic perspective, that is, our languages come with equational theories, and categorical ideas can be used to derive a number of rather general identities that may serve as optimizations or as techniques for discovering optimizations.
          in Proceedings of 3rd International Workshop on Database Programming Languages (1991) view details
  • Suciu, Dan; Tannen, Val "A Query Language for NC" view details Abstract: We show that a form of divide and conquer recursion on sets together
    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
  • Tannen, Val "Languages for Collection Types" Tutorial view details Abstract:
    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
  • Buneman, Peter; Naqvi, Shamim; Tannen, Val, Wong, Limsoon "Principles of Programming with Collection Types" Theoretical Computer Science (1995) view details
          in Proceedings of ACM Symposium on Principles of Database Systems (PODS) 1994 view details
  • Davidson, Susan; Overton, Chris; Tannen, Val; Wong, Limsoon "BioKleisli: A Digital Library for Biomedical Researchers" Journal of Digital Libraries 1997 view details
          in Proceedings of ACM Symposium on Principles of Database Systems (PODS) 1994 view details
  • Lellahi, Kazem; Tannen, Val "A Calculus for Collections and Aggregates" LNCS 1290: Category Theory and Computer Science, Proceedings of the 7th Int'l Conference, CTCS'97 (1997) view details
          in Proceedings of ACM Symposium on Principles of Database Systems (PODS) 1994 view details
  • Buneman, Peter; Crabtree, Jonathan; Davidson, Susan; Tannen, Val; Wong, Limsoon "BioKleisli" Bioinformatics, edited by S. Letovsky (Kluwer Academic Publishers) 1998 view details
          in Proceedings of ACM Symposium on Principles of Database Systems (PODS) 1994 view details
  • Popa, Lucian; Tannen, Val "Chase and axioms for PC queries and dependencies" Technical Report MS-CIS-98-34 1998 view details
          in Proceedings of ACM Symposium on Principles of Database Systems (PODS) 1994 view details