Database system with multi-dimensional summary search tree nodes for reducing the necessity to access records
First Claim
1. A database management system comprising:
- a memory for storing data structures, includinga detail table means for storing a plurality of records, each of the plurality of records being addressable by record pointers and including dimension fields and summary fields, the dimension fields including dimension values, and the summary fields including numeric information;
a summary table means including summary nodes for storing summary information of the summary fields for summary sets of the plurality of records;
a detail index means including detail index nodes for storing the record pointers for index sets of the plurality of records, whereineach index set of the plurality of records includesa plurality of records having a common combination of dimension values for the associated dimension fields, and whereineach summary set of the plurality of records includesa plurality of index sets having a common combination of dimension values for the associated dimension fields;
a dimension node means for storing information identifying the summary table means and the detail index means;
an input means for providing an input set of dimension values for identifying a desired set of the plurality of records;
a processor means connected to the memory and from the input means for accessing the memory and performing operations upon data structures; and
a control means connected to the processor means for controlling operations of the processor means,the control means including,a search means connected from the processor means and responsive to the input set of dimension values fordirecting the processor means to read the dimension node means to identify the summary table means and the detail index means, andresponsive to the identifications of the summary table means and the detail table means,directing the processor means to searchthe summary table means to find a summary node having a set of dimension values corresponding to the input set of dimension values orthe detail index means to find an index set having a set of dimension values corresponding to the input set of dimension valuesand to provide as an outputthe summary values stored in a summary node having a set of dimension values corresponding to the input set of dimension values, ora record pointer for an index set having a set of dimension values corresponding to the input set of dimension values;
a gather means connected from the processor means and responsive to a record pointer provided as an output by the processor means for directing the processor meansto read the index set of records and provide as an output the records of the index set of records identified by the record pointers contained in the detail index means found by the processor means;
a summarize means connected from the processor means and responsive to the records of the index set of records provided by the processor means for directing the processor means to extract summary information from the records of the index set of records read by the processor means; and
,a display meansconnected from the processor means and responsive tothe summary values stored in a summary node having a set of dimension values corresponding to the input set of dimension values orthe summary information extracted from the records of the index set of recordsfor directing the processor means to generate an output presentingthe summary values stored in a summary node having a set of dimension values corresponding to the input set of dimension values, orthe summary information extracted from the records of the index set of records.
1 Assignment
0 Petitions
Accused Products
Abstract
The subject invention is directed to a database system for organizing large amounts of data to be accessed by a digital computer. More particularly, a free form type database, in the form of a summarized, multikey tree, is built from files stored on the computer. After a building operation, the user obtains specified information by using the summarized database. Information in the files is divided into three categories; that is, a dimension field which comprises data to be organized, a summary field which comprises a numeric quantity on which calculations can be performed, and a non-summary field which comprises other information associated with an input record. The internal nodes of the tree summarize and organize sets of input records. Methods are provided for reducing the amount of storage space used by cutting off the tree when the size of sets go below a given threshold, and sharing parts of the tree so that each record does not appear n! times in the database.
155 Citations
10 Claims
-
1. A database management system comprising:
-
a memory for storing data structures, including a detail table means for storing a plurality of records, each of the plurality of records being addressable by record pointers and including dimension fields and summary fields, the dimension fields including dimension values, and the summary fields including numeric information; a summary table means including summary nodes for storing summary information of the summary fields for summary sets of the plurality of records; a detail index means including detail index nodes for storing the record pointers for index sets of the plurality of records, wherein each index set of the plurality of records includes a plurality of records having a common combination of dimension values for the associated dimension fields, and wherein each summary set of the plurality of records includes a plurality of index sets having a common combination of dimension values for the associated dimension fields; a dimension node means for storing information identifying the summary table means and the detail index means; an input means for providing an input set of dimension values for identifying a desired set of the plurality of records; a processor means connected to the memory and from the input means for accessing the memory and performing operations upon data structures; and a control means connected to the processor means for controlling operations of the processor means, the control means including, a search means connected from the processor means and responsive to the input set of dimension values for directing the processor means to read the dimension node means to identify the summary table means and the detail index means, and responsive to the identifications of the summary table means and the detail table means, directing the processor means to search the summary table means to find a summary node having a set of dimension values corresponding to the input set of dimension values or the detail index means to find an index set having a set of dimension values corresponding to the input set of dimension values and to provide as an output the summary values stored in a summary node having a set of dimension values corresponding to the input set of dimension values, or a record pointer for an index set having a set of dimension values corresponding to the input set of dimension values; a gather means connected from the processor means and responsive to a record pointer provided as an output by the processor means for directing the processor means to read the index set of records and provide as an output the records of the index set of records identified by the record pointers contained in the detail index means found by the processor means; a summarize means connected from the processor means and responsive to the records of the index set of records provided by the processor means for directing the processor means to extract summary information from the records of the index set of records read by the processor means; and
,a display means connected from the processor means and responsive to the summary values stored in a summary node having a set of dimension values corresponding to the input set of dimension values or the summary information extracted from the records of the index set of records for directing the processor means to generate an output presenting the summary values stored in a summary node having a set of dimension values corresponding to the input set of dimension values, or the summary information extracted from the records of the index set of records. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
Specification