System and method for describing and creating a user defined arbitrary data structure corresponding to a tree in a computer memory

• US 6,003,033 A
• Filed: 02/28/1992
• Issued: 12/14/1999
• Est. Priority Date: 02/28/1992
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Amano, Tomio, Yamashita, Akio, Takahashi, Hiroyasu
• Primary Examiner(s): HOMERE, JEAN RAYMOND
• Application Number:
  US07/843,704
• Time in Patent Office: 2,846 Days
• Field of Search: 395/600, 395/650, 395/800, 395/160, 707/100, 707/101, 707/102, 707/2, 707/3
• US Class Current: 1/1
• CPC Class Codes: G06F 16/322 Trees
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A system that allows a user to describe a tree or a set of trees in a table, and the system automatically generates a data structure corresponding to the tree or the set of trees in memory in accordance with the description. The system interprets a table with one or more columns wherein each of the node attributes given to a node are entered, allocates a memory area to each of the nodes, sets data on the attributes given to the node, and generates pointer data indicating the connections of the memory areas. The hierarchy of the nodes and the sequence of nodes linked immediately below the same node are determined on the basis of the sequence of rows corresponding to the nodes and levels assigned to the nodes in the table.

Claims

1. A computerized system for describing and generating in memory a user defined arbitrary data structure corresponding to a tree having nodes, comprising:

means for creating a table for receiving data describing each node of a user defined tree structure, said data including user defined attribute data for each said node, said attribute data including node relationships, said table comprising a set of rows and a set of columns with each row corresponding to a single node contained in said user defined tree structure and each column corresponding to an attribute of said nodes;

means for entering user defined attribute data into said table;

means for interpreting said table to allocate an area in a memory for each of said nodes and setting said attribute data of said nodes respectively in said allocated memory areas; and

means for generating pointer data indicating connections of said allocated memory areas according to node relationships indicated in said attribute data.

2. A system as in claim 1 further comprising means for editing said table in response to the entry of said attribute data of each of said nodes by said entering means.

3. A system as in claim 2 further comprising storage means, external of said memory, for storing said table, and means for controlling the storing of data in said table in said storage means.

4. A system as in claim 3 wherein said means for controlling the storing of data in said table in said storage means comprises means for managing data produced by said editing means in response to the entry of attribute data by said entering means.

5. A system as in claim 3 wherein said means for controlling the storing of data in said table in said storage means comprises means for managing data produced by said table interpreting means.

6. A system as in claim 3 wherein said table comprises a main table for containing information relating to some of the nodes in a tree, and a sub-table for containing information relating to some of said nodes in a sub-tree, and further comprising means for merging said main table and said sub-table into a single combined table.

7. A system as in claim 2 wherein said means for editing said table comprises a text editor.

8. A system as in claim 1 further comprising means for entering information on the level of said nodes of said tree in said table.

9. A system as in claim 8 wherein said table interpreting means comprises means for determining the hierarchy of said nodes and the sequence of child nodes beneath a parent node, on the basis of the order of said nodes in said table.

10. A system as in claim 1 further comprising means for displaying said attribute data of each of said nodes in said table.

11. A system as in claim 1 wherein said data describing each node comprises information on node kinds.

12. A system as in claim 11 wherein said data structure contains sets of trees and said node kind information comprises information on whether it is mandatory that a respective node kind exists in every tree that is a member of said set of trees.

13. A system as in claim 1 wherein said attribute data on said nodes comprises information on the maximum and minimum number of said nodes.

14. A computerized method for describing and generating in memory a user defined arbitrary data structure corresponding to a tree having nodes, comprising the steps of:

providing a table for receiving data describing each node of a user defined tree structure, said data including user defined attribute data for each said node, said attribute data including node relationships, said table comprising a set of rows and a set of columns with each row corresponding to a single node contained in said user defined tree structure and each column corresponding to an attribute of said nodes;

entering user defined attribute data into said table;

interpreting said table to allocate an area in a memory for each of said nodes and respectively setting said attribute data of said nodes in said allocated memory areas; and

generating pointer data indicating connections of said allocated memory areas according to node relationships indicated in said attribute data.

15. A method as in claim 14 wherein said table is provided in a storage unit external to said memory and fetched therefrom to memory for said interpreting step.

16. A method as in claim 14 further comprising the steps of:

entering data on the attributes of each of said nodes in said table;

editing said table on the basis of the attribute data entered; and

interpreting said edited table to allocate an area in said memory for each of said nodes.

17. A method as in claim 14 further comprising the step of displaying said table.

18. A method as in claim 14 wherein the step of providing a table comprises the steps of:

storing information relating to some of the nodes in a main table;

storing information relating to some of said nodes in a sub-table; and

merging said main table information and said sub-table information into a single combined table.

19. A method as in claim 14 wherein said table interpreting step comprises determining the hierarchy of said nodes and the sequence of child nodes beneath a parent node, on the basis of the order of said nodes in said table.