Cell-based database management system

• US 10,133,758 B2
• Filed: 09/10/2014
• Issued: 11/20/2018
• Est. Priority Date: 09/10/2014
• Status: Active Grant

• Current Assignee: Boardwalktech, Inc. (Boardwalktech Software Corp.)
• Original Assignee: Boardwalktech, Inc. (Boardwalktech Software Corp.)
• Inventors: Krishnan, Ganesh, Dadbhawala, Dharmesh Kirit, Baluja, Ashish
• Primary Examiner(s): Lu, Charles E
• Application Number:
  US14/481,942
• Publication Number:
  US 20160070728A1
• Time in Patent Office: 1,532 Days
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/2322 using timestamps

Abstract

Provided are systems and methods for managing a database. In an example system, information stored in cells includes a row identifier, a column identifier, a value identifier, and a transaction identifier. The system includes a cell domain and one or more cell buffers. Both the cell domain and cell buffer include a plurality of cells, a row sequence ordering the row identifiers of cells, and a column sequence ordering the column identifiers. Additionally, the cell domain includes row and column identifier generators and transaction and value sequences. The system further includes a transfer module operable to transfer cells from a cell buffer to the cell domain, and a reader module operable to output cells, upon receiving a request buffer, from the cell domain to a response buffer. A set of constraints is applied when outputting cells to the response buffer based on the information stored in the request buffer.

Claims

1. A system for managing a database, the system comprising:

a server including at least on processor and a memory storing processor-executable codes, the server configured to;

maintain a cell-based database, the cell-based database comprising;

a cell domain, the cell domain comprising;

a plurality of cells, each cell of the plurality of cells comprising;

a row identifier;

a column identifier;

a transaction identifier; and

a value identifier;

a domain row sequence, the domain row sequence independently ordering the row identifiers of the plurality of cells;

a domain column sequence, the domain column sequence independently ordering the column identifiers of the plurality of cells;

a row identifier generator, the row identifier generator including an unordered set of unique row identifiers;

a column identifier generator, the column identifier generator including an unordered set of unique column identifiers; and

a transaction sequence, the transaction sequence comprising transaction identifiers of the plurality of cells; and

to transfer cells from a cell buffer of one or more cell buffers to the cell domain, the one or more cell buffers comprising;

a plurality of buffer cells, each buffer cell of the plurality of buffer cells comprising;

the row identifier;

the column identifier;

the transaction identifier; and

the value identifier;

a buffer row sequence, the buffer row sequence independently ordering the row identifiers of the plurality of buffer cells, the buffer now sequence being different from the domain row sequence; and

a buffer column sequence, the buffer column sequence independently ordering the column identifiers of the plurality of buffer cells, the buffer column sequence being different from the domain column sequence; and

wherein while transferring the cells from the cell buffer to the cell domain, the server is further configured to;

determine that at least one of the row identifier, the column identifier, and the transaction identifier is unspecified in at least one cell from the cell buffer;

in response to the determination, transform the at least one cell by specifying the at least one of the row identifier, the column identifier, and the transaction identifier;

determine that a row identifier in at least one cell of the cell buffer is ordered by the buffer row sequence and not ordered by the domain row sequence;

determine, based on the buffer row sequence, a predecessor of the row identifier and a successor of the row identifier, the predecessor being ordered by the domain row sequence using a first row sequence identifier and the successor being ordered by the domain row sequence using a second row sequence identifier;

generate a third row sequence identifier;

add the third row sequence identifier in the domain row sequence between the first row sequence identifier and the second row sequence identifier; and

order the row identifier by the domain row sequence using the third row sequence identifier.

2. The system of claim 1,

wherein while transferring the cells from the cell buffer to the cell domain, the server is further configured to:

determine that a column identifier in at least one cell of the cell buffer is ordered by the buffer column sequence and not ordered by the domain column sequence;

determine, based on the buffer column sequence, a column predecessor of the column identifier and a column successor of the column identifier, the column predecessor being ordered by the domain column sequence using a first column sequence identifier and the column successor being ordered by the domain column sequence using a second column sequence identifier;

generate a third column sequence identifier;

add the third column sequence identifier in the domain column sequence between the first column sequence identifier and the second column sequence identifier; and

order the column identifier by the domain column sequence using the third column sequence identifier.

3. The system of claim 2, wherein the server is further configured to:

generate a number comprising at least a time stamp and a user identifier; and

assign the number to the transaction identifier of a cell from the plurality of cells of the cell domain.

4. The system of claim 3, wherein while transferring the cells from the cell buffer to the cell domain, a single transaction identifier is generated for all cells from the cell buffer.

5. The system of claim 3, wherein while transferring cells from the cell buffer to the cell domain, the cells from the cell buffer are added to the cell domain.

6. The system of claim 3, wherein while transferring cells from the cell buffer to the cell domain, for any cell from the cell buffer for which the row identifier unspecified and an order of the cell in the buffer row sequence of the cell buffer is specified, a new row identifier is generated.

7. The system of claim 3, wherein while transferring cells from the cell buffer to the cell domain, for any cell from the cell buffer for which the column identifier is not specified and an order of the cell in the buffer column sequence is specified, a new column identifier is generated.

