Two-dimensional data storage system

• US 8,108,431 B1
• Filed: 03/24/2008
• Issued: 01/31/2012
• Est. Priority Date: 03/24/2008
• Status: Expired due to Fees

• Current Assignee: Autotelika Incorporated
• Original Assignee: Autotelika Incorporated
• Inventors: Guner, Mahmut, Rosenblitt, David
• Primary Examiner(s): Hoang, Son T
• Application Number:
  US12/053,713
• Time in Patent Office: 1,408 Days
• Field of Search: 707/792, 707/803
• US Class Current: 707/792
• CPC Class Codes: G06F 16/2282 Tablespace storage structures; Management thereof
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/24561 Intermediate data storage techniques for performance improvement

Abstract

A method providing a level of indirection that abstracts the details of physical data storage, requiring neither indexing nor contiguity of data elements in physical storage for efficient data access. Tables are organized in a diagonal pattern (with a natural implementation in electronic spreadsheets), where the region occupied by each table is expandable and shrinkable. A novel query processing mechanism applies successive expressions in a query to progressively smaller arrays of references to a table'"'"'s records. A novel method for implementing join operations avoids data replication, where the table derived from the join contains a matrix of references to values in the original tables. The derived table can subsequently be used to update the original tables via references, where this capability can be utilized in a user interface supporting atomic data entry transactions, where users may edit the derived table, and the corresponding original tables are atomically updated.

Claims

1. A computer-implemented method for implementing a data storage system based on a two-dimensional logical data storage space, implemented via a physical data storage space, containing a plurality of tables, including:

inserting and storing, by means of a computer processor, a table in the plurality of tables into the two-dimensional logical data storage space,

representing, by means of the computer processor, the position of the table via a set of two-dimensional coordinates within the two-dimensional logical data storage space,

where the two-dimensional logical data storage space contains rows and columns representing records and fields of the table, respectively,

where the position of the table is represented so that there is no portion of any other table directly positioned above or below the table, and no portion of any other table directly positioned left or right of the table within the two-dimensional logical data storage space,

where the table position is dependent only on the set of two-dimensional coordinates within the two-dimensional logical data storage space, and where contiguity of data values is required in the two-dimensional logical data storage space, but is not required in the physical data storage space,

executing, by means of the computer processor, a query comprising a plurality of expressions on the table,

where a first expression in the query is applied to the table, resulting in an array of references to a subset of the table'"'"'s records,

where each successive expression in the query is applied to the records referenced by an immediately preceding array, resulting in another array of references to another subset of the table'"'"'s records,

where indexes are not required for efficient data access, and

where a final array contains references to a subset of the table'"'"'s records satisfying the query,

deleting, by means of the computer processor, the table from the two-dimensional logical data storage space.

2. The method of claim 1 including:

inserting a record into the table,

updating the record in the table,

deleting the record from the table,

inserting a field into the table,

updating the field in the table, and

deleting the field from the table,

where the records and fields are inserted, updated and deleted without requiring table reconfiguration.

3. The method of claim 2 including:

adjusting the table'"'"'s position within the two-dimensional logical data storage space when a second table is inserted at a position prior to the table in the two-dimensional logical data storage space,

adjusting the table'"'"'s position within the two-dimensional logical data storage space when the second table is deleted at the position prior to the table in the two-dimensional logical data storage space,

adjusting the table'"'"'s position within the two-dimensional logical data storage space when the record is inserted in the second table located at the position prior to the table in the two-dimensional logical data storage space,

adjusting the table'"'"'s position within the two-dimensional logical data storage space when the record is deleted in the second table located at the position prior to the table in the two-dimensional logical data storage space,

adjusting the table'"'"'s position within said the two-dimensional logical data storage space when the field is inserted in the second table located at the position prior to the table in the two-dimensional logical data storage space, and

adjusting the table'"'"'s position within the two-dimensional logical data storage space when the field is deleted in the second table located at the position prior to the table in the two-dimensional logical data storage space.

4. The method of claim 2 where at least one field in the table is a foreign field that references a field in a second table, including:

adjusting a reference contained in the foreign field when a record is inserted in the second table referenced by the foreign field,

adjusting the reference contained in the foreign field when the record is deleted in the second table referenced by the foreign field,

adjusting the reference contained in the foreign field when a field is inserted in the second table referenced by the foreign field, and

adjusting the reference contained in the foreign field when the field is deleted in the second table referenced by the foreign field.

5. The method of claim 2 including:

cascading the insertion of the record, and

cascading the deletion of the record.

6. The method of claim 1 including:

performing a join operation on base tables in the plurality of tables,

where a table to be joined is a table derived from a prior join operation, where the table derived from the prior join operation contains references to data values in the base tables used for constructing the derived table, and where the derived table does not copy any data values contained in the base tables used for constructing the derived table.

7. The method of claim 6:

where the steps for executing the query are used to identify records in the tables to be joined matching a specific combination of join field data values, and

where the matching records are joined together and added to the derived table resulting from the join operation.

8. The method of claim 6 where a spreadsheet is used to implement the two-dimensional logical data storage space, including:

optimizing performance of the join operation by copying data from the spreadsheet to memory.

9. The method of claim 6 including:

editing data in the derived table,

where the base tables used for constructing the derived table are atomically updated using the edited data.

10. The method of claim 1, wherein the two-dimensional logical data storage space further facilitates operations of:

locking a record corresponding to a row in the two-dimensional logical data storage space, and

locking a plurality of field data values corresponding to a column in the two-dimensional logical data storage space.