Anyone have good DB schema / code for hierarchy matrix?

[adam0101]

I'd like to have a database that can store several items, let's use "Categories" as an example, where each Category can have many Sub-Categories and each Sub-Category can be in many parent Categories.

How could I design the database to handle this? Does anyone have any working examples they could share or a link to a resource on the web? (Maybe even some ASP code that works with the DB if you have any?)

P.S. What would something like this be called? It's not really a hierarchy because of the circular type of referencing. "Matrix" is the only thing I can think of but I don't know if that's very accurate either.

 

[r937]

you're right, it's not a hierarchy

a many-to-many self-referential structure?

create table category
( id integer primary key
, catname varchar(20) not null
)

create table catstruct
( within_id integer
, contains_id integer
, foreign key (within_id)
references category (id)
, foreign key (contains_id)
references category (id)
)

if you can give me example categories, i'll show you the catstruct rows

rudy

http://rudy.ca/

 

[adam0101]

Ok r937...for example, let's say an organization dictated that each department would do the Quality Control for another department. Each department would have a department under it and would also be under a different department:

Sales
--Marketing
----IT
------Sales (is the same as the one above)

I see a few problems you could run into using a "self-referencing structure". If you were ever asked to print out the matrix, 1. How would you know which node to print first and 2. if a parent item can be its own child, it could loop forever. Are there other things you can add to the DB to overcome these problems?

 

[r937]

in your quality control example, the concept of "under" is misleading, as it evokes a hierarchical structure, when clearly it is more lateral

yes, "loops" are certainly possible, but, for several reasons, including programming complexity, they are avoided if possible

where do you start to enumerate a many-to-many structure? if you were doing a hierarchy, you'd start at the nodes without parents, the "roots"

are there things you can add to the database to overcome loops or cycles? yeah, but they're ugly

besides, your example of departments checking up on each other is a nice one, it demonstrates that cases exists where you cannot avoid cycles

coming back to your original example, categories, you would more than likely have a "top" level, and categories at this level would not have any parent categories

best example: dmoz.org

their home page shows their top level categories

now, if you do a search for "programming", you see there are several categories with this name, including

Computers: Programming
Computers: Education: Programming
Computers: Parallel Computing: Programming

does this mean that there's one category with three parents, i.e. a true many-to-many structure?

i don't know for 100% sure, but i'd be willing to bet those are three completely different categories that each belong to only one parent and just happen to have the same name

if you can do this, and restrict your data to a simple one-to-many hierarchy, the database structure gets simpler, and the associated queries to pull stuff out is easier too

note you can also set up a "loop" or cycle in a one-to-many hierarchy

rudy

 

[stoggers]

Hi,

Is this an example of an involuted or recursive relationship. If this is then it is fairly straightforward to implement using associative tables.

The complexity of navigating this structure depends on the dialect of SQL that is used. It is a fairly straightforward task to navigate procedurally but there are several heavyweight DBMS's that contain functionality specifically designed too navigate these structures.

Regards,

Stoggers.

 

[fluteplr]

You might want to have a look at Joe Celko's book 'SQL for Smarties' he has at least a chapter devoted to this type of problem.

 

[stoggers]

Hi,

A very good (free) guide to complex SQL is:

http://ourworld.compuserve.com/homepages/Graeme_Birchall/DB2V81SM.PDF

Regards,

Stoggers.

 

[adam0101]

Thanks for the link stoggers, but the book is only the first 20 pages. I went to the web site and found a link to the full version if anyone's interested:

http://ourworld.compuserve.com/homepages/Graeme_Birchall/DB2V81CK.PDF

 

[adam0101]

Since I first posted this thread, the problem of having a recursive relationship has still been bothering me. I think I finally found a better way to handle the problem and wanted to share it with you. I think it's normal to think that when you have an item (I'll use a "Category" as an example) that can have many sub-categories and can also be a sub-category to many categories, you would join the table to itself in a many-to-many relationship like so:

+-------------+    +----------------+
|tblCategories|    |m2m             |    +-------------+
+-------------+    +----------------+    |tblCategories|
|CategoryID   |===>|ParentCategoryID|    +-------------+
|CategoryName |    |ChildCategoryID |===>|CategoryID   |
+-------------+    +----------------+    |CategoryName |
                                         +-------------+

The problem I kept running into using this method is that, unlike a normal hierarchy, there is no root level Category which means there's no beginning or end. This makes interacting with this structure hard. Just trying to print it out would cause an endless loop. To overcome this problem, I mixed a normal hierarchy schema with an extra table that I use to keep track of the relationships which would cause a loop. Here's the schema:

                     +----------------+   +--------------+
+----------------+   |tblCategories   |   |BackReferences|   +----------------+
|tblCategories   |   +----------------+   +--------------+   |tblCategories   |
+----------------+   |CategoryID      |==>|ParentID      |   +----------------+
|CategoryID      |==>|ParentCategoryID|   |ChildID       |==>|CategoryID      |
|ParentCategoryID|   |CategoryName    |   +--------------+   |ParentCategoryID|
|CategoryName    |   +----------------+                      |CategoryName    |
+----------------+                                           +----------------+

Using this schema, you can find the top of the hierarchy (any Category with ParentCategoryID==0) and you can make additional references to categories by putting them in the "BackReferences" table. For example, a web directory like Yahoo has a hierarchy of categories. These would all be kept in the table tblCategories. They also have links from sub-categories to other sub-categories or parent-categories outside of the main hierarchy. These links would be kept in the "BackReferences" table. Hopefully this is useful to some who have run across the same problem.

Adam

________________________________________________________________________________________