Categories of Classes for Collection Types

• Eugenio Moggi (University of Genova)

* This series of lectures is held as a part of JSPS Core-to-Core Program, A. Advanced Research Networks, and EU FP7 Marie Curie Actions IRSES project CORCON.

(core2core, https://corcon.net/)

Dates: Tuesday 2 August, 2016, 13:30-15:10

Place: JAIST, Collaboration room 7 (I-56) (Access: https://www.jaist.ac.jp/english/top/access/index.html)

Speaker: Eugenio Moggi (University of Genova)

*Tuesday 2 August, 2016, 13:30-15:10*

LECTURE 1: Categories of Classes for Collection Types

ABSTRACT. Collection types have been proposed by Buneman and others (in the '90) as a way to capture database query languages in a typed setting. In 1998 Manes introduced the notion of collection monad on the category S of sets as a suitable semantics for collection types. The canonical example of collection monad is the finite powerset monad Pf.

In order to account for the algorithmic aspects of database languages, the category S is unsuitable, and should be replaced with other categories, whose arrows are maps computable by "low complexity" algorithms. We propose "realizability for DSL" (Domain Specific Languages), where the starting point is a monoid C of endomaps on a set D, instead of a combinatory algebra on D, as a way to get such categories by constructions like the category A[C] of "assemblies".

To get Pf in a systematic way we borrow ideas from AST (Algebraic Set Theory, started by Joyal and Moerdijk in the '90), where they fix a notion of "small" map in a category of "classes", and read "small" as "finite".