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

From: Steve Kass <skass_at_drew.edu>
Date: Mon, 17 Feb 2003 18:22:11 -0500
Message-ID: <b2rqnp\$1tj\$1_at_slb2.atl.mindspring.net>

>"Paul" <pbrazier_at_cosmos-uk.co.uk> wrote in message
>
>
>
>
>>OK suppose I have an employee "relation" which is a multiset.
>>I have two employees called John Smith, in the same dept on the same
>>salary.
>>So my multi-relation contains two outwardly identical tuples:
>>("John Smith", 10, 20000)
>>("John Smith", 10, 20000)
>>
>>Now one of the John Smiths has a sex-change and becomes Jane Smith.
>>
>>How does the user update only one of the rows?
>>Surely it's impossible because the two rows are only distinguished
>>internally?
>>
I think you are confusing your employees with your model. If we have only the two employees named John Smith, in department 10 with salary 20000, and we are storing this information in a multiset, we have only _one_ fact, not two: "There are two John Smiths in department 10 with salary 20000". Two employees, but only one fact.

If we wish to change our data so that it now represents two facts:
"There is one John Smith in department 10 with salary 20000". "There is one Jane Smith in department 10 with salary 20000".

we do so without any difficulty. There are many ways to devise a physical representation of our multiset, and how we transform it depends what the representation is. An easy one to use, where "fact" corresponds to something physical, is to store multiplicities, so that we initially have

"John Smith", 10, 20000, 2

and then have

"John Smith", 10, 20000, 1
"Jane Smith", 10, 20000, 1

We've gone from one fact to two facts, so we have two "rows", neither of which matches the original row. I don't think there's any mystery or difficulty here, so long as you understand that there is only one fact per distinct "row" in the multiset, and that fact includes the row data and its multiplicity, whether or not that single fact corresponds to two "non-facts", such as employees or data packets in the real-world model and/or the physical model. As soon as you violate the conceptual model there will surely be lots of problems.

>>
>>
>
>The fact
>
>("John Smith", 10, 20000)
>
>in multiset theory is not a complete predicate. Therefore, we can't just
>blindly modify it.
>
>The <name, dept> is obviously a unique key. The question should be how do
>we impose constraints in the multiset theory.
>
>
>
>>Can't multisets always be defined in terms of sets?
>>So you could for example define a multiset [a,a,b,c,d,d,d]
>>as the set {(a,1),(a,2),(b,3),(c,4),(d,5),(d,6),(d,7)}
>>(where (x,y) denotes an ordered pair which you could define as the set
>>{{x},{x,y}} if you wanted)
>>
>>
>
>The biggest problem with (x,y)={{x},{x,y}} definition is that it's not
>associative:
>
><a,<b,c>> != <<a,b>,c>
>

What isn't associative? What does <> represent? What does it mean for a definition to be associative? Associativity is a property of binary operations. What binary operation are you talking about here?

>
>Therefore, we can't consistently define ordered tuple with 3 components.
>This is why the above definition is just a toy that is never used in
>practice. Once again, Set Reduction doesn't work!
>
>
Huh? Many definitions are possible, of course. We could represent (x,y,z) in any of these ways, I think (I'm sure I messed up the brackets, though):

```{{1,{x}},{2,{y}}, {3,{z}}
{{x},{y,{y}},{z,{z},{{z}}}}
{{x},{x,{y,{y,z}}}}  -- This is the one I'd call the most natural extension.
{{x,{x,y}},{{x,{x,y}},z}}  -- This is the alternative that bothers you..

```

Are you saying that a concept is hogwash unless there is a unique way for it to be presented in terms of sets? That's hogwash!

>
>
>>or maybe {(a,2),(b,1),(c,1),(d,3)} would be better because it doesn't
>>add extra information (sequential order). Which is really the same as
>>adding the extra "count" column I guess.
>>
>>
>
>In multiset theory we are studying why
>
>{(a,1),(a,2),(b,3),(c,4),(d,5),(d,6),(d,7)}
>
>and
>
>{(a,2),(b,1),(c,1),(d,3)}
>
>are equivalent. In the set theory, however, there is nothing special about
>these 2 representations.
>
So?

>
>
>
>>So multisets really just are syntactic shorthand. Now I suppose
>>ultimately everything is syntactic shorthand for set theory :) but I'm
>>not convinced that at the logical level the advantages of multisets
>>outweigh the disadvantages. Quite possibly it might be different for
>>the physical level though.
>>
>>
>
>My problem is that I'm so frequently blurring distinction between logical
>and physical, that distinction of logical and physical levels is no longer a
>driving principle. It seems to be a price to pay for more poweful
>computation model. Could this model be reasonably "declarative" that is the
>question.
>
>
I think you've lost track entirely of any question here, unless you still think there is no well-founded set-based model for multisets. If you still think that, try again to give a reason why, other than that there is more than one well-founded model. "There is no model, because there are two models."??

>
>
>>Well this is straying off-topic I guess since databases are
>>necessarily finite so a suitably large finite set of integers would
>>suffice.
>>But what if you wanted a multiset of even greater cardinality than the
>>reals? e.g. the set of all subsets of the reals?
>>
>>
>
>No, I rather meant that nonnegative integer set is so obviously
>algebraically nonclosed that it might ultimately show up. Cardinalities and
>powersets in the set theory -- "set of integer sets" -- are notoriously
>useless for anything more practical than measuring the length of Turing
>tape.
>
>
>
There should be no problem modeling multisets where the multiplicities can come from any set of cardinal numbers with addition that contains an additive identity and is closed under addition. You can find a handy set of cardinals that includes 2^(2^aleph_0) if that's what you want.

SK

>
>
Received on Tue Feb 18 2003 - 00:22:11 CET

Original text of this message