Re: Extending my question. Was: The relational model and relational algebra - why did SQL become the industry standard?

From: Steve Kass <>
Date: Thu, 13 Feb 2003 18:28:12 -0500
Message-ID: <b2h9jb$p0h$>

I didn't read the whole thread, but in the right context, the bags are functions, and intersect, union, etc. are all well-defined.

Definition: A multiset M over a domain U is a function with domain U and range the set of non-negative integers.

We say that the element x is in M if M(x) > 0. We say that the element x appears in M with multiplicity k, if M(x) = k We say that M = M' for two multisets M and M' on domains U and U' respectively if M(x) = M'(x) for all x in the intersection of U and U' and M(x) = 0 when x is not in U, and M'(x) = 0 when x is not in U'.

Functions are well-defined in terms of sets also, subsets of U x Z where (x,n) and (x,m) both in a function f implies n = m (single-valuedness).

It makes no sense to take the union of two functions, but it does make sense to take the sum (union all), min (intersection), and other operations.

Just define things carefully and it's all much easier. If you think the intersection
of two multisets, one containing two S's and one containing 3 should be a multiset containing 6 S's, then see if it the product operation f*g(x) = f(x)*g(x)

has useful properties for modeling the real world. I don't see why you would
call something like that intersect, though.

As for what laws hold for multisets, you just go figure out which ones do. Matrix multiplication is not commutative, but that doesn't make matrices "bad"
or useless. It's just something you need to know.

Steve Kass
Drew University

Mikito Harakiri wrote:

>"Lauri Pietarinen" <> wrote in message
>>For instance, you may have learned set-theoretic laws such as A
>>formally the "distributive law of intersection over union." This law
>>holds for sets, but not for bags.
>I wonder why A INTESECT B row multiplicities are not multiplied in the Bag's
>INTESECT definition. Well,
>{<Smith, 20>, <Smith, 20>} INTERSECT {<Smith, 20>,<Smith, 20>, <Smith, 20>}
>= {<Smith, 20>,<Smith, 20>, <Smith, 20>,<Smith, 20>,<Smith, 20>, <Smith,
>might seem counterintutive, but we don't have to appeal to layman's common
>sence, right? Just make the definition that is consistent with algebraic
>rules, and adjust "common sence" to it. Or, am I missing some pitfall?
Received on Fri Feb 14 2003 - 00:28:12 CET

Original text of this message