HIERARCHICAL DATABASE MODEL

Hierarchy is based on Parent-Child Relationship

  • Parent-Child Relationship Type is basically 1:N relationship
  • The schema for a hierarchy has a single root
  • To represent M:N relationship in a hierarchical structure, we must allow duplication of child record instances.

    HIERARCHICAL OCCURENCE TREE

    The main concepts are:

    Type indicators such as D, E, W. etc.
    Descendent of a node
    Subtree of a node
    Level (0, 1, 2, etc.)
    Hierarchical sequence
    (used to linearize a tree)
    Complete hierarchical path
    (from root to a leaf)
    Child pointer
    Parent pointer
    Twin pointer (sibling pointer)

    For example, the following is the hierarchical schema of a company database:

    The tree representation of the above hierarchical schema is shown below:

    The two occurrences of the PCR type (DEPARTMENT and EMPLOYEE) are shown in (a), and the two occcurrences of the PCR type (DEPARTMENT and PROJECT) are shown in (b).

    HIERARCHICAL SEQUENCE

    The hierarchical schema for part of the COMPANY database is as shown:

    The hierarchical occurrence tree of the hierarchical schema is as shown:

    The hierarchical sequence for the occurrence tree is as shown:

    VIRTUAL PARENT-CHILD RELATIONSHIPS

  • Used to overcome limitations in the hierarchical model
  • IMS's LDBR type follows this concept
  • Gain in flexibility, loss in the complexity (almost a network model)

    IMS CONCEPTS

    PDBR type
    Use DBD to specify PDBR type
    PDBR occurrence
    LDBR type
    DBD, PSB and PCB
    Storage organization
    How an application invokes IMS

    IMS DATABASE EXAMPLE

    The PDBR type is as shown:

    The LDBR type is as shown:

    To specify PDBR type, the DBD statements may look like: 

    1 DBD NAME=EDUCPDBD
2 SEGM NAME=COURSE,BYTES=256
3 FIELD NAME=(COURSE#,SEQ),BYTES=3,START=1
4 FIELD NAME=TITLE,BYTES=33,START=4
5 FIELD NAME=DESCRIPTN,BYTES=220,START=37
6 SEGM NAME=PREREQ,PARENT=COURSE,BYTES=36
7 FIELD NAME=(COURSE#,SEQ),BYTES=3,START=1
8 FIELD NAME=TITLE,BYTES=33,START=4
 .....
    To specify LDBR type, the DBD statements may look like: 
    1 PCB TYPE=DB.DBNAME=EDUCPDBD,KEYLEN=15
2 SENSEG NAME=COURSE.PROOPT=G
3 SENSEG NAME=OFFERING,PARENT=COURSE.PROOPT=G
4 NAME=STUDENT,PARENT=OFFERING,PROOPT=G

    IMS QUERY EXAMPLES

    (1) To retrieve the first occurrence of segment OFFERING whose location is 'MADRID', we can use GET UNIQUE command,

    GU COURSE
    OFFERING (LOCATION='MADRID')

    Where (LOCATION='MADRID') is called the SEGMENT SEARCH ARGUMENT (SSA)

    (2) To retrieve all the STUDENT segments for the COURSE OFFERING in Madrid, we can use GET UNIQUE to get first segment, and GET NEXT to retrieve subsequent segments.

    GU COURSE
    OFFERING (LOCATION='MADRID')
    STUDENT
    NS GN STUDENT
    (This loop is terminated on segment not found)
    GO TO NS

    IMS QUERY EXAMPLES

    (3) Similarly, to retrieve only grade 'A' students for course offering in Madrid, we can add an SSA on STUDENT segment,

    GU COURSE
    OFFERING (LOCATION='MADRID')
    NS GN STUDENT (GRADE='A')
    (This loop is terminated on segment not found)
    GO TO NS

    (4) When no segment name is specified, GET NEXT can be used to retrieve all segments.

    GU COURSE
    NS GN
    (This loop is terminated when all segments are retrieved)
    GO TO NS

    IMS QUERY EXAMPLES

    (5) To retrieve all child segments within a parent segment, we can use GET NEXT WITHIN PARENT.

    GU COURSE (COURSE#='M23')
    OFFERING (DATE='730813')
    NS GNP STUDENT
    (This loop is terminated when all STUDENT segments under same OFFERING segment are retrieved)
    GO TO NS

    (6) Similarly, we can retrieve all segments within a root segment, as follows.

    GU COURSE (COURSE#='M23')
    NS GNP
    (This loop is terminated when all segments under root segment are retrieved)
    GO TO NS

    IMS QUERY EXAMPLES

    (7) To perform insertion of a new segment, the new segment must be present in I/O work area. Then the insertion command can be issued.

    ISRT COURSE (COURSE#='M23')
    OFFERING (DATE='730813')
    STUDENT


    (8) To delete a segment, the command GET HOLD is used to "hold" a segment in work area, and then the DLET command can be issued.

    GHU COURSE (COURSE#='M23')
    OFFERING (DATE='730813')
    DLET

    (9) Similar commands are used for segment update.
    GHU COURSE (COURSE#='M23')
    OFFERING (DATE='730813')
    (updated segment is in I/O work area)
    REPL

    MUMPS

  • widely used in the hospitals
  • started as an interpretative system
  • Key concepts:
    Segment
    Pointers
    Dynamic data structure

    The MUMPS database has the following hierarchical schema.

    The MUMPS database structure is as follows: 

    *1 drugrecord
 *2 patient
   3 patient-number
   3 name
   3 prescription-date
     4 treated-problem
      *5 drugs-prescribed
        6 drug-name
        6 quantity
        6 frequency
    In implementation, the MUMPS database structure looks like this:

    MUMPS DBML

    To create the drug database structure using segments, we can use 'set' commands to assign values to global variables, which are denoted by |xyz. The first command assigns the name 'drug' to the directory entry for the drg database.

    set |drg = 'drug'

    Similarly, we create the next-level segment by,

    set |drg(pat) = 'Doe'

    where 'pat' is a unique numeric key, the patient-number, for patient whose name is 'Doe'. In MUMPS, all keys must be numeric keys.

    The subscripts for a global variable, therefore, indicates segments at different levels. levels. Therefore, no previous declaration of file is necessary.

    To create the next-level segment, we could execute,

    set |drg(pat,date) = '1203'

    However, since no data will be stored at this level, this is unnecessary. The value for 'date' can be regarded as a numeric key. Therefore, we can proceed to the next level to execute,

    set |drg(pat,date,icd) = 'Asthma'

    which will also assign a numeric value to 'date'.

    MUMPS DBML

    Similarly, we can regard 'dno' (drug-number) as a numeric key, and proceed to the last level,

    set |drg(pat,date,icd,dno,1) = 'Decadron'
    set |drg(pat,date,icd,dno,2) = 15
    set |drg(pat,date,icd,dno,3) = 3


    To retrieve drug data, we have available as keys patient-number (pat), prescription-date (date), problem-number (icd), and drug-number (dno). All keys are numeric subscripts of the global variable 'drg'. Therefore, the fetch command is,

    set drugname = |drg(pat,day,icd,dno,1)

    The retrieval of a segment is achieved by a sequential scan of segments at every level, until a match is found.

    MUMPS implementation normally uses chains of blocks. Segments at each level are packed into a chain of blocks and accessed sequentially.

    To remove a record and release storage, we can execute,

    kill |drg(pat)

    which will delete one patient's related segments, by removing unused blocks and returning freed blocks to free-space chains.