Method of storing and flattening a structured data document

• US 6,792,428 B2
• Filed: 10/12/2001
• Issued: 09/14/2004
• Est. Priority Date: 10/13/2000
• Status: Expired due to Fees

• Current Assignee: Xpriori LLC
• Original Assignee: Xpriori LLC
• Inventors: Brandin, Christopher Lockton
• Primary Examiner(s): JUNG, DAVID YIUK
• Application Number:
  US09/977,267
• Publication Number:
  US 20020052878A1
• Time in Patent Office: 1,068 Days
• Field of Search: 707/1-10, 707/200-206, 707/100-104, 715/513-525
• US Class Current: 1/1
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]
• CPC Class Codes: G06F 40/154 Tree transformation for tree-structured or markup documents, e.g. XSLT, XSL-FO or stylesheets
• 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 method of flattening a structured data document includes the steps of receiving a structured data document. Next, a first data entry is searched for by the system. When the first data entry is found, it is determining if an attribute is defined before the first data entry. When the attribute is defined before the first data entry, a first line containing all open tags before the attribute and the attribute is created. A record indicator is stored on the first line.

Claims

1. A method of flattening a structured data document, comprising the steps of:

a) receiving a structured data document;

b) searching for a first data entry;

c) when the first data entry is found, determining if an attribute is defined before the first data entry; and

d) when the attribute was defined before the first data entry, creating a first line containing all open tags before the attribute and the attribute.

2. The method of claim 1, further including the steps of:

e) determining if a second attribute is defined before the first data entry;

f) when the second attribute is not defined before the first data entry, creating another line containing a set of open tags up to the first data entry.

3. The method of claim 1, wherein step (b) further includes the step of:

b1) defining a record in the structured data document.

4. The method of claim 3, further including the steps of:

g) adding the first data entry and a record indicator to the another line.

5. The method of claim 4, further including the steps of:

h) searching for a next data entry;

i) when the next data entry is found, determining if the next data entry is in a different record than the first data entry;

j) when the next data entry is in the different record, creating a next line containing all open tags before the attribute and the attribute.

6. The method of claim 5, further including the steps of:

k) storing all open tags preceding the next data entry in a line after the next line and the next data entry and a new record indicator;

l) repeating the steps to form a flattened document.

7. The method of claim 6, further including the steps of:

m) receiving a query having two targets;

n) determining if a first target entries and a second target entries have a common record indicator;

o) when one of the first target entries and the second target entries have the common record indicator, retrieving a record associated with the common record indicator.

8. A method of storing a flattened structured data document, comprising the steps of:

a) receiving the flattened structured data document having a plurality of lines, each of the lines having a tag, a data entry and a format character;

b) creating a map index;

c) determining if the data entry is unique;

d) when the data entry is not unique, determining if a duplicates flag is set;

e) when the duplicates flag is set, incrementing a duplicates count;

f) calculating a transform of the data entry with an instance count to form a first instance transform; and

g) storing a first map pointer in the map index at an address associated with the first instance transform.

9. The method of claim 8, further including the step of:

h) storing an association at the address in the map index.

10. The method of claim 9, further including the steps of:

i) calculating a transform of the second data entry with the association to form a first associated data entry.

11. The method of claim 10, further including the steps of:

j) receiving a query having two targets;

k) determining if a first target has fewer entries than a second target;

m) when the first target has fewer entries than the second target, looking up a first instance of the first target to find a first association;

n) transforming the second target with the association to form a second target association;

o) performing a lookup at an address pointed to by the second target association;

p) when the entry for the second target is found, determining a match has been found.

12. The method of claim 11, further including the steps of:

q) when the second target is not found, looking up a second instance of the first target to find a second association;

r) repeating steps n through p with the second association.

13. A system for storing a flattened structured data document, comprising:

a flattener receiving the structured data document;

a parser connected to the flattener and locating a data element;

a transform generator receiving the data element;

a map store connected to the parser and the transform generator;

a map index connected to the parser and the transform generator; and

a dictionary connected to the map store.

14. The system of claim 13, wherein the flattener includes a record indicator with each line.

15. The system of claim 14, wherein each record starts with a line containing any pushed attributes.

16. The system of claim 15, wherein the map index contains an entry for the data element, the entry is located at an address associated with a transform of the data element.

17. The system of claim 16, wherein the map index contains a second entry for the data element with an instance count, the second entry is located at a second address associated with a second transform of the data element with the instance count.

18. The system of claim 17, wherein the map index contains a third entry for a second data element in a same record as the data element.

19. The system of claim 18, wherein the third entry is located at a third address associated with a third transform of the second data element with an association from the first data element.