Home

Feedback

FAQ

Getting Started

Discussions

Site operation discussions

Recent Posts

(new topic)

Departments

Courses

Research Papers

Design Docs

Quotations

Genealogical Diagrams

Archives

Today I suddenly had an epiphany: nested SQL statements are monads in the way that they enforce orders in execution.

Could someone tell me I'm correct? :-)

Monads are typically equated with single-threadedness, and are therefore used as a technique for incorporating imperative features into a purely functional language. Category theory monads have little to do with single-threadedness; it is the sequencing imposed by composition that ensures single-threadedness. In a Wadler-ised monad this is a consequence of bundling the Kleisli star and flipped compose into the bind operator. There is nothing new in this connection. Peter Landin in his Algol 60 used functional composition to model semi-colon.

Therefore, it is a mistake to think of any construction that enforces the execution order as a monad. Incidentally, Applicatives also enforce execution order, and some applicatives are not monads (for example, code-generating applicatives, sort of an antiquotation facilities). To see if something is a monad, identify the two necessary operations and check the monad laws. By the same token, to see if something is a monoid, find an operation that combines the two instances of the thing and check if it is an associative and there is the unit element.

I'm not ever-so sure whether you mean 'nested' or just sequenced?

[This is more complex than sequential statements in procedural languages, because SQL typically operates in a multi-user environment. So as well as making the updated database 'available' to the next statement in sequence, it must also be 'published' to all other users of the database. That is, each statement is evaluated in the IO monad. And then we'd have to start into talking about commitment control ...]

UPDATE r SET x = MAX(SELECT z FROM s WHERE r.y = s.y)

There's no implied order of execution of the sub-select, and the server is at liberty (for example) to tackle the rows of r in parallel, and could scan the rows of s 'at random'.

In Haskell: x = max (max z1 z2) (max z3 z4)

There's no implied order of execution. Again, the code could evaluate the z's and the max's in parallel.

x = maximum (map z ys) -- where z is a field selector

In the Haskell there's no monad in sight, but there's a kinda order of execution because both maximum and map are folds, so apply from head to tail as it were. (And maximum has to evaluate the whole list to find the geatest element -- but the folds only generate thunks; the order of evaluation thereof is undefined.)

There is a close correspondence between the core of SQL (not including aggregation or sorting) and a monad, and hence between SQL and list comprehensions. This was originally observed by Trinder and Wadler, and exploited by Buneman, Libkin, Tannen, and Wong to define the influential database languages NRC (theory) and Kleisli (practice). The same insights underly Microsoft's LINQ.

P Trinder, P Wadler. Improving list comprehension database queries. TENCON'89. Fourth IEEE Region 10 International Conference, 186-192

P. Buneman, L. Libkin, D. Suciu, V. Tannen, and L. Wong. Comprehension Syntax. SIGMOD Record, 23(1):87-96, March 1994.

Limsoon Wong. Kleisli, a functional query system. Journal of Functional Programming 10(1): 19-56 (2000).

Erik Meijer, Brian Beckman, Gavin M. Bierman: LINQ: reconciling object, relations and XML in the .NET framework. SIGMOD Conference 2006: 706.

The following paper is probably relevant:

www.informatik.uni-kiel.de/~mh/papers/PADL08.pdf

In the paper they use an I/O monad to model inserts/updates.

## Recent comments

2 hours 36 min ago

2 hours 55 min ago

3 hours 28 min ago

5 hours 23 sec ago

13 hours 41 min ago

13 hours 41 min ago

1 day 13 min ago

1 day 4 hours ago

1 day 6 hours ago

1 day 7 hours ago