Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

I would like to make a union of two tables that are actually in a hierarchical constellation.

How would I write that in relational algebra? Say table A is the parent of B in a 1:n relationship.

First I do a selection on A and then I want to only make a union with these entries in B that would be in a join with selection on A.

I would like to write it the way that a database would evaluate it.

Is there such a thing as a conditional union?

share|improve this question
add comment

3 Answers

up vote 2 down vote accepted

I'm not sure what you mean by a UNION. Please explain!

If you are referring to the UNION operator that combines rowsets "vertically" then this might do the trick for you:

SELECT
   CASE X.Which WHEN 1 THEN A.Column1 ELSE B.Column1 END Column1,
   CASE X.Which WHEN 1 THEN A.Column2 ELSE B.Column2 END Column2,
   ...
FROM
   TableA A
   CROSS JOIN (
      SELECT 1
      UNION ALL SELECT 2
   ) X (Which)
   LEFT JOIN TableB B
      ON B.AId = A.Id
      AND X.Which = 2
WHERE
  X.Which = 1
  OR B.AId IS NOT NULL

This will do a single scan operation on both tables, rather than the at least two scans on table A for the following query:

SELECT
   A.Column1,
   A.Column2,
   ...
FROM
   TableA A
UNION ALL
SELECT
   B.Column1,
   B.Column2,
   ...
FROM
   TableA A
   INNER JOIN TableB B
      ON B.AId = A.Id

Now it's possible when you said UNION that you simply meant a mathematical intersection, in which case the last SELECT above will be what you need—a simple JOIN operation:

SELECT
   A.Whatever,
   B.Whatever,
   ...
FROM
   TableA A
   INNER JOIN TableB B
      ON B.AId = A.Id

UPDATE

Apparently, some DB engines have different capabilities. For example, the last two queries in my example script below (reportedly) have very different execution plans in MySQL, but they are identical in SQL Server, which selects the best access path by changing join order, left/right input position, and moving conditions around as needed. It is not stuck doing JOINs first and WHEREs second.

To support my claim about SQL server, I cooked up some test script. This loads a parent table with 1 million rows and a child table with approximately 2.5 million rows. The individual rows we're looking for get put nicely deep into the stack (totally unnecessary, I know, but hey, it was fun).

CREATE DATABASE Proof;
GO
ALTER DATABASE Proof SET RECOVERY SIMPLE --no need to bloat the tran log
USE Proof;
GO
CREATE TABLE books (
   id int identity(1,1) NOT NULL CONSTRAINT PK_books PRIMARY KEY CLUSTERED,
   title varchar(100)
);

CREATE TABLE characters (
   book_id int not null constraint fk_characters foreign key references books (id),
   name varchar(100),
   CONSTRAINT PK_characters PRIMARY KEY CLUSTERED (book_id, name)
);

SET NOCOUNT ON;
DECLARE
   @book int,
   @rowcount int,
   @lastbookid int,
   @which int;

SET @book = Coalesce((SELECT Count(*) FROM books), 0);
SET @which = 1;
WHILE 1 = 1 BEGIN
   INSERT books
   SELECT Left(Replicate('-' + Convert(varchar(11), @book + v.number), 20), 100)
   FROM master.dbo.spt_values v
   WHERE   
      v.type = 'P'
      AND v.number < 1000000 - @book;

   SELECT @rowcount = @@rowcount, @lastbookid = scope_identity();
   IF @rowcount = 0 BREAK;
   SET @book = @book + @rowcount;

   INSERT characters
   SELECT
      B.id, Left(Replicate('|' + Convert(varchar(11), v.number), 20), 100)
   FROM
      books B
      CROSS JOIN master.dbo.spt_values v
   WHERE
      B.id BETWEEN @lastbookid - @rowcount + 1 AND @lastbookid
      AND v.type = 'P'
      AND v.number BETWEEN 1 AND Convert(int, Rand() * 4) + 1;


   IF @book >= 250000 AND @which = 1 BEGIN -- put them deep inside
      INSERT books VALUES ('The Frog and the Sorcerer');
      INSERT characters
      SELECT scope_identity(), name
      FROM (
          SELECT 'Frog' UNION ALL SELECT 'Sorcerer'
      ) x (name);
      SET @book = @book + 1;
      SET @which = @which + 1;
   END
   ELSE IF @book >= 500000 AND @which = 2 BEGIN
      INSERT books VALUES ('The Princess and the Pea');
      INSERT characters
      SELECT scope_identity(), name
      FROM (
          SELECT 'Princess' UNION ALL SELECT 'Pea'
      ) x (name);
      SET @book = @book + 1;
      SET @which = @which + 1;
   END
   ELSE IF @book >= 750000 AND @which = 3 BEGIN
      INSERT books VALUES ('Two Ways to Tango');
      INSERT characters
      SELECT scope_identity(), name
      FROM (
          SELECT 'Tango Alpha' UNION ALL SELECT 'Tango Omega'
      ) x (name);
      SET @book = @book + 1;
      SET @which = @which + 1;
   END;
