Re: More on lists and sets

Collection algebras has been popular in the 90s, although I'm not sure how much progress has been made.

Here is a little bit more development on the idea that we loose some algebraic properties along the chain sets --> bags --> lists. As it has been established elsewhere, we can focus at only two operations: natural join and inner union. For simplicity, let's even more restrict ourselves to the relations with the same header which has one attribute only. In this case the operations are familiar intersection "/\" and union "\/".

The sets obey the following laws:

A \/ A = A
A \/ B = B \/ A
(A \/ B) \/ C = A \/ (B \/ C)

A /\ A = A
A /\ B = B /\ A
(A /\ B) /\ C = A /\ (B /\ C)

Bags compromise idempotence:

A \/ A = 2A != A
A \/ B = B \/ A
(A \/ B) \/ C = A \/ (B \/ C)

A /\ A = A^2 != A
A /\ B = B /\ A
(A /\ B) /\ C = A /\ (B /\ C)

How do we define union and intersection for lists? Union is easy: it's list concatenation. Therefore, we have
A \/ A != A
A \/ B != B \/ A
(A \/ B) \/ C = A \/ (B \/ C)

In other words, lists compromise commutativity for a union. What about intersection? More important, how do we even define it?

Definition. List intersection is a cartesian product with equijoin of the list nodes and lexicographic order. Example: 1->2->1 /\ 2->1->2 = 2->1->1->2

2        2
^           ^
|             \

|      \
2        2

   1 -> 2 -> 1

It is remarkable that list intersection laws mimic the ones for the union:
A /\ A != A
A /\ B != B /\ A
(A /\ B) /\ C = A /\ (B /\ C)

(I didn't proove the last one, but withessed it on the example only:-)
Received on Tue Mar 21 2006 - 02:38:58 CET