Re: Relational question

From: Steve Kass (skass_at_drew.edu)
Date: 12/15/04 

Date: Wed, 15 Dec 2004 00:43:47 -0500

Well said.

SK

John Gilson wrote:

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

Relevant Pages

  • Re: Official Status of SQLServer 2005 ADP
    ... I have said that the support for SQL passthrough ... queries under MDB was bad and worst than the one offered by ADP while you ... > attempt to "pass through" every Access query against a linked ODBC ...
    (microsoft.public.access.adp.sqlserver)
  • Re: 2 crosstabs
    ... I have no problem using one query as the source for a line graph. ... problems comes when I want to combine both queries into one line graph. ... sense of it to generate my own SQL: ... Orders INNER JOIN (Products INNER JOIN [Order ...
    (microsoft.public.access.queries)
  • Re: Massive Large Query Issues
    ... Project Budgets: Entered at the Capital Request level, ... installed (One install is typically $100,000 plus the cost of the equpment, ... install SQL Server. ... Often, a collection of queries ...
    (microsoft.public.access.queries)
  • Re: Massive Large Query Issues
    ... Project Budgets: Entered at the Capital Request level, ... install SQL Server. ... of queries? ... make of the query you provided is to roll it up into a subsequent ...
    (microsoft.public.access.queries)
  • Re: "Query Too Complex" Errors
    ... few dozens of queries, in the middle of which there's a long chain of ... we've been having a lot of those "Query Too ... some of the complexity in the SQL ... SQL statement you are working on. ...
    (microsoft.public.access.forms)