Find skills requirement using Postgresql

I saw this question on Stackoverflow

I have a question about a Database technique to store dependencies. I know there are out there a lot of them, but I cannot place them easily in the scheme I need. I have created simple image:





As you can see what I need is to create a tree of skills (like in games) which depends on each other. So for example if someone goes and want to have skill 8 I can tell him that he needs to first have skill 1,2 and 5.

This might be fine for hirearchial data in database, but what I cannot quite figure out is how to do this model dynamically. The problem I have is, that skills will be added all the time in all possible places in the tree. Never ending. An skills can be added on any level.

Now after this first question there is one more complication. I need the skills to have levels as well. So for example skill 1 can have 10 levels. and you can achieve skill 2 only after achieving skill 1 level 5.

For people who play games like World of Warcraft should be understandable.

One more note, Skills can be added anytime, but cannot be changed after adding. On normal basis. Just in case some of the skill would be extremely bad or something like that, then it would be removed, but that would occur just very rarely.

Thank you for suggestions, links or any other materials!

Note: On Skill #7 with skills required of 1,2,3,4,9 it should be 1,2,3,4,6,9.


I'm challenged enough to solve it, but I'm not challenged enough to solve it without CTE. With that in mind, here's my Postgresql query for that:

with recursive 
skill_list(skill_id) as
(
    select distinct skill_id from skill_req 
    where req is not null
    union
    select distinct req from skill_req
    where req is not null 
)
,skill_tree(skill_group, depend_on) as
(
    select skill_id, skill_id -- seed
    from skill_list 
 
    union 
 
    select st.skill_group, sr.req
    from skill_req sr
    join skill_tree st 
    on sr.skill_id = st.depend_on 
)
,skills_required as
(
    select skill_group, depend_on
    from skill_tree
    where skill_group <> depend_on -- remove seeds 
)
select 
 
    sl.skill_id, 
    array_agg(sr.depend_on order by depend_on) as array_version,
    array_to_string(array_agg(sr.depend_on order by depend_on), ',') as  group_concat_version

from skill_list sl
left join skills_required sr on sr.skill_group = sl.skill_id
group by sl.skill_id   

Output:

 skill_id | array_version | group_concat_version 
----------+---------------+----------------------
        1 | {NULL}        | 
        2 | {1}           | 1
        3 | {NULL}        | 
        4 | {3}           | 3
        5 | {1}           | 1
        6 | {1,2,3,4}     | 1,2,3,4
        7 | {1,2,3,4,6,9} | 1,2,3,4,6,9
        8 | {1,2,5}       | 1,2,5
        9 | {3}           | 3
       10 | {1,3,4,5,9}   | 1,3,4,5,9
(10 rows)

Live test: http://www.sqlfiddle.com/#!1/77894/1