Encoding semi-structured data for efficient search and browsing

• US 20080065596A1
• Filed: 10/12/2007
• Published: 03/13/2008
• Est. Priority Date: 02/26/2001
• Status: Active Grant

• Current Assignee: DB Software, Inc.
• Original Assignee: Ori Software Development Ltd
• Inventors: Franklin, Michael, Sample, Neal, Cooper, Brian, Shadmon, Moshe
• Granted Patent: US 8,065,308 B2
• Time in Patent Office: Days
• US Class Current: 707/2
• CPC Class Codes: G06F 16/81 Indexing, e.g. XML tags; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/835 Query processing
• CPC Class Codes: Y10S 707/955 Object-oriented
• CPC Class Codes: Y10S 707/956 Hierarchical
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A method for encoding XML tree data that includes the step of encoding the semi-structured data into strings of arbitrary length in a way that maintains non-structural and structural information about the XML data, and enables indexing the encoded XML data in a way that facilitates efficient search and browsing.

Claims

1. A method for transforming Extensible Markup Language (XML) documents for querying;

the method comprising;

a. receiving an XML document;

b. transforming said XML document into transformed objects;

c. each of said transformed objects include non-structural and structural information from said XML document.

2. The method of claim 1 wherein said transformed objects are the keys to be indexed, constituting an index, to allow efficient access to information of interest.

3. The method of claim 2, wherein said index contains a parent/child relationship of components from the said XML document;

said components may be non-structural and/or structural information from the said XML document.

4. The method of claim 1, wherein said step of transforming said XML document includes creating or updating an index to include hierarchical information about said XML document.

5. The method of claim 1, wherein said step of transforming said XML document includes creating an index of order information about said XML document.

13. The method of claim 2, wherein said index is a designated index.

16. The method of claim 2, wherein said index is a layered index.

19. The method of claim 2, wherein said index is based on a Patricia Trie.

6. A method for transforming Extensible Markup Language (XML) documents for querying;

the method comprising;

a. receiving an XML document as an input;

b. transforming the XML document into keys;

each of said keys can include non-structural and/or structural information from said XML document;

said method facilitates access to searched data using the said keys.

7. The method of claim 6, wherein said transformation creates an index to allow efficient search.

8. The method of claim 6, wherein said transformation creates an index containing parent/child relationship for elements in the XML document.

12. The method of claim 7, wherein said index is a designated index.

15. The method of claim 7, wherein said index is a layered index.

18. The method of claim 7, wherein said index is based on a Patricia Trie.

9. A method for transforming an XML document to enable search of the XML document or components of the XML document, the method comprising:

a transforming the XML document into a logical tree in which elements of said XML document are nodes of the logical tree;

b each of said nodes represents non-structural and/or structural information from said XML document;

c. labeling nodes of said logical tree with identifiers;

d. creating an index to facilitate efficient search to data in said logical tree.

10. The method of claim 9, wherein said index includes parent/child relationship of nodes.

11. The method of claim 9, wherein said index is a designated index.

14. The method of claim 9, wherein said index is a layered index.

17. The method of claim 9, wherein said index is based on a Patricia Trie.

20. A method for mapping semi-structured data into keys comprising:

for each determined element within the semi-structured data;

creating one or more keys for that element, each of the said keys may include structural and/or non-structural information associated with the said element.

21. A computer readable recording medium containing a computer program product that includes a storage for storing index over keys representing elements of semi-structured data;

said keys were created according to the method in claim 20.

22. The computer program product of claim 21, wherein said index is a designated index.

23. The computer program product of claim 21, wherein said index is a layered index.

24. The computer program product of claim 21, wherein said index is based on a Patricia Trie.

25. The computer program product of claim 21, wherein said index is partitioned into blocks;

the structure within the blocks of the said index is based on a Patricia Trie.