END;
GO
SET SHOWPLAN_ALL ON;
GO
SELECT A.title,B.name
FROM
    books A
    LEFT JOIN characters B
        ON A.id = B.book_id
WHERE
    A.title IN ('Two Ways to Tango', 'The Frog and the Sorcerer')
OPTION (MAXDOP 1);
GO
SET SHOWPLAN_ALL OFF;
GO
SET SHOWPLAN_ALL ON;
GO
SELECT A.title, B.name
FROM
    (
        SELECT id, title FROM books A
        WHERE title IN ('Two Ways to Tango', 'The Frog and the Sorcerer')
    ) A
    LEFT JOIN characters B
        ON A.id = B.book_id
OPTION (MAXDOP 1);
GO
SET SHOWPLAN_ALL OFF;
GO
USE master;
GO
DROP DATABASE Proof;

The two execution plans are identical. I suppressed parallelism because it was just unneeded noise (plans were still the same). Here is the result of the SHOWPLAN with the query removed (the only part that was different).

StmtText                                                                                                                                                                                                                               StmtId NodeId Parent PhysicalOp           LogicalOp            Argument                                                                                                                                                                                               DefinedValues         EstimateRows EstimateIO EstimateCPU  AvgRowSize TotalSubtreeCost OutputList              Warnings Type     Parallel EstimateExecutions
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ------ ------ ------ -------------------- -------------------- ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ --------------------- ------------ ---------- ------------ ---------- ---------------- ----------------------- -------- -------- -------- ------------------
                                                                                                                                                                                                                                       1      1      0      NULL                 NULL                 1                                                                                                                                                                                                      NULL                  2.994377     NULL       NULL         NULL       12.71991         NULL                    NULL     SELECT   0        1
  |--Nested Loops(Left Outer Join, OUTER REFERENCES:([A].[id]))                                                                                                                                                                        1      2      1      Nested Loops         Left Outer Join      OUTER REFERENCES:([A].[id])                                                                                                                                                                            NULL                  2.994377     0          0.0000125165 151        12.71991         [A].[title], [B].[name] NULL     PLAN_ROW 0        1
       |--Clustered Index Scan(OBJECT:([Proof].[dbo].[books].[PK_books] AS [A]), WHERE:([Proof].[dbo].[books].[title] as [A].[title]='The Frog and the Sorcerer' OR [Proof].[dbo].[books].[title] as [A].[title]='Two Ways to Tango')) 1      3      2      Clustered Index Scan Clustered Index Scan OBJECT:([Proof].[dbo].[books].[PK_books] AS [A]), WHERE:([Proof].[dbo].[books].[title] as [A].[title]='The Frog and the Sorcerer' OR [Proof].[dbo].[books].[title] as [A].[title]='Two Ways to Tango') [A].[id], [A].[title] 1            10.73646   1.100157     114        11.83662         [A].[id], [A].[title]   NULL     PLAN_ROW 0        1
       |--Clustered Index Seek(OBJECT:([Proof].[dbo].[characters].[PK_characters] AS [B]), SEEK:([B].[book_id]=[Proof].[dbo].[books].[id] as [A].[id]) ORDERED FORWARD)                                                                1      4      2      Clustered Index Seek Clustered Index Seek OBJECT:([Proof].[dbo].[characters].[PK_characters] AS [B]), SEEK:([B].[book_id]=[Proof].[dbo].[books].[id] as [A].[id]) ORDERED FORWARD                                                                [B].[name]            2.994377     0.003125   0.0001602938 50         0.003285294      [B].[name]              NULL     PLAN_ROW 0        0
share|improve this answer
1  
I trust that you are right about SQL-Server producing identical plans for the 2 versions of the query. But the SHOWPLAN when tables have so few rows is not proof, I think. –  ypercube Feb 9 '12 at 8:33
    
@ypercube One counterfactual disproves the claim. Period. To satisfy your idle curiosity, I'm happy to test with a million rows if you like. –  ErikE Feb 9 '12 at 17:32
    
@ypercube There you go. 1 million parent rows, 2.5 million child rows. Same execution plan. If you want me to add or remove indexes, add columns, change data, or whatever, please suggest and I will retest. –  ErikE Feb 9 '12 at 18:56
    
Nice. 1M rows is enough for me :) –  ypercube Feb 10 '12 at 1:45
    
@ypercube Are you sure? I mean, a billion rows really wouldn't be that hard. Just 30 minutes instead of 3 minutes for the script. :) –  ErikE Feb 10 '12 at 2:23
show 5 more comments

If I understood the question well, your task can be solved by using recursive queries. Oracle (see and SQLServer (2005 and higher) both support it. Surely, different RDMS vendors use a slightly different syntax.

share|improve this answer
add comment

Do you mean intersect? Consider relvars Customers and Orders with a correspondence where one customer has zero, one or many orders (I wouldn't refer to this as a hierarchy, though). To find customers who have orders:

( Customers { customer_ID } ) INTERSECT ( Orders { customer_ID } ) 

I rather suspect this isn't what you mean, in which please amend your question to add example data and expected results.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.