Re: repeating groups

From: Marshall Spight <>
Date: 18 Feb 2006 22:11:44 -0800
Message-ID: <>

Jonathan Leffler wrote:
> mAsterdam wrote:
> > Marshall Spight wrote:
> >>>[...snippage...]
> >> Sure. But there are several ways out of the repeating groups problem
> >>
> >> 1) decomposing relations, aka "classical" 1NF
> >> 2) higher-than-1 cardinality attributes: lists or sets
> >
> > Aren't you jumping over the "order may have meaning" problem
> > here by taking these two together?
> It depends whether you take the OR in 'lists or sets' to be inclusive or
> exclusive, doesn't it? If it is inclusive, then lists handle the 'order
> has meaning' case and sets handle the 'order is not significant case'.
> But you've complicated the algebra - instead of just sets, you've now
> got to deal with lists and sets (and the alternatives you list below).

Yes, *exactly*!

Complicating the algebra should give us pause, but I now believe it is something that we have to do. Lists are essential; sets are essential; I am not willing to admire a language that doesn't make both of them first class. I am not convinced there is any other structure that we need to give such importance to. And lists and sets need to interoperate. Hence we have to have the unified algebra.

I've been thinking about this problem for a while. A half-assed job is remarkably easy. What is remarkably hard is to actually do a good job.

> >> 3) Fully nested relations.
> >
> > lists-of-lists? sets-of-sets? lists-of-sets? sets-of-lists?
> >
> >> Actually, 2) was something I hadn't really thought of before:
> >> add *one* level of nesting. This idea is interesting but less
> >> appealing than 3, because it is less regular. I tend to prefer
> >> orthogonal designs; they have fewer arbitrary limitations.
> Was it Hoare who said "anything in computer science that isn't recursive
> isn't any good" or words to that effect? (I found two references at
> Google to Jim Gray saying "Anything in computer science that's not
> recursive is no good", but it is not an easy expression to search for.)

An excellent expression! I had not heard that before.

> 1-level of nesting would be arbitrary and would very quickly become
> restrictive. Indeed, you'd have to be very careful not to lose the
> closure property of the algebra.


But there is the existence proof for the usefulness of one level of additional structure, and that is the special handling given to the type list-of-character. Still, I favor the recursive type approach. (I actually prefer to say "inductive".)

Marshall Received on Sun Feb 19 2006 - 07:11:44 CET

Original text of this message