Home » forums » LtU Forum

Restructuring Partitioned Normal Form Relations Without Information Loss

By itself, this paper is not related to PLT. However, it is interesting to observe how an idea of "types up to isomorphism" manifests itself in different communities - called data equivalence of (nested) relational schemes in this paper.

I wonder, how reformulation of the paper in CT terms would look like, and whether it will be data-equivalent to the original :-)

Restructuring Partitioned Normal Form Relations Without Information Loss

PS: I hope this is not too much off-topic.

By Andris Birkmanis at 2005-04-25 15:17 | LtU Forum | previous forum topic | next forum topic | other blogs | 4348 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

On topic, off topic

I hope this is not too much off-topic.

I can't make this paper out from looking at the abstract. What are nested relations? Are they relations between relations (i.e. what everyone else calls higher-order relations)? Is this meant to be similar to the 2-categorical ideas that keep appearing in PL-semantics?

By Charles A Stewart at Wed, 2005-04-27 01:03 | login or register to post comments

No categories

Is this meant to be similar to the 2-categorical ideas that keep appearing in PL-semantics?

No, not that ambitious. And even not 1.5-categorical.

Flat relations can be thought as lists (or sets, or multisets) of products of base types. Their schemas are very rigid, therefore.

Schemas of nested relations belong to algebra freely generated from base types, products, lists, and, in some variants, coproducts. Basically, we are talking algebraic data types.

One of the goals of the paper is to show under what conditions two schemas can hold the same data, or in other words, are isomorphic.

To me, this sounds like a good application for CT (and yes, many papers on nested relational model mention monads and monadic comprehensions - in fact, I find their version of monads easier to understand than that of modern tutorials :) ). Also, I wonder, whether all the research in the area of nested relational model was eclipsed by XML and its friends. Or did it kill itself by betting too much on ODBMS? Is Kleisli doing ok (other than helping to match genes :) )?

By Andris Birkmanis at Wed, 2005-04-27 06:21 | login or register to post comments

OK, I get the picture, definitely on topic

Thanks for the summary.

Schemas of nested relations belong to algebra freely generated from base types, products, lists, and, in some variants, coproducts. Basically, we are talking algebraic data types.

I'd be surprised if this didn't give rise to a CCC in the usual way, maybe even a topos, so one would get some 2-categorical structure for free.

Also, I wonder, whether all the research in the area of nested relational model was eclipsed by XML and its friends.

It sounds cleaner to me, though in defence of the XMLy way, I was at a talk by Maarten Marx that showed how lots of of the ideas in XML Schema were very natural from the POV of modal languages and frame semantics.

By Charles A Stewart at Wed, 2005-04-27 10:10 | login or register to post comments