I am making a simple todo app (Laravel4/MySQL) and it needs the ability to make tasks and subtasks (limiting it to max. 3 levels)
I was checking out Nested-Set implementations for Laravel here and here. Is it an overkill for my requirement?
I'm guessing nested-sets saves hierarchy data globally (against say, a per-user or per-project basis) and are better for items like a multilevel menu with a limited number of items. What is the best implementation for my case, where hundreds of users would have a multitude of projects and each having hundreds of multilevel tasks/sub-tasks? Would there be unnecessary traversals/overheads if I implement nested-sets for my case?
My answer would be Closure Table.
I read about a few ways to solve hierarchies in the book SQL Antipatterns (https://books.google.com/books/about/SQL_Antipatterns.html?id=Ghr4RAAACAAJ). I definitely recommend reading the book.
My favorite way to implement hierarchies is via closure tables. This is a great source that explains them in depth: http://technobytz.com/closure_table_store_hierarchical_data.html.
To summarize: make one table that keeps track of the actual items in the hierarchy (e.g. task_id, task_description, time_opened, etc.) and another table to track the relations. This second table should have things such as task_id and parent_task_id. The best trick with these tables is to keep track of every parent-child relation, not just the direct parent-child relations. So if you have Task 1 that has a child task, Task 2, and Task 2 has a child task, Task 3, keep track of the parent child relation between Task 1 and Task 2 as well as between Task 1 and Task 3.
The tradeoff with closure tables vs nested sets is that closure tables consume more memory, but have less computing needed when doing operations. This is because you store every relation between every task (this takes memory) and the simple availability of all of these relationships makes it faster for the RDBMS to get information about the relationships.
Hope this helps!
I recommend to read the Managing hierarchical data in mysql article.
Briefly,
CREATE TABLE category(
category_id INT AUTO_INCREMENT PRIMARY KEY,
name VARCHAR(20) NOT NULL,
parent INT DEFAULT NULL
);
INSERT INTO category VALUES(1,'ELECTRONICS',NULL),(2,'TELEVISIONS',1),(3,'TUBE',2),
(4,'LCD',2),(5,'PLASMA',2),(6,'PORTABLE ELECTRONICS',1),(7,'MP3 PLAYERS',1),(8,'FLASH',7),
(9,'CD PLAYERS',6),(10,'2 WAY RADIOS',6);
SELECT * FROM category ORDER BY category_id;
+-------------+----------------------+--------+
| category_id | name | parent |
+-------------+----------------------+--------+
| 1 | ELECTRONICS | NULL |
| 2 | TELEVISIONS | 1 |
| 3 | TUBE | 2 |
| 4 | LCD | 2 |
| 5 | PLASMA | 2 |
| 6 | PORTABLE ELECTRONICS | 1 |
| 7 | MP3 PLAYERS | 6 |
| 8 | FLASH | 7 |
| 9 | CD PLAYERS | 6 |
| 10 | 2 WAY RADIOS | 6 |
+-------------+----------------------+--------+
The query retrieve all your data:
SELECT t1.name AS lev1, t2.name as lev2, t3.name as lev3, t4.name as lev4
FROM category AS t1
LEFT JOIN category AS t2 ON t2.parent = t1.category_id
LEFT JOIN category AS t3 ON t3.parent = t2.category_id
WHERE t1.name = 'ELECTRONICS';
The retrieving only leaf names:
SELECT t1.name FROM
category AS t1 LEFT JOIN category as t2
ON t1.category_id = t2.parent
WHERE t2.category_id IS NULL;
The retrieving one path:
SELECT t1.name AS lev1, t2.name as lev2, t3.name as lev3, t4.name as lev4
FROM category AS t1
LEFT JOIN category AS t2 ON t2.parent = t1.category_id
LEFT JOIN category AS t3 ON t3.parent = t2.category_id
WHERE t1.name = 'ELECTRONICS' AND t3.name = 'FLASH';