Methods and apparatus for storing and manipulating variable length and fixed length data elements as a sequence of fixed length integers

• US 7,178,100 B2
• Filed: 12/10/2001
• Issued: 02/13/2007
• Est. Priority Date: 12/15/2000
• Status: Expired due to Fees

• Current Assignee: Charles Call
• Original Assignee: Charles Call
• Inventors: Call, Charles G.
• Primary Examiner(s): Hudspeth; David
• Assistant Examiner(s): Sked; Matthew J.
• Application Number:
  US10/012,815
• Publication Number:
  US 20020143521A1
• Time in Patent Office: 1,891 Days
• Field of Search: None
• US Class Current: 715/210
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]
• CPC Class Codes: G06F 40/149 Adaptation of the text data for streaming purposes, e.g. Efficient XML Interchange [EXI] format
• CPC Class Codes: G06F 40/221 Parsing markup language streams streaming G06F40/149
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

Apparatus for storing and processing a plurality of data items each comprising supplied data values organized in one or more fields each of which stores typed data. Character strings and natural language text are converted to numerical token values in an array of fixed length integers and other forms of typed data (real numbers, dates, times, boolean values, etc.) are also converted to integer form and stored in the array. Stored metadata specifies the data type of all data in the integer array to enable each integer to be rapidly accessed and interpreted. When fixed length data types are present, the metadata specifies location, size and type of each fixed length element. When variable length data is stored in the integer array, size and location data stored in the integer array is accessed to rapidly and directly access the variable size data. The presence of implicit or explicit size information for each data structure, including variable size structures, speeds processing by eliminating the need to scan the data for delimiters, and by reducing the processing needed to perform memory allocation, data movement, lookup operations and data addressing functions. Data stored in the integer array is subdivided into items, and items are subdivided into fields. Items may be organized into more complex data structures, such as relational tables, hierarchical object structures, linked lists and trees, and the like, using special fields called links which identify other referenced items.

Claims

1. Apparatus for storing and processing a plurality of data items each comprising supplied data values organized in one or more fields, at least some of said fields containing variable length data values, and at least a given one of said supplied data values comprising a sequence of character values, at least some of which represent natural language text consisting of a sequence of natural language words, said apparatus comprising, in combination,

a random access memory for storing an array of fixed-length binary integers,

a first data converter for transforming each of said data values in each of said fields into a sequence of zero or more fixed-length integers and for storing each such sequence in said random access memory, said first data converter including means for convening each given one of said natural language words into one of said integers having a value which uniquely specifies said given natural language word,

means for storing the number of integers in the sequence of integers representing the contents of each field containing said variable length data values,

means responsive to the designation of a particular one of said natural language words for accessing a selected sequence of integers representing said given one of said supplied data values in a particular one of said fields by performing a search for the integer value representing said particular one of said words in said array, and

a second data converter for transforming said selected sequence of integers into said sequence of character values representing said supplied data values in said particular one of said fields, said second data converter including means for transforming a sequence of integers representing a corresponding sequence of natural language words into the corresponding sequence of character values representing said natural language text.

2. Apparatus as set forth in claim 1 wherein each of said fields contains typed data, wherein said random access memory contains metadata specifying the data type of each of said fields, and wherein said first data converter and said second data converter perform transformations between character data representing supplied data values and sequences of one or more integers in accordance with the specified data type of each field containing data being transformed.

3. Apparatus as set forth in claim 1 wherein at least some of said data items include one or more link values each of which identifies a referenced data item in said plurality of data items and wherein each of said link values is transformed by said first data converter into an integer which designates the location in said random access memory of the stored sequence of integers representing said referenced data item.

4. Apparatus as set forth in claim 3 wherein at least some of said link values specify parent-child relationships between different data items in said plurality of data items.

5. Apparatus as set forth in claim 3 wherein at least some of said link values specify linked listings of different data items in said plurality of data items.

