Browse Prior Art Database

New Mechanism for Manipulating Hierarchical Structures

IP.com Disclosure Number: IPCOM000105320D
Original Publication Date: 1993-Jul-01
Included in the Prior Art Database: 2005-Mar-19
Document File: 8 page(s) / 169K

Publishing Venue

IBM

Related People

Singh, S: AUTHOR [+2]

Abstract

The mapping of hierarchical data modeling structures (trees) to Entity-Relationship (E-R) data modeling structures is complex when dealing with E-R models where the source or target of a relationship is another relationship. The necessary algorithms, concepts and data structures which are necessary to facilitate the population of the database via a hierarchical tree which is mapped to an E-R model, where the source or target of a relationship is another relationship, will be described here. This solution not only addresses this particular problem but it is a general traversal mechanism for hierarchical tree structures which map to E-R models. Most of the databases developed in the future will be E-R or Object-Oriented databases.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 24% of the total text.

New Mechanism for Manipulating Hierarchical Structures

      The mapping of hierarchical data modeling structures (trees) to
Entity-Relationship (E-R) data modeling structures is complex when
dealing with E-R models where the source or target of a relationship
is another relationship.  The necessary algorithms, concepts and data
structures which are necessary to facilitate the population of the
database via a hierarchical tree which is mapped to an E-R model,
where the source or target of a relationship is another relationship,
will be described here.  This solution not only addresses this
particular problem but it is a general traversal mechanism for
hierarchical tree structures which map to E-R models.  Most of the
databases developed in the future will be E-R or Object-Oriented
databases.  Therefore, the tree traversal mechanisms and the data
structures described here will be useful in the migration of
hierarchical databases to the newer databases.

      The following figures illustrate an E-R model and the
associated hierarchical structure that maps to this model.

-------------------------------------
|  E-R model        | Tree structure|
|-----------------------------------|
|    -----          |     -----     |
|    | A |          |     | A |     |
|    -----          |     -----     |
|      |            |       | r1    |
|----  |     ----   |     -----     |
||B |------->|C |   |     | B |     |
|----        ----   |     -----     |
|                   |       | r2    |
|                   |     -----     |
|                   |     | C |     |
|                   |     -----     |
-------------------------------------

E-R Model/Hierarchical Tree Structure Mapping

      "A, B, and C"  tree structure nodes map to "A, B, and C"  E-R
model entities.  Similarly, "r1 and r2"  connections between the tree
nodes map to "r1 and r2"  E-R model relationships.  The following
four terms are necessary in order to effectively present the ideas in
this paper.  These terms apply to the tree structure section in the
above figure.

o   Logical Source : This is the source of a connection as viewed via
    the hierarchical tree structure.  Tree node "A"  is the logical
    source of connection "r1".
o   Logical Target : This is the target of a connection as viewed via
    the hierarchical tree structure.  Tree node "B"  is the logical
    target of connection "r1".
o   Physical Source : This is the source of a connection as viewed
    via the E-R model.  Entity "A"  is the physical source of
    connection "r1".
o   Physical target : This the target of a connection as viewed via
    the E-R model.  Relationship "r2"  is the physical target of
    connecti...