12 Replies Latest reply: Feb 12, 2013 7:27 AM by Spooky RSS

    hierarchical query

    Spooky
      Hi!
      I have Oracle 11g R2 XE database.

      I've created table "person", and populated it with some sample data.
      Here are DDL and DML statements:
      CREATE TABLE person (id NUMBER PRIMARY KEY,
                           first_name VARCHAR2(30) NOT NULL,
                           last_name VARCHAR2(30) NOT NULL,
                           gender VARCHAR2(1),
                           mother_id NUMBER REFERENCES person (id),
                           father_id NUMBER REFERENCES person (id)
                           )
      / 
      INSERT INTO person (id, first_name, last_name, gender)
      VALUES (1, 'John', 'Stone', 'M')
      / 
      INSERT INTO person (id, first_name, last_name, gender)
      VALUES (2, 'Joana', 'Stone', 'F')
      / 
      INSERT INTO person
      VALUES (3, 'Martin', 'Stone', 'M', 2, 1)
      / 
      INSERT INTO person
      VALUES (4, 'Jeff', 'Stone', 'M', 2, 1)
      / 
      INSERT INTO person
      VALUES (5, 'Billy', 'Stone', 'F', 2, 1)
      / 
      INSERT INTO person (id, first_name, last_name, gender)
      VALUES (6, 'Diana', 'Stone', 'F')
      / 
      INSERT INTO person
      VALUES (7, 'Dean', 'Stone', 'M', 6, 3)
      / 
      INSERT INTO person
      VALUES (8, 'Marry', 'Stone', 'F', 6, 3)
      / 
      INSERT INTO person (id, first_name, last_name, gender)
      VALUES (9, 'Tina', 'Stone', 'F')
      / 
      INSERT INTO person
      VALUES (10, 'Jerry', 'Stone', 'M', 9, 7)
      /
      INSERT INTO person
      VALUES (11, 'Anita', 'Stone', 'F', NULL, NULL)
      /
      INSERT INTO person
      VALUES (12, 'Andy', 'Stone', 'M', 11, 4)
      /
      INSERT INTO person
      VALUES (13, 'Scott', 'Stone', 'M', 9, 7);
      I need hierarchical query to find are two persons relatives. That is, do they have same ancestor(s) and who are those ancestors.

      E.g.
      --Here I want to find do Jerry Stone (id = 10) and Billy Stone (id = 5) have any same ancestor.
      
      SELECT CONNECT_BY_ROOT first_name || ' ' || last_name as main_ancestor
      FROM person
      WHERE LEVEL > 1 and id = 10
      CONNECT BY (PRIOR id = mother_id or father_id = prior id)
      INTERSECT
      SELECT CONNECT_BY_ROOT first_name || ' ' || last_name as main_ancestor
      FROM person
      WHERE LEVEL > 1 and id = 5
      CONNECT BY (PRIOR id = mother_id or father_id = prior id)
      
      Result is:
      MAIN_ANCESTOR                                               
      -------------------------------------------------------------
      Joana Stone                                                   
      John Stone    
      The problem is, if I put Jerry Stone (id = 10) and his brother Scott Stone (13), the query gives me all same ancestors, that is
      MAIN_ANCESTOR                                               
      -------------------------------------------------------------
      Dean Stone                                                    
      Diana Stone                                                   
      Joana Stone                                                   
      John Stone                                                    
      Martin Stone                                                  
      Tina Stone  
      Is there any way to change the query that the result for this wolud be Dean and Tina Stone, which are their parents.
      All in all, I have to find first same ancestor or ancestors of two given persons.

      Hope you understand the question.
      If anyone have an idea please let me know.

      Thanks!

      Edited by: Spooky on 2013.02.12 13:25
        • 1. Re: hierarchical query
          jeneesh
          May be a join?
          with t1 as
          (    
              select connect_by_root first_name || ' ' || last_name as main_ancestor,level lvl
              from person
              where level > 1 and id = 10
              connect by (prior id = mother_id or father_id = prior id)
          ),
          t2 as
          (
              select connect_by_root first_name || ' ' || last_name as main_ancestor,level lvl 
              from person    
              where level > 1 and id = 13
              connect by (prior id = mother_id or father_id = prior id)
          ),
          join_data as
          (
              select t1.main_ancestor,row_number() over(order by least(t1.lvl,t2.lvl)) rn
              from t1,t2
              where t1.main_ancestor = t2.main_ancestor
          )
          select main_ancestor
          from join_data
          where rn <= 2;
          
          MAIN_ANCESTOR                                               
          -------------------------------------------------------------
          Dean Stone                                                    
          Tina Stone  
          Edited by: jeneesh on Feb 12, 2013 6:26 PM
          Assumed that the relation can be in different levels..
          • 2. Re: hierarchical query
            BluShadow
            SQL> ed
            Wrote file afiedt.buf
            
              1  select main_ancestor
              2  from (
              3        select main_ancestor
              4              ,case when lvl = min(lvl) over () then 1 else 0 end as top
              5        from (
              6              select level as lvl, first_name || ' ' || last_name as main_ancestor
              7              from   person
              8              connect by (id = prior mother_id or id = prior father_id)
              9              start with id = 10
             10              INTERSECT
             11              select level as lvl, first_name || ' ' || last_name as main_ancestor
             12              from   person
             13              connect by (id = prior mother_id or id = prior father_id)
             14              start with id = 13
             15             )
             16       )
             17* where top = 1
            SQL> /
            
            MAIN_ANCESTOR
            -------------------------------------------------------------
            Dean Stone
            Tina Stone
            Edited by: BluShadow on 12-Feb-2013 12:54
            Not sure this is a valid solution, as it assumes the relations are at the same level.... still thinking about it.
            • 3. Re: hierarchical query
              jeneesh
              And one more clarification will be required (apart from LEVEL):

              What about different persons having same name?

              ideally you should "INTERSECT" the IDs and then find out the corresponding names..
              • 4. Re: hierarchical query
                Spooky
                Yes jeneesh, i will use id's here...
                • 5. Re: hierarchical query
                  BluShadow
                  Here's one way if you want the 'nearest' common ancestors...
                  SQL> ed
                  Wrote file afiedt.buf
                  
                    1  select id, main_ancestor
                    2  from (
                    3        select id, min_lvl, main_ancestor
                    4              ,dense_rank() over (order by min_lvl) as rnk
                    5        from (
                    6              select id, least(per1_lvl,per2_lvl) as min_lvl, main_ancestor, count(*) as cnt
                    7              from (
                    8                    select id, level as per1_lvl, 999 as per2_lvl, first_name || ' ' || last_name as main_ancestor
                    9                    from   person
                   10                    connect by (id = prior mother_id or id = prior father_id)
                   11                    start with id = 10
                   12                    UNION ALL
                   13                    select id, 999, level as per2_lvl, first_name || ' ' || last_name as main_ancestor
                   14                    from   person
                   15                    connect by (id = prior mother_id or id = prior father_id)
                   16                    start with id = 13
                   17                   )
                   18              group by id, least(per1_lvl,per2_lvl), main_ancestor
                   19              having count(*) = 2
                   20             )
                   21        )
                   22* where rnk = 1
                  SQL> /
                  
                          ID MAIN_ANCESTOR
                  ---------- -------------------------------------------------------------
                           7 Dean Stone
                           9 Tina Stone
                  and just change the rank to a descending order if you want the common ancestors (which usually will be the top of the tree)...
                  SQL> ed
                  Wrote file afiedt.buf
                  
                    1  select id, main_ancestor
                    2  from (
                    3        select id, min_lvl, main_ancestor
                    4              ,dense_rank() over (order by min_lvl desc) as rnk
                    5        from (
                    6              select id, least(per1_lvl,per2_lvl) as min_lvl, main_ancestor, count(*) as cnt
                    7              from (
                    8                    select id, level as per1_lvl, 999 as per2_lvl, first_name || ' ' || last_name as main_ancestor
                    9                    from   person
                   10                    connect by (id = prior mother_id or id = prior father_id)
                   11                    start with id = 10
                   12                    UNION ALL
                   13                    select id, 999, level as per2_lvl, first_name || ' ' || last_name as main_ancestor
                   14                    from   person
                   15                    connect by (id = prior mother_id or id = prior father_id)
                   16                    start with id = 13
                   17                   )
                   18              group by id, least(per1_lvl,per2_lvl), main_ancestor
                   19              having count(*) = 2
                   20             )
                   21        )
                   22* where rnk = 1
                  SQL> /
                  
                          ID MAIN_ANCESTOR
                  ---------- -------------------------------------------------------------
                           1 John Stone
                           2 Joana Stone
                  • 6. Re: hierarchical query
                    jeneesh
                    Spooky wrote:
                    Yes jeneesh, i will use id's here...
                    Is your issue resolved by any of the above solutions?
                    • 7. Re: hierarchical query
                      Spooky
                      Thanks guys!

                      I have a large set of data, and trying now with both your answers.
                      In some examples they work as they should, and in some they aren't. :)

                      Looking for solution now...

                      If you come up with something new please respond.
                      • 8. Re: hierarchical query
                        Spooky
                        Give me a moment to try some examples jeneesh...
                        • 9. Re: hierarchical query
                          jeneesh
                          Spooky wrote:
                          Give me a moment to try some examples jeneesh...
                          No worries.. Take your time..

                          :)
                          • 10. Re: hierarchical query
                            Frank Kulash
                            Hi,

                            Depending on what you mean by "first"
                            WITH     got_ancestors     AS
                            (
                                 SELECT     id, first_name, last_name
                                 ,     CONNECT_BY_ROOT id     AS start_id
                                 ,     LEVEL     AS lvl
                                 FROM     person
                                 START WITH     id IN (5, 10)
                                 CONNECT BY     id IN (PRIOR mother_id, PRIOR father_id)
                                 ORDER BY     LEVEL
                            )
                            ,     got_r_num     AS
                            (
                                 SELECT     id, first_name, last_name
                                 ,     RANK () OVER (ORDER BY  lvl)     AS r_num
                                 FROM     got_ancestors
                                 WHERE     start_id  = 5
                                 AND     id        IN (
                                                SELECT     id
                                                FROM     got_ancestors
                                                WHERE     start_id     = 10
                                                     )
                            )
                            SELECT     id, first_name, last_name
                            FROM     got_r_num
                            WHERE     r_num     = 1
                            ;
                            This returns the common ancestors who are closest to 5 (that is, have the fewest gereations between themselves and 5). That is, it will return an ancestor who is 3 levels above 5 in preference to one who is 4 levels above 5 and 2 levels above 10.
                            There are lots of other ways to define "first". For many of them, the query above will work by changing the ORDER BY clause in the RANK function.

                            Whatever you do, it will be faster if you make the CONNECT BY query a Bottom-Up Query , like the one above, where you can use a START WITH clause.
                            • 11. Re: hierarchical query
                              BluShadow
                              Slight correction to mine...
                              SQL> ed
                              Wrote file afiedt.buf
                              
                                1  select id, main_ancestor
                                2  from (
                                3        select id, min_lvl, main_ancestor
                                4              ,dense_rank() over (order by min_lvl) as rnk
                                5        from (
                                6              select id, min(least(per1_lvl,per2_lvl)) as min_lvl, main_ancestor, count(*) as cnt
                                7              from (
                                8                    select id, level as per1_lvl, 999 as per2_lvl, first_name || ' ' || last_name as main_ancestor
                                9                    from   person
                               10                    connect by (id = prior mother_id or id = prior father_id)
                               11                    start with id = 10
                               12                    UNION ALL
                               13                    select id, 999, level as per2_lvl, first_name || ' ' || last_name as main_ancestor
                               14                    from   person
                               15                    connect by (id = prior mother_id or id = prior father_id)
                               16                    start with id = 13
                               17                   )
                               18              group by id, main_ancestor
                               19              having count(*) = 2
                               20             )
                               21        )
                               22* where rnk = 1
                              SQL> /
                              
                                      ID MAIN_ANCESTOR
                              ---------- -------------------------------------------------------------
                                       7 Dean Stone
                                       9 Tina Stone
                              and with id 10 and 5...
                              SQL> ed
                              Wrote file afiedt.buf
                              
                                1  select id, main_ancestor
                                2  from (
                                3        select id, min_lvl, main_ancestor
                                4              ,dense_rank() over (order by min_lvl) as rnk
                                5        from (
                                6              select id, min(least(per1_lvl,per2_lvl)) as min_lvl, main_ancestor, count(*) as cnt
                                7              from (
                                8                    select id, level as per1_lvl, 999 as per2_lvl, first_name || ' ' || last_name as main_ancestor
                                9                    from   person
                               10                    connect by (id = prior mother_id or id = prior father_id)
                               11                    start with id = 10
                               12                    UNION ALL
                               13                    select id, 999, level as per2_lvl, first_name || ' ' || last_name as main_ancestor
                               14                    from   person
                               15                    connect by (id = prior mother_id or id = prior father_id)
                               16                    start with id = 5
                               17                   )
                               18              group by id, main_ancestor
                               19              having count(*) = 2
                               20             )
                               21        )
                               22* where rnk = 1
                              SQL> /
                              
                                      ID MAIN_ANCESTOR
                              ---------- -------------------------------------------------------------
                                       2 Joana Stone
                                       1 John Stone
                              • 12. Re: hierarchical query
                                Spooky
                                Thank's all!

                                You're been very hepful.

                                Frank and BluShadow solutions work for me. I can't make both of your answers correct, so sorry about that. :)