Complex SQL Query: Select like tree traversal

Question

Consider the following (1:N) relationship:

[entity: user] <------ rid key ------> [entity: rid].

consider the data in both tables as:

select * from user;
user-id        rid-key
a-basa         a
b-basa         b
a.a-basa       a.a   
a.b-basa       a.b
a.a.a-basa     a.a.a
a.a.b-basa     a.a.b
a.b.a-basa     a.b.a
a.b.b-basa     a.b.b
a.b.b.a-basa   a.b.b.a
a.b.b.b-basa   a.b.b.b



select * from rid;

rid-key    parent-rid    enabled
a            null        true
b            null        true
a.a          a           true 
a.b          a           false
a.a.a        a.a         true
a.b.a        a.b         true
a.b.b        a.b         true
a.b.b.a      a.b.b       true
......
n rows

I need to design a single query (not stored procedure) which will input a user-id, and the following facts are considered:

If an user is given access to a rid, then it can also access the parent rid of the rid given - the rid itself is enabled (enabled = true).

This should continue till we reach the root rid, ie. parent rid property is null.

In above example, the list of accessible rid for the user 'a.b.b.a-basa' will be:

a.b.b.a
a.b.b
a.b

and for a.a.a-basa:

a.a.a
a.a
a

can we get this list using a single query? Any sql vendor is fine.

+1 for the question, with a loop this would have been...:) much easier, but anyway you need a query... — bonCodigo
– bonCodigo, Commented Jan 13, 2013 at 9:25
is the number of levels known? If not, I do not believe it will be possible, as SQL does not support recursion. — cha
– cha, Commented Jan 13, 2013 at 9:32
@cha: SQL (the language) supports recursion. MySQL implementation of SQL does not (only through procedures and functions). — ypercubeᵀᴹ
– ypercubeᵀᴹ, Commented Jan 13, 2013 at 9:35
And with this particular design, one doesn't even need a recursive query. It can be done with a simple one that would work in all DBMS. — ypercubeᵀᴹ
– ypercubeᵀᴹ, Commented Jan 13, 2013 at 9:41

ypercubeᵀᴹ · Accepted Answer · 2013-01-13 11:17:42Z

There are several models for Hierarchical data. Most models (like the Adjacency List) require some sort of recursion for some queries. With your design that uses the Materialized Path model, what you want is possible without a recursive query.

Tested in MySQL (that has no recursive queries), at SQL-fiddle test-mysql. It can be easily converted for other DBMS, if you modify the string concatenation part:

SELECT 
     COUNT(*)-1 AS steps_up,
     rid2.rid_key AS ancestor_rid_key
FROM 
    u2 
  JOIN
    rid 
      ON u2.rid_key = rid.rid_key
      OR u2.rid_key LIKE CONCAT(rid.rid_key, '.%')
  JOIN
    rid AS rid2 
      ON rid.rid_key = rid2.rid_key
      OR rid.rid_key LIKE CONCAT(rid2.rid_key, '.%')
WHERE
    u2.userid = 'basa'
  AND
    u2.rid_key = 'a.b.b.a' 
GROUP BY 
    rid2.rid_key, rid2.enabled 
HAVING 
    COUNT(*) + (rid2.enabled = 'true') 
  = SUM(rid.enabled = 'true') + 1 ;

It uses this view, which is not strictly needed but it shows that the user.user_id is storing data that you already have in the rid_key column.

CREATE VIEW u2 AS
SELECT 
    SUBSTRING_INDEX(user_id, '-', -1) AS userid
  , rid_key
FROM user ;

One more note is that the above query does not use the parent_rid column at all. And that I'm sure it can be further improved.

Alen Oblak · Accepted Answer · 2013-01-13 09:34:16Z

1

In Oracle, you can achieve this using a hierarhical query. Search for CONNECT BY or have a look at this article.

answered Jan 13, 2013 at 9:34

Alen Oblak

3,32515 silver badges27 bronze badges

Comments

MarkD · Accepted Answer · 2013-01-13 09:34:28Z

1

This should get the ball rolling for you. The answer works on SQL Server 2005 onwards

DECLARE @UsersRIDkey VARCHAR(10) = 'a.a.a'
;WITH UserCTE (userid, ridkey) AS
(
    SELECT 'a-basa',         'a'        UNION ALL
    SELECT 'b-basa',         'b'        UNION ALL
    SELECT 'a.a-basa',       'a.a'      UNION ALL
    SELECT 'a.b-basa',       'a.b'      UNION ALL
    SELECT 'a.a.a-basa',     'a.a.a'    UNION ALL
    SELECT 'a.a.b-basa',     'a.a.b'    UNION ALL
    SELECT 'a.b.a-basa',     'a.b.a'    UNION ALL
    SELECT 'a.b.b-basa',     'a.b.b'    UNION ALL
    SELECT 'a.b.b.a-basa',   'a.b.b.a'  UNION ALL
    SELECT 'a.b.b.b-basa',   'a.b.b.b'  
)
,RidCTE (ridkey, parentrid,    isenabled) AS
(
    SELECT 'a',            null,        1   UNION ALL
    SELECT 'b',            null,        1   UNION ALL
    SELECT 'a.a',          'a',         1   UNION ALL
    SELECT 'a.b',          'a',         0   UNION ALL
    SELECT 'a.a.a',        'a.a',       1   UNION ALL
    SELECT 'a.b.a',        'a.b',       1   UNION ALL
    SELECT 'a.b.b',        'a.b',       1   UNION ALL
    SELECT 'a.b.b.a',      'a.b.b',     1   
)
,RidHierarchyCTE AS
(
    SELECT *
    FROM RidCTE
    WHERE ridkey = @UsersRIDkey
    UNION ALL
    SELECT R.ridkey, R.parentrid, R.isenabled
    FROM RidHierarchyCTE    H
    JOIN RidCTE             R ON R.ridkey = H.parentrid
)
SELECT ridkey
FROM RidHierarchyCTE

answered Jan 13, 2013 at 9:34

MarkD

5,3361 gold badge16 silver badges22 bronze badges

1 Comment

user330315 Over a year ago

Should work for PostgreSQL and DB2 as well (apart from the variable definition). Btw: you should get used to putting the statement terminator (;) where it belongs: at the end: sqlblog.org/2009/09/03/…

DazzaL · Accepted Answer · 2013-01-13 09:43:32Z

Oracle solution:

SQL> select u.user_id, r.rid_key, r.parent_rid, r.enabled
  2    from users u
  3         inner join rid r
  4                 on r.rid_key = u.rid_key
  5   start with u.user_id = 'a.a.a-basa'
  6   connect by prior r.parent_rid = r.rid_key and prior enabled = 'true'
  7  /

USER_ID      RID_KEY PAREN ENABL
------------ ------- ----- -----
a.a.a-basa   a.a.a   a.a   true
a.a-basa     a.a     a     true
a-basa       a       null  true

SQL> select u.user_id, r.rid_key, r.parent_rid, r.enabled
  2    from users u
  3         inner join rid r
  4                 on r.rid_key = u.rid_key
  5   start with u.user_id = 'a.b.b.a-basa'
  6   connect by prior r.parent_rid = r.rid_key and prior enabled = 'true'
  7  /

USER_ID      RID_KEY PAREN ENABL
------------ ------- ----- -----
a.b.b.a-basa a.b.b.a a.b.b true
a.b.b-basa   a.b.b   a.b   true
a.b-basa     a.b     a     false

http://sqlfiddle.com/#!4/d529f/1

Collectives™ on Stack Overflow

Complex SQL Query: Select like tree traversal

4 Answers 4

Comments

Comments

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related