Re: Relational question

From: John Gilson (jag_at_acm.org)
Date: 12/13/04 

Date: Mon, 13 Dec 2004 05:16:57 GMT

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
> >
> >
> >
> >

Relevant Pages

  • Re: Weekly crosstab query
    ... queries for the other information and then linking the queries together by ... ensure that the queries return data for the same set of employees. ... Query Two uses query one in place of the OvertimeTracking table ... INNER JOIN qPrior ON ...
    (microsoft.public.access.queries)
  • Re: how can i make this query run faster
    ... your query is very hard to read, ... that this LEFT JOIN can be changed to INNER JOIN. ... An outer join usually means that the optimizer has to use a ... specific access path, ...
    (microsoft.public.sqlserver.programming)
  • Re: Query Error Message
    ... Are you building a UNION query? ... You can simplify it by removing the ORDER BY in each of the three queries ... > Single_Insured.) INNER JOIN (Single_Commissions INNER JOIN ...
    (microsoft.public.access.queries)
  • RE: Aggregates, Joins, I am totally stuck on this issue
    ... a left outer join it makes it an inner join? ... I have two aggregate queries which are grouped on ... >> query and then create an append query which puts the results of this master ... >> a LEFT OUTER JOIN and run it and what do it get? ...
    (microsoft.public.access.queries)
  • Re: Getting the High and Low Tides from a Series of Data
    ... queries, sub queries and virtual table) will extract all occurrences ... of an extremum. ... I prefer method 3, a total query, because it ... FROM myTable INNER JOIN query1 ...
    (microsoft.public.access.gettingstarted)