Re: In an RDBMS, what does "Data" mean?
Date: Thu, 01 Jul 2004 00:59:14 GMT
Message-ID: <ClJEc.170800$mz2.8599651_at_phobos.telenet-ops.be>
Marshall Spight wrote:
>
> Does anyone know of a "list calculus" or "list algebra" with a
> formal definition? It is just too simple for anyone to have
> cared about?
Yes, it exists, and, no, it is not too simple for anyone to have cared about. There are in fact lots of them. The most interesting ones are based on the the comprehension syntax.
Comprehension syntax.
Peter Buneman, Leonid Libkin, Dan Suciu, Val Tannen and Limsoon Wong.
SIGMOD Record, 23 (1994), 87-96.
Related to those are the ones based on monads.
Comprehending monads
Philip Wadler. Mathematical Structures in Computer Science, Special
issue of selected papers from 6'th Conference on Lisp and Functional
Programming, 2:461-493, 1992.
The core of XQuery is to some extent based on that. With Google and citeseer you should be able to find on-line versions. There are many many more papers on this, but these should set you in the right direction.
If you are into that sort of thing you might want to read about calculi for even more general data structures such as pomsets (partially ordered mutisets, a generalization of sets, bags and lists):
An Algebra for Pomsets
Stéphane Grumbach and Tova Milo
Proceedings of the 5th International Conference on Database Theory
191-207, 1995
Happy reading,
- Jan Hidders