Hierarchical/tree database for directories path in filesystem

Question

I want to store the directories (present on the disk) into a database, maintaining their hierarchical/tree structure.

Here's a figure:

                         (ROOT)
                       /        \ 
                    Dir2        Dir3
                   /    \           \
                 Dir4   Dir5        Dir6
                 /          
               Dir7

I am using the SQLite database.

Please suggest me:

the SQL query to store above structure in SQLite database, and
a query to retrieve full path of the directory when I select one.

i.e. suppose I select Dir7 then I should get the full path like ROOT/Dir2/Dir4/Dir7

A closure table might be a good choice. Have a look at [What is the most efficient/elegant way to parse a flat table into a tree?](http://stackoverflow.com/questions/192220/what-is-the-most-efficient-elegant-way-to-parse-a-flat-table-into-a-tree#192462), and also see [Bill Karwin's](http://stackoverflow.com/users/20860/bill-karwin) slides on [Models for hierarchical data](http://www.slideshare.net/billkarwin/models-for-hierarchical-data) — Mike, Jul 23 '11 at 19:01
The subject came up again on the SQLite mainling list, and Eduardo Morras (re)pointed out this SQLite vtable extension to deal with hierarchy from the SQLite repo itself: 1) http://www.sqlite.org/src/artifact/636024302cde41b2bf0c542f81c40c624cfb7012 2) http://www.sqlite.org/src/finfo?name=ext/misc/closure.c — ddevienne, Oct 17 '14 at 07:14

Mike · Accepted Answer · 2017-09-10T11:54:27.330

Here's a quick closure table example for SQLite. I've not included the statements for inserting items into an existing tree. Instead, I've just created the statements manually. You can find the insert and delete statements in the Models for hierarchical data slides.

For the sake of my sanity when inserting the IDs for the directories, I renamed the directories to match their IDs:

        (ROOT)
      /        \ 
    Dir2        Dir3
    /    \           \
  Dir4   Dir5        Dir6
  /          
Dir7

Create tables

CREATE TABLE `filesystem` (
  `id` INTEGER,
  `dirname` TEXT,
  PRIMARY KEY (`id`)
);

CREATE TABLE `tree_path` (
  `ancestor` INTEGER,
  `descendant` INTEGER,
  PRIMARY KEY (`ancestor`, `descendant`)
);

Insert directories into filesystem table

INSERT INTO filesystem (id, dirname) VALUES (1, 'ROOT');
INSERT INTO filesystem (id, dirname) VALUES (2, 'Dir2');
INSERT INTO filesystem (id, dirname) VALUES (3, 'Dir3');
INSERT INTO filesystem (id, dirname) VALUES (4, 'Dir4');
INSERT INTO filesystem (id, dirname) VALUES (5, 'Dir5');
INSERT INTO filesystem (id, dirname) VALUES (6, 'Dir6');
INSERT INTO filesystem (id, dirname) VALUES (7, 'Dir7');

Create the closure table paths

INSERT INTO tree_path (ancestor, descendant) VALUES (1, 1);
INSERT INTO tree_path (ancestor, descendant) VALUES (1, 2);
INSERT INTO tree_path (ancestor, descendant) VALUES (1, 3);
INSERT INTO tree_path (ancestor, descendant) VALUES (1, 4);
INSERT INTO tree_path (ancestor, descendant) VALUES (1, 5);
INSERT INTO tree_path (ancestor, descendant) VALUES (1, 6);
INSERT INTO tree_path (ancestor, descendant) VALUES (1, 7);
INSERT INTO tree_path (ancestor, descendant) VALUES (2, 2);
INSERT INTO tree_path (ancestor, descendant) VALUES (2, 4);
INSERT INTO tree_path (ancestor, descendant) VALUES (2, 5);
INSERT INTO tree_path (ancestor, descendant) VALUES (2, 7);
INSERT INTO tree_path (ancestor, descendant) VALUES (3, 3);
INSERT INTO tree_path (ancestor, descendant) VALUES (3, 6);
INSERT INTO tree_path (ancestor, descendant) VALUES (4, 4);
INSERT INTO tree_path (ancestor, descendant) VALUES (4, 7);
INSERT INTO tree_path (ancestor, descendant) VALUES (5, 5);
INSERT INTO tree_path (ancestor, descendant) VALUES (6, 6);
INSERT INTO tree_path (ancestor, descendant) VALUES (7, 7);

Run some queries

# (ROOT) and subdirectories
SELECT f.id, f.dirname FROM filesystem f
  JOIN tree_path t
    ON t.descendant = f.id
 WHERE t.ancestor = 1;

+----+---------+
| id | dirname |
+----+---------+
|  1 | ROOT    |
|  2 | Dir2    |
|  3 | Dir3    |
|  4 | Dir4    |
|  5 | Dir5    |
|  6 | Dir6    |
|  7 | Dir7    |
+----+---------+


# Dir3 and subdirectories
SELECT f.id, f.dirname
  FROM filesystem f
  JOIN tree_path t
    ON t.descendant = f.id
 WHERE t.ancestor = 3;

+----+---------+
| id | dirname |
+----+---------+
|  3 | Dir3    |
|  6 | Dir6    |
+----+---------+

# Dir5 and parent directories
SELECT f.id, f.dirname
  FROM filesystem f
  JOIN tree_path t
    ON t.ancestor = f.id
 WHERE t.descendant = 5;