6. Apparatus as set forth in claim 1 wherein said character values are expressed in Extended Markup Language and wherein said first data conversion means transfonns said character values into a sequence of groups of integer values each representing an XML element, each given one of said groups representing an XML element including:

at least one integer designating the name of said XML element and the number of integer values in said given one of said groups, and

a sequence of one or more integer values designating the content of said XML element.

7. Apparatus for storing and processing a plurality of data items each comprising supplied data values organized in one or more fields, at least a given one of said supplied data values comprising a sequence of character values, at least some of which represent natural language text consisting of a sequence of natural language words, and at least a further one of said data items including one or more link values each of which identifies a referenced data item in said plurality of data items, said apparatus comprising, in combination,

a random access memory for storing an array of fixed-length binary integers,

a first data converter for transforming each of said data values in each of said fields into a sequence of zero or more fixed-length integers and for storing each such sequence in said random access memory, said first data converter including means for converting each given one of said natural language words into one of said integers having a value which uniquely specifies said given natural language word, and wherein each of said link values is transformed by said first data converter into an integer which designates the location in said random access memory of the stored sequence of integers representing said referenced data item,

means responsive to the designation of a particular one of said natural language words for accessing a selected sequence of integers representing said given one of said supplied data values in a particular one of said fields by performing a search for the integer value representing said particular one of said words in said array, and

a second data converter for transforming said selected sequence of integers into said sequence of character values representing said supplied data values in said particular one of said fields, said second data converter including means for transforming a sequence of integers representing a corresponding sequence of natural language words into the corresponding sequence of character values representing said natural language text.

8. Apparatus as set forth in claim 7 wherein at least some of said link values specify parent-child relationships between different data items in said plurality of data items.

9. Apparatus as set forth in claim 7 wherein at least some of said link values specify linked listings of different data items in said plurality of data items.

10. Apparatus as set forth in claim 7 wherein each of said fields contains typed data, wherein said random access memory contains metadata specifying the data type of each of said fields, and wherein said first data converter and said second data converter perform transformations between character data representing supplied data values and sequences of one or more integers in accordance with the specified data type of each field containing data being transformed.

11. Apparatus as set forth in claim 7 wherein said character values are expressed in Extended Markup Language and wherein said first data conversion means transforms said character values into a sequence of groups of integer values each representing an XML element, each given one of said groups representing an XML element including:

at least one integer designating the name of said XML element and the number of integer values in said given one of said groups, and

a sequence of one or more integer values designating the content of said XML element.

12. Apparatus for storing and processing a plurality of data items each comprising supplied data values organized in one or more fields, at least a given one of said supplied data values comprising a sequence of character values expressed in Extended Markup Language, at least some of which represent natural language text consisting of a sequence of natural language words, said apparatus comprising, in combination,

a random access memory for storing an array of fixed-length binary integers,

a first data converter for transforming each of said data values in each of said fields into a sequence of zero or more fixed-length integers and for storing each such sequence in said random access memory, said first data converter including means for converting each given one of said natural language words into one of said integers having a value which uniquely specifies said given natural language word, and wherein said first data conversion means transforms said character values into a sequence of groups of integer values each representing an XML element, each given one of said groups representing an XML element including:

at least one integer designating the name of said XML element and the number of integer values in said given one of said groups, and

a sequence of one or more integer values designating the content of said XML element,

means responsive to the designation of a particular one of said natural language words for accessing a selected sequence of integers representing said given one of said supplied data values in a particular one of said fields by performing a search for the integer value representing said particular one of said words in said array, and

a second data converter for transforming said selected sequence of integers into said sequence of character values representing said supplied data values in said particular one of said fields, said second data converter including means for transforming a sequence of integers representing a corresponding sequence of natural language words into the corresponding sequence of character values representing said natural language text.

13. Apparatus as set forth in claim 12 wherein each of said fields contains typed data, wherein said random access memory contains metadata specifying the data type of each of said fields, and wherein said first data converter and said second data converter perform transformations between character data representing supplied data values and sequences of one or more integers in accordance with the specified data type of each field containing data being transformed.