Please enable JavaScript.
Coggle requires JavaScript to display documents.
Design Patterns of Data Bases - Coggle Diagram
Design Patterns of Data Bases
Graph, Trees and Hierarchies Overview
abstract structures
graphs
a diagram of “dots”and “lines”
called nodes or vertices and edges
“flow” or relationship
edges can be undirected or directed
general models
the components
a road map
Flowcharts, organizational charts
directed graph
one direction only
shown by the arrowheads
undirected graph
both directions
an edge must join two (and only two) nodes
Trees are a special case of graphs
hierarchies are a special case of trees
Trees properties
A tree is a connected graph that has no cycles
Every node is the root of a subtree
Every two nodes in the tree are connected on one (and only one) path
A tree is a connected graph that has one less edge than it has nodes
an edge (a, b) is deleted
result is a forest of two disjointed trees
One tree contains node (a)
the other contains node (b)
hierarchy is a directed tree with extra properties
subordination
inheritance
the most important property
does not exist in an ordinary tree
organizational charts
business applications
the same node can play many different roles
The menu
have roles that are filled by entities
each node appears once in a tree and is unique
Adjacency List Model
Data Manipulation
adding and updating elements
removal is more difficult
selection is a problem
choose only all direct descendants of the item
single-table representation
the edge connection appears in the same table as the node
Adjacency list model
one column for the identifier of the node
one column of the same data type for the parent of the node
best for organizational charts
different assemblies
two-table format
one table contains the nodes of the graph
other table contains the edges
represented as pairs of end points
Nested Sets Model
nested sets is a better model for trees and hierarchies
model a tree with left and right nested sets with number pairs
contain the pairs of their subordinates
Data Manipulation
adding and editing are extremely costly
removing is a costly procedure too
selection is the purpose
Materialized Path
Data manipulation
adding and editing are more difficult
removal of item doesn’t involve violations
selection is the strength
Materialized Path method
stores the path from the root to each node as a string at that node
a denormalized table
path is not a scalar value
worst-case operation is to alter the root of the tree
to recalculate all the paths
if the assumption is that structural modifications high in the tree are relatively uncommon, then this might not be a problem
