Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-07-13
2002-12-31
Corrielus, Jean M. (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06502101
ABSTRACT:
TECHNICAL FIELD
The present invention relates generally to the conversion of highly hierarchical data structures into less hierarchical data structures. More particularly, the present invention relates to receiving an input file in a standard format and converting it into a flat table data structure.
BACKGROUND OF THE INVENTION
Historically large database users utilized database management programs written for specific applications with little thought to standardization. Through the years as more and more data was added, the databases resulting from these database management programs grew larger and larger and have become known as legacy systems. As the organizations utilizing these large proprietary databases became more automated and computerized, the need to share data between departments, functions, subsidiaries and sister organizations became more and more prevalent. Due to this need, a standard database formats were developed.
One such standard format developed is XML. XML is a very hierarchical data base format, which includes a multitude of data structures which in turn contain data sub-structures, which in turn may contain data sub-substructures. Due to the advent of this standard database format, many computer users have converted the aforementioned proprietary legacy database systems to the standard XML database format.
Along with the advent of the personal computer on the modern business landscape came many useful application programs including those utilizing electronic spreadsheets. Electronic spreadsheets typically operate on data contained in a matrix of cells comprising columns and rows. Generally, this data format is contained in a single table and is a very flat data structure in that the data is not maintained in a hierarchical data structure utilized by XML.
With the ease of availability of the personal computer, many users have become proficient in their use and more specifically, in using electronic spreadsheet application programs. While the electronic spreadsheets offer many advantages over prior conventional means, they utilizes a flat data structure. With huge amounts of data stored in hierarchical formats such as XML, the electronic spreadsheet with its flat data structure had no means to access this wealth of data thus a means for accessing it with a spreadsheet has become desirable. While other programs have parsed data contained in the XML format, none have converted XML formatted data into a flat data structure suitable for the use by an electronic spreadsheet.
Therefore, there remains a need in the art for a method for converting a database structure that is arbitrarily hierarchical into a flat data structure. This flat data structure should be suitable for use in electronic spreadsheet tables.
SUMMARY OF THE INVENTION
The present invention fulfills the need in the art for converting a database structure that is arbitrarily hierarchical into a flat data structure suitable for use in electronic spreadsheet tables.
In accordance with one aspect of the present invention, a system and method are provided for converting a hierarchical data structure into a flat data structure. The format of the hierarchical data structure may be XML.
First, the hierarchical data structure is converted into an input data tree comprising nodes. These nodes contain the data elements of the hierarchical data structure and are linked together in a parent-child relationship. This parent-child relationship is derived from the hierarchical data structure.
Next, a shape tree is constructed corresponding to the input data tree by collapsing nodes of the input data tree containing redundant elements into one node. Once the shape tree is constructed, it is then annotated with properties describing the hierarchical relationships between elements of the input data tree. These properties may include, 1) a first property specifying the maximum number of times a given element appears inside its parent across the entire input tree, 2) a second property set equal to false if and only if the node's first property is greater than zero or if the node has any child nodes and anyone of said child nodes have a second property set to false, and 3) a third property set to true if every occurrence of the element corresponding to the node contains numeric data.
Finally, a list of column names are built for the flat data structure deriving the column names by tracing the shape tree. Once the column names are built, the data is emitted from the input data tree into proper columns and row of the flat data structure. The flat data structure may be readily usable by an electronic spreadsheet.
REFERENCES:
patent: 4555771 (1985-11-01), Hayashi
patent: 5295261 (1994-03-01), Simonetti
patent: 5438511 (1995-08-01), Maxwell et al.
patent: 6263332 (2001-07-01), Nasr et al.
patent: 6424979 (2002-07-01), Livingston et al.
Bohannon et al., “From XML Schema to relations: A cost-based approach to XML Storage”, IEEE, 2002.*
Chow et al., “Index Design for structured documents based on abstaction”, IEEE, Feb. 1992.*
Su et al., “XEM: Managing the evolution of XML document”, IEEE, pp. 103-110.
Allen Jason
Cahill Jason
Verprauskus Andy
Corrielus Jean M.
Hornsby, III Alton
Merchant & Gould
Microsoft Corporation
LandOfFree
Converting a hierarchical data structure into a flat data... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Converting a hierarchical data structure into a flat data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Converting a hierarchical data structure into a flat data... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2960877