Back to results
US 7,627,589 B2Granted
High performance XML storage retrieval system and method
AssigneePalo Alto Research Center Incorporated
InventorRobert D. Cheslow
Life of this patent
Estimating the term…
Abstract
A binary object XML repository for storage and retrieval of data in XML documents includes import manager capabilities for converting file formats to XML. Indexing capabilities encode XML document data in a binary data structure for storage within lexicon(s) in the form of tokens and token types, with a token including data elements corresponding to XML syntax. The lexicon(s) also assigns token identifier numbers, which sequence module(s) store in an original sequence. Postings module(s) map the token identifier numbers to the token identifier's position in the original sequence.
Claims19
A computer system for storage and retrieval of data in extensible markup language (XML) documents, comprising:
- a memory;
- and
- a processor operatively coupled to the memory and configured to execute computer executable program modules, including:
- an import manager module configured to convert at least one file format to XML code defined by an XML schema;
- an indexer module configured to encode document data comprised in the XML code defined by the XML schema into a binary data structure, comprising:
- a scoping submodule configured to determine scope within the document data and the scope comprises at least one well-formed fragment of the XML code;
- and
- a storage submodule configured to store the binary data structure by the scope;
- a lexicon module configured to store at least one token and at least one token type and assigning at least one token identifier number, wherein said token includes data elements corresponding to XML syntax and said at least one token type reflects at least one component of XML syntax;
- a sequence module configured to store said at least one token identifier number in an original sequence;
- a determination module configured to determine whether said token is included in a lexicon;
- a token identifier number retrieval module configured to retrieve said token identifier number from said lexicon if said token is included in said lexicon, appending said token identifier number to said original sequence, and storing said token identifier number in the list for the XML data element;
- a lexicon storage module configured to store said token and said token type in the lexicon if said token is not included in said lexicon, assigning a unique token identifier to said token, appending said token identifier to the original sequence, and storing said token identifier in the list for the XML data element;
- a postings module configured to map said at least one token identifier number to a position of said token identifier number in said original sequence, wherein the postings module further inverts the position information from a list of tokens in an XML data element to map at least one selected token to all the XML data elements in which the selected token appears;
- a regenerator module configured to retrieve said at least one token for the scope in said original sequence, comprising:
- an insertion submodule configured to insert the at least one token into an output stream for each such well-formed fragment of the XML code;
- and
- a return submodule configured to return completed XML markup upon reading an end of the scope;
- a XML grammar state machine module configured to use token type information to compute the XML syntax for regenerating the XML code, comprising:
- a reading submodule configured to read the next token identifier number from the original sequence;
- a retrieval submodule configured to retrieve the token and token type for a token identifier number from the lexicon;
- and
- a token insertion submodule configured to insert said token into the output stream with the XML markup syntax appropriate for type.
20 more elements
A computer-implemented method for storage and retrieval of data in extensible markup language (XML) documents, comprising:
- receiving and converting at least one file format to XML code defined by an XML schema;
- encoding XML document data comprised in the XML code defined by the XML schema into a binary data structure, comprising:
- determining a scope within the document data and the scope comprises at least one well-formed fragment of the XML code;
- and
- storing the binary data structure by the scope;
- storing at least one token and at least one token type and assigning at least one token identifier number, wherein said at least one token includes data elements corresponding to XML syntax and said at least one token type reflects at least one component of XML syntax;
- storing said at least one token identifier number in an original sequence;
- determining whether said token is included in a lexicon;
- retrieving said token identifier number from said lexicon if said token is included in said lexicon, appending said token identifier number to said original sequence, and storing said token identifier number in the list for the XML data element;
- storing said token and said token type in the lexicon if said token is not included in said lexicon, assigning a unique token identifier to said token, appending said token identifier to the original sequence, and storing said token identifier in the list for the XML data element;
- mapping said at least one token identifier number to a position of said token identifier in said original sequence;
- inverting the position information from a list of tokens in an XML data element to map at least one selected token to all the XML data elements in which the selected token appears;
- initiating document regeneration for the scope, comprising:
- inserting the at least one token into an output stream for each such well-formed fragment of the XML code;
- and
- returning completed XML markup upon reading an end of the scope;
- and
- using token type information to compute the XML syntax for regenerating the XML code, comprising:
- reading the next token identifier number from the original sequence;
- retrieving the token and token type for a token identifier number from the Lexicon;
- and
- inserting said token into the output stream with the XML syntax appropriate for type.
19 more elements
A computer-readable storage medium storing computer program code that, when executed by a computer, causes the computer to perform:
- converting at least one file format to extensible markup language (XML) code defined by an XML schema;
- encoding XML document data comprised in the XML code defined by the XML schema into a binary data structure, comprising:
- determining a scope within the document data and the scope comprises at least one well-formed fragment of the XML code;
- and
- storing the binary data structure by the scope;
- storing at least one token and at least one token type and assigning at least one token identifier number, wherein said at least one token includes data elements corresponding to XML syntax and said at least one token type reflects at least one component of XML syntax;
- storing said at least one token identifier number in an original sequence;
- determining whether said token is included in a lexicon;
- retrieving said token identifier number from said lexicon if said token is included in said lexicon, appending said token identifier number to said original sequence, and storing said token identifier number in the list for the XML data element;
- storing said token and said token type in the lexicon if said token is not included in said lexicon, assigning a unique token identifier to said token, appending said token identifier to the original sequence, and storing said token identifier in the list for the XML data element;
- mapping said at least one token identifier number to a position of said token identifier in said original sequence;
- inverting the position information from a list of tokens in an XML data element to map at least one selected token to all the XML data elements in which the selected token appears;
- initiating document regeneration for the scope, comprising:
- inserting the at least one token into an output stream for each such well-formed fragment of the XML code;
- and
- returning completed XML markup upon reading an end of the scope;
- and
- using token type information to compute the XML syntax for regenerating the XML, code, comprising:
- reading the next token identifier number from the original sequence;
- retrieving the token and token type for a token identifier number from the Lexicon;
- and
- inserting said token into the output stream with the XML syntax appropriate for type.
19 more elements
Dependencies are inferred from the claim text.