Oracle FAQ | Your Portal to the Oracle Knowledge Grid |
Home -> Community -> Usenet -> comp.databases.theory -> Re: Requirements for update languages?
lauri.pietarinen_at_atbusiness.com (Lauri Pietarinen) wrote in message news:<e9d83568.0211120512.2b06ec2f_at_posting.google.com>...
> One interesting consequense of bags is that
> the cartesian product cannot be defined.
>
> <quote from http://www.dbdebunk.com/cjddtdt_2.htm>
>
>
> The first problem concerns Cartesian product. Part of the standard's
> explanation of the SQL FROM clause reads as follows:
>
> [The] result of the <from clause> is the ... Cartesian product of the
> tables identified by [the] <table reference>s [in that <from
> clause>]. The ... Cartesian product, CP, is the multiset of all rows
> R such that R is the concatenation of a row from each of the
> identified tables ... .
>
> Note, therefore, that CP is not well-defined! -- the fact that the
> standard goes on to say that "The cardinality of CP is the product
> of the cardinalities of the identified tables" notwithstanding.
> Consider the tables T1 and T2 shown below:
>
> T1 T2
> +----+ +----+
> ¦ C1 ¦ ¦ C2 ¦
> +----¦ +----¦
> ¦ 0 ¦ ¦ 1 ¦
> ¦ 0 ¦ ¦ 2 ¦
> +----+ +----+
>
> Either of the following fits the above definition for "the" Cartesian
> product CP of T1 and T2 (that is, either one could be "the"
> multiset referred to):
>
> CP1 CP2
> +---------+ +---------+
> ¦ C1 ¦ C2 ¦ ¦ C1 ¦ C2 ¦
> +----+----¦ +----+----¦
> ¦ 0 ¦ 1 ¦ ¦ 0 ¦ 1 ¦
> ¦ 0 ¦ 1 ¦ ¦ 0 ¦ 2 ¦
> ¦ 0 ¦ 2 ¦ ¦ 0 ¦ 2 ¦
> ¦ 0 ¦ 2 ¦ ¦ 0 ¦ 2 ¦
> +---------+ +---------+
>
> As an exercise, I suggest you try your hand at fixing up the
> wording of the standard appropriately. If you do try this exercise, I
> believe you'll find you're inevitably led into using the language of
> sets, not bags, in order to get around the errors and ambiguities.
>
>
> </quote>
Cartesian Product on bags is easily defined if we allow "unproject" operations. In your example we need to add a sequence columns C01 to T1 and C02 to T2 so that both T1(C01,C1) and T2(C02,C2) are sets. Then, calculate the cartesian product of the sets and project away C01 and C02 from the result.
Proposition. The Cartesian Product as defined above is a well defined operation; it doesn't depend on the details of the "unproject" operation.
The other way to legitimate bags is a theory of distributions: each distribution is a generalization of a bag. Cartesian Product is just a product of 2 distributions. Given
T1: {0->2} and T2: {1->1, 2->1}
then
T1*T2 = {<0,1> -> 2, <0,2> -> 2}
Note, that aggregation fits naturally into distribution theory, and
not
into logic or set theory.
Received on Tue Nov 12 2002 - 13:42:02 CST