Archive for the ‘Multisets’ Category

Generic Multiset Programming for Language-Integrated Querying

Saturday, September 10th, 2011

More than one resource on generic multiset programming by Fritz Henglein and Ken Friis Larsen:

Paper: Generic Multiset Programming for Language-Integrated Querying

Video: Generic Multiset Programming for Language-Integrated Querying

From the introduction to the paper:

We introduce a library for generic multiset programming. It supports algebraic programming based on Codd’s original relational algebra with select (filter), project (map), cross product, (multi)set union and (multi)set di fference as primitive operators and extends it with SQL-style functions corresponding to GROUP BY, SORT BY, HAVING, DISTINCT and aggregation functions.

It generalizes the querying core of SQL as follows: Multisets may contain elements of arbitrary fi rst-order data types, including references (pointers), recursive data types and nested multisets. It contains an expressive embedded domain specifi c language for user-defi nable equivalence and ordering relations. And it allows in principle arbitrary user-defi ned functions for selection, projection and aggregation.

Under Contributions:

In this paper we provide a library for SQL-style programming with multisets that

  • supports all the classic features of the data query sublanguage of SQL;
  • admits multisets of any element type, including nested multisets and trees;
  • admits user-definable equivalences (equijoin conditions), predicates, and functions;
  • admits naïaut;ve programming with cross-products, but avoids spending quadratic time on computing them;
  • offers an object-oriented (object-method-parameters) syntax using infix binary operators;
  • and is easy to implement.

To demonstrate this we include the complete source code (without basic routines for generic discrimination reported elsewhere) and a comple of paradigmatic examples.

Looks interesting to me!