## faqts : Computers : Databases

##### + Search    Did You Find This Entry Useful? 1 of 71 people (1%) answered YesRecently 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 ] 
2 [ B ]            [ b ] 
3 [ C ]            [ c ] 
4 [ D ]            [ d ] 
5 [ E ]            [ e ] 
[ f ] 
[ g ] 
[ h ] 
[ i ] 
[ j ] 
[ k ] 
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 ] 
[ b ] 
[ c ] 
[ d ] 
[ e ] 
[ f ] 
[ g ] 
[ h ] 
[ i ] 
[ j ] 
[ k ] 
---
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.
---
---