+----+---------+
| id | dirname |
+----+---------+
|  1 | ROOT    |
|  2 | Dir2    |
|  5 | Dir5    |
+----+---------+

# Dir7 and parent directories
SELECT f.id, f.dirname
  FROM filesystem f
  JOIN tree_path t
    ON t.ancestor = f.id
 WHERE t.descendant = 7;

+----+---------+
| id | dirname |
+----+---------+
|  1 | ROOT    |
|  2 | Dir2    |
|  4 | Dir4    |
|  7 | Dir7    |
+----+---------+

SELECT f.id, f.dirname
  FROM filesystem f
  JOIN tree_path t
    ON t.ancestor = f.id
 WHERE t.descendant = (
SELECT id
  FROM filesystem
 WHERE dirname LIKE '%7%'
);

+----+---------+
| id | dirname |
+----+---------+
|  1 | ROOT    |
|  2 | Dir2    |
|  4 | Dir4    |
|  7 | Dir7    |
+----+---------+

@JOHN: Sorry, but I've never used orientDB, so couldn't really comment. — Mike, Jul 23 '11 at 20:28
@JOHN: I'm not sure what you mean - please can you give an example? — Mike, Jul 23 '11 at 20:52
@JOHN: There's a few ways to do it. I've added another example which simply does an additional SELECT to find the ID. You could also do a JOIN. — Mike, Jul 23 '11 at 21:06
I read the queries first and kept wondering, "How does that work?" The I realized that your `tree_path` table is the adjacency list representation of the *transitive closure* of the directory graph, answering the questions, "Is this path a reachable descendant of this other path?" and "Is this path a reachable ancestor of this other path?" Nice. — seh, Jul 23 '11 at 21:33
@seh: Yes, it's a really nice technique. Although it requires more entries than a simple adjacency list, the queries to select data are much simpler. I can't take the credit though. If you want to find out more about it, check the Bill Karwin links that I posted in the comments under the question. Note that you can also add a path length, which makes finding immediate ancestors/descendants simpler. — Mike, Jul 23 '11 at 21:38
Shouldn't your `tree_path` table contain a "nesting level" or "depth" field to make it a closure table? — j b, Jan 10 '14 at 13:13
@Mike "The order of the concatenated elements is arbitrary." (on `group_concat()`) https://sqlite.org/lang_aggfunc.html#groupconcat -- How do we know that the intermediate directories will be in order? — Bora M. Alper, Sep 08 '17 at 14:02
@boramalper Thanks, I wasn't aware of that. I've removed that particular example. — Mike, Sep 10 '17 at 11:55

Jackson Cassimiro · Answer 2 · 2016-03-09T11:51:35.900

I think you should read about a method caled Modified Preorder Tree Traversal: http://www.sitepoint.com/hierarchical-data-database/

That link discusses about two methods to storing hierarchical data into relational databases: the adjacency list model and the modified preorder tree traversal algorithm.

The main idea of Modified Preorder Tree Traversal method is annotate all nodes with pointers to auxiliate the navigation and sub-tree selection:

score 2 · Answer 3 · answered Jul 23 '11 at 19:42

You represent hierarchical data as a series of nodes each of which has an ID and a Parent ID. You could store your in a table called DIRTAB with 2 ID columns and one for the text of the individual directory name:

ID -- as a primary key  
PARENT_ID -- refers to the ID of the parent row in DIRTAB  
DIRNAME -- the text of the name eg Dir5

SQLite lacks the CONNECT BY clause that Oracle has to process hierarchical data but I think if you're prepared to accept some ugly SQL you can approximate something hierarchical:

SELECT (CASE WHEN p5.DIRNAME IS NOT NULL THEN p5.DIRNAME || '/' ELSE '' END) ||
       (CASE WHEN p4.DIRNAME IS NOT NULL THEN p4.DIRNAME || '/' ELSE '' END) ||
       (CASE WHEN p3.DIRNAME IS NOT NULL THEN p3.DIRNAME || '/' ELSE '' END) ||
       (CASE WHEN p2.DIRNAME IS NOT NULL THEN p2.DIRNAME || '/' ELSE '' END) ||
       (CASE WHEN p1.DIRNAME IS NOT NULL THEN p1.DIRNAME || '/' ELSE '' END) ||
       p0.DIRNAME as FULLPATH
FROM DIRTAB p0
     LEFT OUTER JOIN DIRTAB p1 ON p1.ID = p0.PARENT_ID
     LEFT OUTER JOIN DIRTAB p2 ON p2.ID = p1.PARENT_ID
     LEFT OUTER JOIN DIRTAB p3 ON p3.ID = p2.PARENT_ID
     LEFT OUTER JOIN DIRTAB p4 ON p4.ID = p3.PARENT_ID
     LEFT OUTER JOIN DIRTAB p5 ON p5.ID = p4.PARENT_ID
WHERE p0.DIRNAME = 'Dir6'

The trouble here is that you have to anticipate the maximum depth of you directory structure and expand the SQL statement to cope. I have done 6 levels as an example.
Also I'm assuming that SQLite has no problem concatenating empty strings. (Some DBs treat them as null and convert the whole expression result to null)

Hierarchical/tree database for directories path in filesystem

3 Answers3

Linked