8. The system of claim 3, wherein while transferring cells from the cell buffer to the cell domain, if at least one of the cells from the cell buffer cannot be transferred to the cell domain then all of the cells from the cell buffer are not transferred to the cell domain.

9. The system of claim 3, wherein the server is further configured to:

receive a request buffer, the request buffer including a cell buffer from the one or more cell buffers; and

output a response buffer, the response buffer including a cell buffer from the one or more cell buffers.

10. The system of claim 9, wherein:

cells in the request buffer include at least one of the following;

a row identifier, a column identifier, and a transaction identifier; and

cells in the response buffer include all of the following;

a row identifier, a column identifier, a transaction identifier, and a value identifier.

11. The system of claim 9, wherein:

cells in the request buffer include a transaction identifier;

the response buffer comprises cells from the cell domain, wherein a maximum of transaction identifiers for the cells does not exceed the transaction identifier of the cells in the request buffer;

a minimum of transaction identifiers of cells, the cells being associated with a cell domain and not being associated with the response buffer, exceeds the transaction identifier of cells in the request buffer;

the column identifiers of the cells in the response buffer are ordered with the buffer column sequence of the cell buffer; and

the row identifiers of the cells in the response buffer are ordered with the buffer row sequence of the cell buffer.

12. The system of claim 9, wherein:

the request buffer comprises at least a first cell and a second cell, the transaction identifier of the first cell being less than a transaction identifier of the second cell; and

the response buffer comprises all cells from the cell domain, wherein a transaction identifier of the cells is between the transaction identifier of the first cell and the transaction identifier of the second cell.

13. The system of claim 9, wherein:

at least one cell in the request buffer has a specified row identifier; and

the column identifiers of the cells in the response buffer are ordered with the buffer column sequence of the cell buffer.

14. The system of claim 9, wherein:

at least one cell in the request buffer has a column identifier specified; and

the row identifiers of the cells in the response buffer are ordered with the buffer row sequence of the cell buffer.

15. The system of claim 9, wherein:

at least one cell in the request buffer has a value identifier specified;

the row identifiers of the cells in the response buffer are ordered with the buffer row sequence of the cell buffer; and

the column identifiers of the cells from the response buffer are ordered by the buffer column sequence of the cell buffer.

16. A non-transitory computer-readable storage medium having embodied thereon a program, the program being executable by a processor to perform a method for managing a database, the method comprising:

transferring cells from a cell buffer of one or more cell buffers to a cell-based database, the cell-based database comprising a cell domain;

receiving a request buffer, the request buffer including a cell buffer from the one or more cell buffers; and

outputting a response buffer, the response buffer including a cell buffer from the one or more cell buffers; and

wherein

the cell domain comprises;

a plurality of cells, each cell of the plurality of cells comprising;

a row identifier;

a column identifier;

a transaction identifier, the transaction identifier comprising a time identifier and a user identifier; and

a value identifier;

a domain row sequence, the domain row sequence independently ordering the row identifiers of the plurality of cells;

a domain column sequence, the domain column sequence independently ordering the column identifiers of the plurality of cells;

a row identifier generator, the row identifier generator including an unordered set of unique row identifiers;

a column identifier generator, the column identifier generator including an unordered set of unique column identifiers; and

a transaction sequence, the transaction sequence comprising transaction identifiers of the plurality of cells; and

the one or more cell buffers comprise;

a plurality of buffer cells, each buffer cell of the plurality of buffer cells comprising;

the row identifier;

the column identifier;

the transaction identifier, the transaction identifier comprising a buffer time identifier and the buffer user identifier; and

the value identifier;

a buffer row sequence, the buffer row sequence independently ordering the row identifiers of the plurality of buffer cells, the buffer row sequence being different from the domain row sequence; and

a buffer column sequence, the buffer column sequence independently ordering the column identifiers of the plurality of buffer cells, the buffer column sequence being different from the domain column sequence; and

wherein the transferring includes;

determining that at least one of the row identifier, the column identifier, and the transaction identifier is unspecified in at least one cell from the cell buffer;

in response to the determination, transforming the at least one cell by specifying the at least one of the row identifier, the column identifier, and the transaction identifier;

determining that a row identifier in at least one cell of the cell buffer is ordered by the buffer row sequence and not ordered by the domain row sequence;

determining, based on the buffer row sequence, a predecessor of the row identifier and a successor of the row identifier, the predecessor being ordered by the domain row sequence using a first row sequence identifier and the successor being ordered by the domain row sequence using a second row sequence identifier;

generating a third row sequence identifier;

adding the third row sequence identifier in the domain row sequence between the first row sequence identifier and the second row sequence identifier;

ordering the row identifier by the domain row sequence using the third row sequence identifier;

determining, that a column identifier in at least one cell of the cell buffer is ordered by the buffer column sequence and not ordered by the domain column sequence;

determining, based on the buffer column sequence, a column predecessor of the column identifier and a column successor of the column identifier, the column predecessor being ordered by the domain column sequence using a first column sequence identifier and the column successor being ordered by the domain column sequence using a second column sequence identifier;

generating a third column sequence identifier;

adding the third column sequence identifier in the domain column sequence between the first column sequence identifier and the second column sequence identifier; and

ordering the column identifier by the domain column sequence using the third column sequence identifier.