Data structure for a hardware database management system

• US 20050234882A1
• Filed: 04/20/2004
• Published: 10/20/2005
• Est. Priority Date: 04/20/2004
• Status: Abandoned Application

• Current Assignee: InfiniDB, Inc.
• Original Assignee: InfiniDB, Inc.
• Inventors: Bennett, Victor A., Petersen, Frederick R.
• Application Number:
  US10/827,744
• Publication Number:
  US 20050234882A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/21 Design, administration or maintenance of databases
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

A data structure for a hardware database system is described. The data structure is made up of multiple sub-trees interconnected to form a graph structure. Each sub-tree begins at a memory location, or root address. Next the sub-tree includes profile information relevant to the sub-tree, such profile information can include, but is not limited to, information on the type of data being stored, the number of entries in the sub-tree, privilege information for accessing the sub-tree, etc. After the profile information the sub-trees contain search strings, or differential bits that lead to each of the entries in the sub-tree. Each search string ends in a result string. The result string can be actual data, can be a pointer to another sub-tree, can be a function call, or can be any other useful data or entry.

Claims

1. A data structure for storing data in a database comprising:

at least one sub-tree, each of the at least one sub-tree being associated with a distinct root tree address and including profile data storing information about the sub-tree, signature strings for matching a search object against entries in the sub-tree, and results strings representing the entries in the sub-tree.

2. The data structure of claim 1 wherein the results strings are the data entries in the database.

3. The data structure of claim 1 wherein the results strings are the root addresses of other sub-trees.

4. The data structure of claim 1 wherein the sub-tree further includes a tree id.

5. The data structure of claim 1 wherein the profile data includes information about the data type stored in the sub-tree.

6. The data structure of claim 1 wherein the profile data includes information about privileges for accessing the sub-tree.

7. The data structure of claim 1 wherein one sub-tree points to the root address of other sub-trees.

8. The data structure of claim 7 wherein a sub-tree represents a column in a relational table.

9. The data structure of claim 1 wherein the sub-strings represent the differential bits for each entry in the sub-tree.

10. A method for creating a data structure in hardware database, the method comprising:

selecting a root address for a sub-tree;

writing profile information for the sub-tree accessible by the root address; and

creating signature strings in the sub-tree, each signature string leading to a result string, wherein the result string represents an entry in the sub-tree.

11. The method of claim 10 further comprising after creating, repeating the method to create additional sub-trees, wherein the results strings contain the root addresses of other sub-trees, thereby linking the sub-trees into a graph structure.

12. The method of claim 10 wherein the entry in the sub-tree is data stored in the database.

13. The method of claim 12 wherein the profile information includes privilege information.

14. A data structure for storing data in a database in memory comprising:

a plurality of sub-trees containing entries in the database, each sub-tree including a root address, profile data, signature strings and results strings, wherein the root address is the address in memory where the sub-tree begins, the profile data contains information about the sub-tree, the signature strings are branches in the sub-tree leading to each entry in the sub-tree, and results strings representing each entry in the sub-tree;

such that each sub-tree can refer to other sub-trees by using the appropriate root address as the results string.

15. The data structure of claim 14 wherein the profile data includes privilege information for accessing the sub-tree.

16. The data structure of claim 14 wherein a sub-tree represents a column in a relational table.

17. The data structure of claim 14 wherein the sub-strings represent the differential bits for each entry in the sub-tree.