Mysql technique for Skill dependencies

Question

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!

Answer 1

As you can see what I need is to create a tree of skills (like in games) which depends on each other.

I need the skills to have levels as well. So for example skill 1 can have 10 levels.

This means that you will need a table to store the skill and the max level of the skill, basically:

create table skills(
  skill_id integer,
  skill_name varchar(500) not null,
  skill_max_level integer not null,
  primary key(skill_id));

And you will need to set the dependecy with an optional level required:

create table skills_depend
( skill_id integer
, skill_depend integer
, level_depend integer 
, primary key(skill_id, skill_depend)
, foreign key (skill_id)
  references skills (skill_id)
, foreign key (skill_depend)
  references skills (skill_id) );

The query will depend on what you want to check (e.g. if the user have the pre-requisites to adquire a skill).

Combined this with the user level and the skills that he already have I think that's a start point.

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.

This requirement you will need to control in your application level (let the user only add or delete the skill).

---

You can play with this on the SQLFiddle

Answer 2

I'm challenged enough to solve the problem, but I'm not challenged enough to solve it in MySQL. With that in mind, here's the Postgresql version of your problem:

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

Data:

CREATE TABLE skill_req
    (skill_id int, req int);

INSERT INTO skill_req
    (skill_id, req)
VALUES   
   (2, 1),

   (4, 3),

   (5, 1),

   (6, 4), 
   (6, 2),

   (7, 6),   
   (7, 9),

   (8, 2),
   (8, 5),

   (9, 3),

   (10, 4),
   (10, 5),
   (10, 9);

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