Re: Relational question
From: John Gilson (jag_at_acm.org)
Date: 12/14/04
- Next message: Adam Machanic: "Re: Dynamic Comma delimited output"
- Previous message: Steve Kass: "Re: Dynamic Comma delimited output"
- In reply to: Steve Kass: "Re: Relational question"
- Next in thread: Steve Kass: "Re: Relational question"
- Reply: Steve Kass: "Re: Relational question"
- Messages sorted by: [ date ] [ thread ]
Date: Tue, 14 Dec 2004 05:31:04 GMT
If one considers the question as purely a SQL question then,
yes, the two queries are equivalent but with further explanation
or qualification needed, as you noted. In purely relational terms,
the qualifications are more intrinsic to the discipline. That is, all
relational queries remove redundant duplicate rows implicitly
thus obviating the need for SQL's explicit DISTINCT but, in
general, requiring its use in an equivalent SQL query. Also,
in relational queries, joining relations A and B by stating the join
condition as simply A=B is taken to mean a natural join, that is, an
equijoin with respect to all corresponding pairs of attributes of the
same name appearing in both relations. So, assuming relations
A = (attr1, attr2)
B = (attr1, attr3),
A LEFT JOIN B ON A=B as a relational algebra expression
would be transformed into SQL as
SELECT DISTINCT A.attr1, A.attr2, B.attr1, B.attr3
FROM A LEFT JOIN B ON A.attr1=B.attr1
Note that if this were an INNER JOIN we would only need to
include one copy of each pair of duplicate attributes, e.g.,
A INNER JOIN B ON A=B as a relational algebra expression
would be transformed into SQL as either
SELECT DISTINCT A.attr1, A.attr2, B.attr3
FROM A JOIN B ON A.attr1=B.attr1
or
SELECT DISTINCT B.attr1, A.attr2, B.attr3
FROM A JOIN B ON A.attr1=B.attr1
-- JAG "Steve Kass" <skass@drew.edu> wrote in message news:%23ohSMTS4EHA.1260@TK2MSFTNGP12.phx.gbl... > True, but doesn't this show that the answer to the original poster's > question is "no", or at least "only under some circumstances" (In addition > to making this relational with DISTINCT, I think the join "a.a" in the > second join must join all columns of a with their counterparts, since > otherwise the two original joins do not even have the same sets of > attributes.) > > SK > > John Gilson wrote: > > >I think if you have each query return the same attributes and > >ensure that the result is a relation, i.e., a set and not a bag, > >then the results will be the same and hence the expressions > >relationally equivalent. > > > >select DISTINCT A.colT1A, A.colT1B, > > B.colT2A, B.colT2B, > > C.colT3A, C.colT3B > >from > > @t1 as a > > left outer join > > @t2 as b > > on a.colT1A = b.colT2A > > left outer join > > @t3 as c > > on a.colT1A = c.colT3A > > > >select DISTINCT AB.colT1A, AB.colT1B, > > AB.colT2A, AB.colT2B, > > AC.colT3A, AC.colT3B > > from ( > > select * > > from @t1 as a left outer join @t2 as b > > on a.colT1A = b.colT2A > >) as AB inner join ( > > select * > > from @t1 as a left outer join @t3 as c > > on a.colT1A = c.colT3A > >) as AC > >on AB.colT1A = AC.colT1A > > > >-- > >JAG > > > >"Steve Kass" <skass@drew.edu> wrote in message news:u0U8q8z3EHA.824@TK2MSFTNGP11.phx.gbl... > > > > > >>Hm. Then what's going on here? > >> > >>declare @t1 table(colT1A int, colT1B int) > >>declare @t2 table(colT2A int, colT2B int) > >>declare @t3 table(colT3A int, colT3B int) > >> > >>insert into @t1 values(1,1) > >>insert into @t1 values(1,2) > >>insert into @t1 values(2,3) > >> > >>insert into @t2 values(1,1) > >>insert into @t2 values(3,2) > >> > >>insert into @t3 values(2,1) > >>insert into @t3 values(4,2) > >> > >>select * > >>from > >> @t1 as a > >> left outer join > >> @t2 as b > >> on a.colT1A = b.colT2A > >> left outer join > >> @t3 as c > >> on a.colT1A = c.colT3A > >> > >> > >>select * from ( > >> select * > >> from @t1 as a left outer join @t2 as b > >> on a.colT1A = b.colT2A > >>) as AB inner join ( > >> select * > >> from @t1 as a left outer join @t3 as c > >> on a.colT1A = c.colT3A > >>) as AC > >>on AB.colT1A = AC.colT1A > >> > >>--SK > >> > >>John Gilson wrote: > >> > >> > >> > >>>"Vadim Rapp" <vrapp@nospam.polyscience.com> wrote in message > >>>news:%23H%23smvS3EHA.3388@TK2MSFTNGP15.phx.gbl... > >>> > >>> > >>> > >>> > >>>>Hello, > >>>> > >>>>are the following equivalent? > >>>> > >>>>(A LOJ B on a=b) LOJ C on a.c > >>>> > >>>>and > >>>> > >>>>(A LOJ B on a.b) Join (A LOJ C on a.c) on a.a > >>>> > >>>> > >>>>? > >>>> > >>>> > >>>>thanks, > >>>> > >>>>Vadim Rapp > >>>> > >>>> > >>>> > >>>> > >>>Yes, the two expressions above are relationally equivalent. Let's see why. > >>> > >>>A LEFT OUTER JOIN, e.g., > >>> > >>>A > >>>LEFT OUTER JOIN > >>>B > >>>ON A=B > >>> > >>>is, loosely specified, equivalent to > >>> > >>>(A > >>>INNER JOIN > >>>B > >>>ON A=B) > >>>UNION > >>>(A WHERE NOT EXISTS A=B) > >>> > >>>which we'll refer to as [1]. > >>> > >>>Let's look at the first LEFT JOIN query [2]: > >>> > >>>A > >>>LEFT OUTER JOIN > >>>B > >>>ON A=B > >>>LEFT OUTER JOIN > >>>C > >>>ON A=C > >>> > >>>This can be transformed using [1] to > >>> > >>>(A > >>>INNER JOIN > >>>B > >>>ON A=B > >>>UNION > >>>A WHERE NOT EXISTS A=B) AS AB > >>>INNER JOIN > >>>C > >>>ON AB=C > >>> > >>>UNION > >>> > >>>(A > >>>INNER JOIN > >>>B > >>>ON A=B > >>>UNION > >>>A WHERE NOT EXISTS A=B) AS AB > >>>WHERE NOT EXISTS AB=C > >>> > >>>which we'll refer to as [3]. > >>> > >>>This can then be expanded into the following four queries that are > >>>unioned: > >>> > >>>A > >>>INNER JOIN > >>>B > >>>ON A=B > >>>INNER JOIN > >>>C > >>>ON A=C > >>> > >>>UNION > >>> > >>>(A WHERE NOT EXISTS A=B) AS A > >>>INNER JOIN > >>>C > >>>ON A=C > >>> > >>>UNION > >>> > >>>(A > >>>INNER JOIN > >>>B > >>>ON A=B) AS AB > >>>WHERE NOT EXISTS AB=C > >>> > >>>UNION > >>> > >>>A WHERE NOT EXISTS A=B AND NOT EXISTS A=C > >>> > >>>which we'll refer to collectively as [4] and the constituent queries > >>>in order as [4.1], [4.2], [4.3] and [4.4]. > >>> > >>>Let's look at the second LEFT JOIN query [5]: > >>> > >>>(A > >>>LEFT OUTER JOIN > >>>B > >>>ON A=B) AS AB > >>>INNER JOIN > >>>(A > >>>LEFT OUTER JOIN > >>>C > >>>ON A=C) AS AC > >>>ON AB=AC > >>> > >>>Using the above equivalence for LEFT JOIN, [1], we can transform this > >>>into: > >>> > >>>(A > >>>INNER JOIN > >>>B > >>>ON A=B > >>>UNION > >>>A WHERE NOT EXISTS A=B) AS AB > >>>INNER JOIN > >>>(A > >>>INNER JOIN > >>>C > >>>ON A=C > >>>UNION > >>>A WHERE NOT EXISTS A=C) AS AC > >>>ON AB=AC > >>> > >>>and refer to it as [6]. > >>> > >>>Our goal will be to transform [6] into four queries that are unioned > >>>as in query [4]. Let's assume the following: > >>> > >>>J = (Inner) Join operator > >>>U = Union operator > >>>A', B', C', D', T' are all tables > >>> > >>>We can see that the query [6] is of the form > >>> > >>>(A' U B') J (C' U D') > >>> > >>>It's clear that > >>> > >>>(A' U B') J T' = (T' J A') U (T' J B') > >>> > >>>If T' = (C' U D') then > >>> > >>>(A' U B') J (C' U D') = ((C' U D') J A') U ((C' U D') J B') = > >>>(A' J C') U (A' J D') U (B' J C') U (B' J D') > >>> > >>>which we'll refer to as [7]. > >>> > >>>So we can see that the LEFT JOIN query [5] can be transformed into [6] > >>>and then into four queries that are unioned in [7]. Let's now > >>>determine whether they can be transformed into the same four unioned > >>>queries as [4]. > >>> > >>>Let's assign A', B', C' and D' to table expressions in [6]. > >>> > >>>A' = (A INNER JOIN B ON A=B) > >>>B' = (A WHERE NOT EXISTS A=B) > >>>C' = (A INNER JOIN C ON A=C) > >>>D' = (A WHERE NOT EXISTS A=C) > >>> > >>>We can now look at the individual joins in [7]: > >>> > >>>(A' J C') = (A INNER JOIN B ON A=B) AS AB > >>> INNER JOIN > >>> (A INNER JOIN C ON A=C) AS AC > >>> ON AB=AC > >>> = A > >>> INNER JOIN > >>> B > >>> ON A=B > >>> INNER JOIN > >>> C > >>> ON A=C > >>> > >>>which is equal to [4.1]. > >>> > >>>(A' J D') = (A INNER JOIN B ON A=B) AS AB > >>> INNER JOIN > >>> (A WHERE NOT EXISTS A=C) AS A > >>> ON AB=A > >>> = A > >>> INNER JOIN > >>> B > >>> ON A=B AND > >>> WHERE NOT EXISTS A=C > >>> > >>>which is equal to [4.3]. > >>> > >>>(B' J C') = (A WHERE NOT EXISTS A=B) AS A > >>> INNER JOIN > >>> (A INNER JOIN C ON A=C) AS AC > >>> ON A=AC > >>> = (A WHERE NOT EXISTS A=B) AS A > >>> INNER JOIN > >>> C > >>> ON A=C > >>> > >>>which is equal to [4.2]. > >>> > >>>(B' J D') = (A WHERE NOT EXISTS A=B) AS A1 > >>> INNER JOIN > >>> (A WHERE NOT EXISTS A=C) AS A2 > >>> ON A1=A2 > >>> = A WHERE NOT EXISTS A=B AND NOT EXISTS A=C > >>> > >>>which is equal to [4.4]. > >>> > >>>Therefore, [7], with the substitutions above, is equal to [4] and > >>>hence [2] is equal to [5]. > >>> > >>>-- > >>>JAG > >>> > >>> > >>> > >>> > >>> > >>> > > > > > > > > > >
- Next message: Adam Machanic: "Re: Dynamic Comma delimited output"
- Previous message: Steve Kass: "Re: Dynamic Comma delimited output"
- In reply to: Steve Kass: "Re: Relational question"
- Next in thread: Steve Kass: "Re: Relational question"
- Reply: Steve Kass: "Re: Relational question"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
