faqts : Computers : Databases

+ Search
Add Entry AlertManage Folder Edit Entry Add page to http://del.icio.us/
Did You Find This Entry Useful?

1 of 71 people (1%) answered Yes
Recently 0 of 10 people (0%) answered Yes

Entry

Database: Relational: List: Is a one to many database similar to a graph? [array]

Jul 6th, 2008 13:32
Knud van Eeden, dman,


----------------------------------------------------------------------
--- Knud van Eeden --- 10 September 2004 - 08:09 pm ------------------
Database: Relational: List: Is a one to many database similar to a 
graph? [array]
---
---
A one to many database is a special case of a graph.
---
figure 1: Two lists: in a 'one to many' relation
           One              Many
        1 [ A ]            [ a ] [3]
        2 [ B ]            [ b ] [3]
        3 [ C ]            [ c ] [1]
        4 [ D ]            [ d ] [2]
        5 [ E ]            [ e ] [3]
                           [ f ] [4]
                           [ g ] [2]
                           [ h ] [5]
                           [ i ] [4]
                           [ j ] [3]
                           [ k ] [1]
        array1[]           array2[][]
---
This represents the graph(s):
figure 2: graph another equivalent representation of the same 
information
      A           B           C           D      E
      |           |           |           |      |
  +---+---+   +---+---+   +---+---+   +---+---+  |
  |       |   |       |   |   |   |   |       |  |
  c       k   d       g   a   b   e   f       i  h
---
---
You can also show the one to many database as an adjacency graph
(in other words, it is a list, with a variable amount of
elements assigned to each option)
figure 3: adjacency graph: another equivalent representation of the 
same information
          1[ A ]->[c]->[k]
          2[ B ]->[d]->[g]
          3[ C ]->[a]->[b]->[e]
          4[ D ]->[f]->[i]
          5[ E ]->[h]
---
That this adjacency graph is equivalent to the two lists 
representation,
you can quite easy see when you take the elements of the right list of 
figure 3,
and put them in 1 line:
---
figure 4.1: put all the elements of the graph in figure 3 in a line
 [c] [k] [d] [g] [a] [b] [e] [f] [i] [h]
---
figure 4.2: give each element a number corresponding to its connected
            element in the left list in figure 1.
 [c] [k] [d] [g] [a] [b] [e] [f] [i] [h]
  1   1   2   2   3   3   3   4   4   5
---
figure 4.3: Then rotate this list over ninety degrees:
   1 [ c ]
   1 [ k ]
   2 [ d ]
   2 [ g ]
   3 [ a ]
   3 [ e ]
   4 [ f ]
   4 [ i ]
   5 [ h ]
---
figure 4.4: Then rearrange them according to figure 1
            (this is possible, because you keep the number
             with it, so you do not loose information here)
   [ a ] [3]
   [ b ] [3]
   [ c ] [1]
   [ d ] [2]
   [ e ] [3]
   [ f ] [4]
   [ g ] [2]
   [ h ] [5]
   [ i ] [4]
   [ j ] [3]
   [ k ] [1]
---
Thus a one to many (or similarly a many to one) list is the equivalent
of a graph. A graph is quite a versatile structure which pops up in
a lot of areas. So your one to many database might be able to cover
the equivalent information in that areas in a suitable way.
---
---
Internet: see also:
---
Database: Link: Overview: Can you give me an overview of links?
http://www.faqts.com/knowledge_base/view.phtml/aid/33838/fid/132
----------------------------------------------------------------------