I've got a PHP web application which utilizes a MySQL database for object marking, by which I have used the tag structure recognized because the response to this SO question.

Let me implement a tag hierarchy, where each tag may have a unique parent tag. Looks for a parent or gaurdian tag T would then match all descendants of T (i.e. T, tags whos parent is T (kids of T), grandchildren of T, etc.).

The simplest method of carrying this out appears to become to include a ParentID area towards the tag table, which consists of the ID of the tag's parent tag, or some miracle number when the tag doesn't have parent. Trying to find descendants, however, then requires repeated full searches from the database to obtain the tags in every 'generation', which Let me avoid.

A (most probably) faster, but less normalised method of doing this is to possess a table that contains all of the kids of each tag, as well as all of the descendants of every tag. Nevertheless this runs the chance of sporadic data within the database (e.g. a tag being the kid in excess of one parent).

Can there be a great way to make queries to locate descendants fast, and keep the information as normalised as you possibly can?

I implemented it using two posts. I simplify it here just a little, because I needed to keep your tag title inside a separate area/table because I needed to localize it for various languages:

  • tag
  • path

Take a look at these rows for instance:

tag            path
---            ----
database       database/
mysql          database/mysql/
mysql4         database/mysql/mysql4/
mysql4-1       database/mysql/mysql4-1/
oracle         database/oracle/
sqlserver      database/sqlserver/
sqlserver2005  database/sqlserver/sqlserver2005/
sqlserver2005  database/sqlserver/sqlserver2008/


While using like operator on the way area it is simple to get all needed tag rows:

SELECT * FROM tags WHERE path LIKE 'database/%'

You will find some implementation particulars like whenever you move a node within the hierarchy you need to change all children too etc., but its easy.

Also make certain that the duration of your path is lengthy enough - during my situation I made use of not the tag reputation for the road, but another area to make certain which i do not get too lengthy pathways.

Ali's answer includes a connect to Joe Celko's Trees and Hierarchies in SQL for Smarties, which verifies my suspicion - there is not an easy database structure that provides the very best of all mobile phone industry's. The very best for my purpose appears to become the "Frequent Insertion Tree" detailed within this book, that is such as the "Nested Set Model" of Ali's link, however with non-consecutive indexing. This enables O(1) insertion (a la unstructured Fundamental line numbering), with periodic index reorganisation whenever needed.

I'd apply certain type of array to keep the kids tags, this ought to be much faster than joining a table on itself (particularly if you have a lot of tags). I'd a glance, and that i can't know if mysql includes a native array data type, however, you can emulate this using a text column and storing a serialized array inside it. If you wish to quicken things further, you need to have the ability to put a text search index on that column to discover which tags are associated.

[Edit] After reading through Ali's article, Used to do more hunting and located this presentation on a lot of processes for applying hierarchies in postgres. May still be useful for explanatory reasons.

You can build what Kimball calls a Hierarchy Assistant Table.

Say you hierarchy appears like this: A -> B B -> C C -> D

you'd place records right into a table that appears such as this

ParentID, ChildID, Depth, Greatest Flag, Cheapest Flag

A, A, , Y, N

A, B, 1, N, N

A, C, 2, N, N

A, D, 3, N, Y

B, B, , N, N

B, C, 1, N, N

B, D, 2, N, Y

C, C, , N, N

C, D, 1, N, Y

D, D, . N, Y

I believe I've that correct.... anyways. The thing is you'll still store you hierarchy properly, you simply build this table Out of your proper table. THIS table queries just like a Banshee. Say you'd like to learn what all of the first level below B are.

WHERE parentID = 'B' and Depth = 1