Re: Exciting Papers on Normalization in list-based data models

Dawn M. Wolthuis wrote:
>
> Excellent! I can see that I'm missing some notation conventions I'll have
> to dig up to get all the way through it (for example, L[N] in the definition
> of a list-valued attribute doesn't provide me with enough information until
> the next def which tells me the domain, so I gather that L[N] is the label
> for any vector consisting of elements in the domain of N)

It's the type. This is sort of the standard way to define complex values. In Def. 1 they tell you that you start with the basic (atomic if you will) types like

   Name with dom(Name) the domain of Names    Address with dom(Address) the domain of Address    ... et cetera

Then in Def. 2 they tell you that from these basic types you can build more complex ones. So L(Name, Address) denotes a type for a tuple with two fields. The type L[Address] denotes the type for a list of addresses. And you can recursively nest these. So the type L[L(Name,L[Address])] denotes the type for lists of tuples where these tuples contain a Name and a list of Adresses.

So in Def. 3 they then actually tell you which values belong to these types, which here means that the dom function for basic types is generalized for the types defined in Def. 2.

> I love the domain of lamda as {ok} -- I don't know if there is a history for
> that or if these guys made that up (to indicate null as a value, if I'm
> reading it right).

They need it to make their algebraic approach work. But it's acutally pretty standard, although usually it takes the shape of the empty tuple type. So they probably could have used the type L() for that. It's not really a null but rather a special value which has no further meaning, and unless you also intruduce union types you cannot say that the type of a certain attribute is "Name OR \lambda".

> I sure would have preferred a nice little business data processing example
> over the nucleotide sequences but the multivalue dependency work looks right
> up my alley, if only I understood it. smiles. --dawn

Well, at least it should tell you that the real experts on database theory are a lot less squeamish about data models with lists than some of the relational fundamentalists would like.

• Jan Hidders