Hierarchical Semantic Database Structure of the E-Learning Systems

Abstract

Chapter Preview

Top

Background

The most researched, highly effective storage methods for hierarchy in relational systems are tree management method. The basic methods for persisting trees in relational systems are adjacency list, materialized path, nested sets and closure table. The short description of each method is given below.

Adjacency List

The “ancestor-descendant” relation is stored together with data as the simple link to the immediate ancestor.

In Figure 1, the example of hierarchical structure of data and its storage with use of this method is presented. The main problem when using such a way of storage – impossibility of quick extracting completely hierarchy because of obtaining each following level demands join operation that imposes restriction on the greatest possible depth of structure (tree).

Figure 1.

Adjacency List

Materialized Path

For each node in structure of hierarchical data it is stored also enumeration of all his ancestors.

In Figure 2, the example of hierarchical structure of data and its storage with use of this method is presented. As enumeration of ancestors is stored in one element of a tuple, the main lack of this method is additional overhead costs of work with this element: checks on infinite loops, string concatenation etc.

Figure 2.

Materialized Path

Nested Sets

For each node in structure of hierarchical data two additional fields are added: left (the left border of a set, some number which is less than all numbers, which use descendants of the current node) and right (the right border of a set, number which is less than all numbers, which use descendants of the current node). Thus, the relation “ancestor - descendant” is defined by entry of the descendant left value into an ancestor’s interval (left; right).

In Figure 3, the example of hierarchical structure of data and its storage with use of this method is presented. Use of nested sets allows get rid of restriction on the maximum possible depth of a tree, and joint uses of this method with the Adjacency List method will allow to take all structure of hierarchical data by means of one operation of relational algebra. However, costs of an inserting and moving of nodes demand a large number of additional operations for recalculation of left and right values that is especially significant on hierarchical structures with a high nesting level.

Figure 3.

Nested Sets

Key Terms in this Chapter

Sub Tree “Disconnection”: The Process of separating sub tree from its structure; Opening Up.

Hierarchical Structure Extraction: Process of extracting (selecting) hierarchy from persisted state.

Hierarchical Structure Linking: Connection of hierarchical structures of different users, generating a graph of shared content (ext. course).

Access to Sub Tree: Act of “sharing” the sub tree from one user to another (for example teacher can share the course to students).

Sub Tree: Some part of hierarchical structure and all its descendants.

Hierarchical Structure Depth - Nesting Level: A maximum of nested levels count (of given hierarchical structure).