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.
Dates: Tuesday 2 August, 2016, 13:30-15:10
Place: JAIST, Collaboration room 7 (I-56) (Access: http://www.jaist.ac.jp/english/location/access.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".