Re: Notions of Type

Vadim Tropashko wrote:
> paul c wrote:

>> D&D claim their algebra can also
>> be reduced to two operators as well, take your choice, NAND and REMOVE
>> or NOR and REMOVE.

Second point on page 8, http://www.dcs.warwick.ac.uk/~hugh/TTM/APPXA.pdf.

Actually, they include TCLOSE as well, so if transitive closure is included, then I guess there are three ops, but I suppose the same is true of TA.

I assume the six classical ops are select/restrict, union, product, join, divide (plus project), don't know if it's necessary to write them all out, as D&D do the same in the above and many other sources show how their ops can be replaced with nor or nand, eg., http://en.wikipedia.org/wiki/NAND

> One reason for a doubt is that Relational Algebra has one operator that
> still can't be expressed in terms of union and join -- the set
> difference.

It's been a long time since I read about circuit theory, but their claim seems to be well-known in that field and both were pre-dated long before. I presume one or the other is why they posit nor or nand, although they don't end up going with either. It's true that they use union to define sum/Insert and depend on negation for difference/Delete, but each can be expressed in terms of the negation of the other - I think they use both union and join only to make their definitions as short as possible. As long as you have negation, or negated or/and, then I believe difference and sum are possible and you don't need both.

Therefore, if D&D can reduce all 6 operations to just 2,
> then it's quite an achievement.

Although there are aspects of TA that are over my head, I think there is certainly a similarity with D&D. Sometimes I think TA's generalized union could just as well be called Project!

p Received on Sun Aug 20 2006 - 02:20:57 CEST