Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

SQL and Delphi: recursive mechanism for creating a tree from a table

The DBMS I'm working with is MySQL, the programming environment is Delphi 7 (which doesn't really matter for this example).

I have a table called 'subject' where I store all book subjects in the system. Subjects can have a parent-child relationship, like science can be divided, let's say, into math and physics whereas math can be subdivided into calculus, algebra, geometry and on we go.

What I would like is create a tree populated with the date from that table. Please, help me do that. It even doesn't matter what language you use for illustration purposes, it simply can be pseudocode.

The database diagram for the Subject table looks like this:

enter image description here

The Subject table definition:

DROP TABLE IF EXISTS subject;
CREATE TABLE IF NOT EXISTS subject (                  # Comment
    subject_id  INT UNSIGNED NOT NULL AUTO_INCREMENT, # Subject ID
    subject     VARCHAR(25)  NOT NULL,                # Subject name
    parent_id   INT UNSIGNED     NULL DEFAULT NULL,   # Parent ID as seen from
    PRIMARY KEY (subject_id),                         # the diagram refers to
    UNIQUE (subject),                                 # the subject_id field
    INDEX (parent_id),
    CONSTRAINT fk_subject_parent
    FOREIGN KEY (parent_id)
        REFERENCES subject (subject_id)
            ON DELETE RESTRICT
            ON UPDATE CASCADE
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

Populating the Subject table with some dummy data:

INSERT INTO subject (subject, parent_id) VALUES
                    ('Science',    NULL),
                    ('Mathematics',   1),
                    ('Calculus',      2),
                    ('Algebra',       2),
                    ('Geometry',      2),
                    ('Languages',  NULL),
                    ('English',       6),
                    ('Latin',         6);

SELECT statement returns this:

SELECT * FROM subject;
╔════════════╦═════════════╦═══════════╗
║ subject_id ║   subject   ║ parent_id ║
╠════════════╬═════════════╬═══════════╣
║          1 ║ Science     ║      NULL ║
║          2 ║ Mathematics ║         1 ║
║          3 ║ Calculus    ║         2 ║
║          4 ║ Algebra     ║         2 ║
║          5 ║ Geometry    ║         2 ║
║          6 ║ Languages   ║      NULL ║
║          7 ║ English     ║         6 ║
║          8 ║ Latin       ║         6 ║
╚════════════╩═════════════╩═══════════╝

Stored procedures:

DELIMITER$$

DROP PROCEDURE IF EXISTS get_parent_subject_list;
CREATE PROCEDURE get_parent_subject_list ()
BEGIN
    SELECT subject_id, subject
    FROM subject
    WHERE parent_id IS NULL
    ORDER BY subject ASC;
END$$


DROP PROCEDURE IF EXISTS get_child_subject_list;
CREATE PROCEDURE get_child_subject_list (IN parentID INT)
BEGIN
    SELECT subject_id, subject
    FROM subject
    WHERE parent_id = parentID
    ORDER BY subject ASC;
END$$

DELIMITER ;

Next is my Delphi procedure that attempts to populate a tree view with data, but as can be seen further, it can't get any deeper than the second level:

procedure TForm1.CreateSubjectTreeView(Sender: TObject);
var
    i : integer;
begin
    i := 0;

    q1.SQL.Clear;
    q1.SQL.Add('CALL get_parent_subject_list()');
    q1.Open;
    q1.First;

    while not q1.EOF do
    begin
        TreeView.Items.Add(nil, q1.Fields[1].Value);

        q2.SQL.Clear;
        q2.SQL.Add('CALL get_child_subject_list(' +
                    VarToStr(q1.Fields[0].Value) + ')');
        q2.Open;
        q2.First;

        while not q2.EOF do
        begin
            TreeView.Items.AddChild(TreeView.Items.Item[i], q2.Fields[1].Value);
            q2.Next;
        end;

        i := TreeView.Items.Count;
        q1.Next;
    end;
end;

This is what this snippet of code does:

+- Science
|   |
|   +- Mathematics
|
+- Languages
    |
    +- English
    +- Latin

But I would like it to look like this:

+- Science
|   |
|   +- Mathematics
|       |
|       +- Calculus
|       +- Algebra
|       +- Geometry
|
+- Languages
    |
    +- English
    +- Latin
like image 806
Mikhail Avatar asked Apr 09 '13 13:04

Mikhail


1 Answers

I suggest you not load the whole tree at once, why should you ? no man can view at the moment a thousand of items. And it can be long and your program would look frozen. And it makes a huge load pike over network and server.

You better use VirtualTreeView approach, where each item loads its children items on request. That would require one parametrized prepared query like

 Select ID, Title, This, That from TREE where Parent_ID = :ID
  • http://code.google.com/p/virtual-treeview/
  • http://www.lischke-online.de/index.php/controls/virtual-treeview-gallery
  • Tree-like Datastructure (for use with VirtualTreeview)
  • VirtualStringTree Correct/recommended use

And yes, don't make new SQL text for every item. It is both dangerous and slow (you need to drop all the data gathered for an old request and parse the new one)

You should make one parametrized query, Prepare it and just do close/change param values/open.

See reasons and Delphi sample at http://bobby-tables.com/


One example of "load it all at once altogether" rush is at dynamically create popup menu tree from sql server table in Delphi - though i don't think rush is good approach for more or less large trees.

Note about this approach: you fill in root elements, then you find one way or another to fill in elements, not filled yet, but already referenced by others until there is no such elements at last.

You can do it recursively of course, traversing tree to its ends - but that would ask for many nested database queries.

You may make a recursive SQL request, but it would probably be very server-dependent and RDBMS engines usually impose their limits on recursion depth.

An approach maybe slightly worse on tree control but more clean and easier on RDBMS would be to make a dedicated TQueue of just added tree items. After you load some element - initially all root ones - you remember it in the queue. Then you remove one by another from the queue and fill in (load and enqueue) its children. Until the queue gets empty.

like image 61
Arioch 'The Avatar answered Oct 13 '22 03:10

Arioch 'The