home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / database / 8905 < prev    next >
Encoding:
Internet Message Format  |  1993-01-07  |  5.4 KB
  1. Path: sparky!uunet!nntp1.radiomail.net!fernwood!autodesk!tropic!tchild
  2. From: tchild@autodesk.com (Timothy Child)
  3. Newsgroups: comp.databases
  4. Subject: Re: Hierarchical Structures in RDBMS
  5. Message-ID: <18335@autodesk.COM>
  6. Date: 7 Jan 93 23:10:08 GMT
  7. References: <1993Jan6.094340.5870@devon.co.uk>
  8. Sender: news@Autodesk.COM
  9. Reply-To: tchild@autodesk.com
  10. Organization: Autodesk, Inc.
  11. Lines: 140
  12.  
  13. In article 5870@devon.co.uk, don@duncan (Don Radvan) writes:
  14. > 
  15. > I have an interesting problem. I need to represent hierarchical data  
  16. > structures within a relational db, but I need to do it in a way that  
  17. > permits the user to create his own hierarchy. That is, I do not know the  
  18. > structure of the hierarchy before hand. 
  19. > 
  20. > For example:
  21. >     A user wants to organize various objects. These objects will  
  22. > appear as leaf nodes in the user's own hierarchy. The user may choose many  
  23. > different ways of organizing these objects, indeed, s/he may have many  
  24. > simultaneous hierarchies of organization for each set of objects. What  
  25. > results is a sort of directory tree. Each directory is a category of  
  26. > objects and each "file" or non-directory entry in a directory is an  
  27. > object. Given the objects of apples and oranges, we may get the following:
  28. > 
  29. >                                   Stuff
  30. >                                     |
  31. >                     --------------------------------
  32. >                   Food                          Non-Food
  33. >                     |
  34. >             ---------------------- . . .
  35. >          Fruit        Veggies 
  36. >            |
  37. >      -------------
  38. >   Apples       Oranges
  39. > 
  40. > And so when s/he does a query such as the following:
  41. >     select name where Food = "Fruit"
  42. > or
  43. >     select name where Stuff = "Food" AND Food = "Fruit"
  44. > 
  45. > we would get Apples and Oranges.
  46. > 
  47.  
  48.  It's possible to model this problem with an RDBMS, but I don't know of
  49.  a STANDARD way to express the appropriate SQL to return the information
  50.  and I don't think there is one!  
  51.  
  52.  What you have in the hierarchy above is a specialized form of directed
  53.  acyclic graph (DAG).  The solution proposed below applies cyclic and
  54.  acyclic graphs so the system also must contain extra logic to assure the
  55.  appropriate specialized form of graph.
  56.  
  57.  A graph can be modeled in an RDBMS with two tables Nodes and Links.
  58.  Nodes are the entities of the hierarchy like: Stuff, Fruit, Food, etc,
  59.  . . .
  60.  
  61.  A node relation would be something like:
  62.  
  63.      Node id (prime key), node attributes, . . . 
  64.  
  65.  Links are the connections between Nodes and contain the keys of the parent
  66.  and sibling nodes. A link relation would be something like . . .
  67.  
  68.      Parent Node id, Sibling Node id, (together making the primary key), 
  69.         link attributes,  etc . . .
  70.  
  71.  In the above example the tables would look like, . . .
  72.  
  73.   Nodes              Links
  74.  
  75.  Stuff            Stuff, Food
  76.  Food            Stuff, Non_Food
  77.  Non_Food        Food, Fruit
  78.  Fruit            Food, Veggies
  79.  Veggies        Fruit, Apples
  80.  Apples            Fruit, Oranges
  81.  Oranges
  82.  
  83.  The query strategy is to start with  a given Node id and search
  84.  the Link table for all entires that contain that Node id as the
  85.  parent. The parents sibling node ids can be used to search the Links
  86.  table for their siblings. The search continues recursively until the
  87.  desired number of levels has been reached.
  88.  
  89.  Standard SQL queries have no way of dealing with this recursive
  90.  search. Some vendors provide work arounds with non standard
  91.  features.  Another solution is to have specific queries
  92.  for a specific number of levels.
  93.  
  94.  There is one piece of semantics this relational approach doesn't
  95.  capture and that is sub-entity synonyms. Because all entries in the
  96.  hierarchy are nodes they appear in the node table as unique names, no
  97.  duplicates are allowed.  It is possible to have a hierarchy with two
  98.  sub-entities with the same name that are different, my above solution
  99.  doesn't support this.
  100.  
  101.  For example consider the hierarchy ....
  102.  
  103.  
  104.             Stuff
  105.           |
  106.     -------------------
  107.     |           |
  108.       Food         Non-Food
  109.     |           |
  110.       -------         ---------
  111.       |     |          |          |
  112.    Fruit             Paint
  113.       |                  |
  114.     --------          -----------
  115.     |        |         |     |    |
  116.   Orange   Apple    Blue  Red Orange    
  117.  
  118.  
  119.   Orange is both a kind of fruit and a paint. To support this sort of
  120.   arrangement you need to introduce an extra key field to identify node
  121.   types.  Let's call it the type id. The Node and Link relations now
  122.   look like:
  123.  
  124.   Node Id, Type Id, (a compound primary key) ...
  125.  
  126.   Parent Node Id, Parent Type Id, Sibling Node Id, Sibling Type Id,
  127.      (all 4 fields are the primary key) . . .
  128.  
  129.   I would also recommend adding an additional table of Type Ids.
  130.   The type table would allow for referential integrity checks
  131.   on the type id.
  132.  
  133.   This solution only works if the nodes are of different types. It
  134.   wouldn't work if the hierarchy was a UNIX directory structure
  135.   for example.
  136.  
  137.   Another problem with this approach and the relation model is the
  138.   issue that a Node is a Node and only a Node. Therefore all nodes have
  139.   an identical number and kinds of attributes.  This problem can be
  140.   dealt with in a couple of ways, including extra tables which contain
  141.   specific attributes for each type. It is considered bad practice to
  142.   need to add new tables because of new subtype instances.
  143.  
  144.   In general graph like structures are one of the toughest things to
  145.   work with in the relational model.  A network or an object oriented
  146.   data base has a more natural affinity for solving this kind of
  147.   problem.
  148.  
  149.  -Tim Child
  150.  
  151.  Autodesk Inc. (Exercising an individual first amendment right.)
  152.  
  153.