Method and system for implementing an enhanced database

Abstract

A database is created from a set of data by identifying the patterns in the data set, storing the patterns in a memory device, and generating a representation of the database structure using pointers to the stored patterns. The use of pointers to store the patterns can greatly reduce the amount of memory or other space required to store the data set by replacing duplicate patterns with additional pointers, which are normally considerably smaller in size. In addition, the use of pointers may allow for more rapid searching, sorting, and other operations on the database. The representation of the database may use pointers in a tree structure to identify nodes and reduce searching and other operations. A tree structure representation of a table may use a pointer to a pattern for the base leaf node (e.g., nodes that do not branch) while using pointer pairs to represent branching nodes.

1 . A method for identifying a new pattern for a table of a database, comprising: 
 identifying a first subordinate pattern and a second subordinate pattern for a data pattern;    determining if the first subordinate pattern is new, wherein the first subordinate pattern is compared to a first set of patterns;    determining, where the first subordinate pattern is not new, if the second subordinate pattern is new, wherein the second subordinate pattern is compared to a second set of patterns;    determining, where the first subordinate pattern is not new and the second subordinate pattern is not new, if the data pattern is new, wherein the data pattern is compared to a third set of patterns, the third set of patterns composed of at least one pattern pair containing a left pattern from the first set of patterns and a right pattern from the second set of patterns;    storing the data pattern in the third set of patterns with a frequency value equal to one where at least one of the first subordinate pattern is new, the second subordinate pattern is new, and the data pattern is new; and    incrementing the frequency value for the data pattern in the third set of patterns where the first subordinate pattern is not new, the second subordinate pattern is not new and the data pattern is not new.    
     
     
         2 . A method for identifying a new pattern for a table of a database, comprising: 
 identifying a first subordinate pattern and a second subordinate pattern for a data pattern;    retrieving a first frequency value for the first subordinate pattern, wherein the first frequency value is one if the first subordinate pattern is new;    retrieving, where the first frequency value is greater than one, a second frequency value for the second subordinate pattern, wherein the second frequency value is one if the second subordinate pattern is new;    determining, where the first frequency value is greater than one and the second frequency value is greater than one, if the data pattern is new, wherein the data pattern is compared to a set of patterns;    storing the data pattern in the set of patterns with a pattern frequency value equal to one where at least one of the first frequency value is one, the second frequency value is one, and the data pattern is new; and    incrementing the pattern frequency value for the data pattern in the set of patterns where the first frequency value is greater than one and the second frequency value is greater than one and the data pattern is not new.    
     
     
         3 . A method for designing a table of a database from a tree structure, comprising: 
 determining a set of values for a field of the table;    computing at least one of a cardinality and a correlation for the field, the correlation of the field determined in relation to a second field;    grouping the field with the second field according to at least one of the computed cardinality and the computed correlation of the field;    building a sub-tree for the grouping of the field with the second field;    assembling a final tree from the sub-tree; and    building the table from the final tree.    
     
     
         4 . A method for designing a table of a database from a tree structure, comprising: 
 determining at least one field for the table;    computing the cardinality for the field;    sorting the at least field into an ascending list based on the computed cardinality of the field;    generating a tree from the ascending list;    building the table from the tree.    
     
     
         5 . A method for designing a table of a database from a tree structure, comprising: 
 determining at least one field for the table;    computing the cardinality for the field;    sorting the at least field into an ascending list based on the computed cardinality of the field;    grouping the field into a sub-list, wherein the grouping is based on a grouping value calculated by taking a logarithmic value of the cardinality for the field;    building a sub-tree for the sub-list;    assembling the sub-list into a final tree; and    building the table from the final tree.    
     
     
         6 . A method for representing at least one value from a table of a database, comprising: 
 determining a set of values for each field of the table in the database, wherein the set of values does not include any duplicate values;    adding a NULL value as a first value in the set of values for each field; and    using a pointer for each field in a representation of a tuple in the table of the database, the pointer at least one of a) referencing the first value in the set of values for the field to indicate the NULL value, b) referencing the value in the set of values for the field, and c) encoding the value from the set of values for the field into the pointer.    
     
     
         7 . A method for representing at least one value from a table of a database, comprising: 
 determining whether a set of values for a field of the table in the database can be directly encoded by a pointer;    generating the set of values for the field of the table in the database, wherein the set of values does not include any duplicate values and wherein the set of values for the field can not be directly encoded by the pointer as decided in the determining step;    adding a NULL value as at least one of a) a first value in the set of values for the field wherein the set of values for the field can not be directly encoded by the pointer and b) a first pointer value in the set of directly encoded pointer values wherein the set of values for the field can be directly encoded by the pointer; and    using the pointer for each field in a representation of a tuple in the table of the database, the pointer at least one of a) referencing the first value in the set of values for the field to indicate the NULL value, b) referencing the value in the set of values for the field, c) encoding the value from the set of values for the field into the pointer, and d) encoding the first pointer value in the set of directly encoded pointer values to indicate the NULL value.    
     
     
         8 . A method for representing at least one data pattern in a table of a database, comprising: 
 determining a set of patterns for a tuple of the table of the database, wherein the set of values does not include any duplicate patterns;    adding a NULL pattern as a first pattern in the set of patterns for the tuple; and    using a pointer for each pattern in a representation of the tuple in the table of the database, the pointer at least one of a) referencing the first pattern in the set of patterns for the tuple to indicate the NULL pattern, b) referencing the pattern in the set of patterns for the tuple, and c) encoding a pattern identifier for the pattern in the set of patterns into the pointer.    
     
     
         9 . A method for evaluating an expression for a table of a database, comprising: 
 determining a common path to a common node for a first field and a second field of the table, wherein the expression uses at least the first field and the second field as an argument;    calculating and storing a value for the expression in a pattern at the common node where the pattern at the common node does not already contain the value for the expression; and    retrieving the value for the expression from the pattern at the common node.    
     
     
         10 . A method for including a derived field in a table of a database, comprising: 
 including an expression as a pattern for the derived field in the table;    evaluate the expression if a path to at least one of a node and a field in the table contains the expression;    return a value for the path, the value reflecting at least one of the evaluated expression and a stored valued indicated by the path.    
     
     
         11 . A method for sorting a table of a database according to a sort pattern and a sort order, comprising: 
 allocating space for a sorted table, the space allocated in memory or storage;    determining an offset value for each sort pattern in the table, the offset value determined as a function of the sort order and a number of instances for each sort pattern; and    copying each row of the table to the allocated space, the position of the row in the sorted table determined as a function of the sort pattern of the row and the offset value for the sort pattern of the row, wherein the offset value for the sort pattern of the row is incremented after copying the row.    
     
     
         12 . A method for sorting a table of a database according to a sort pattern and a sort order, comprising: 
 allocating space for a sorted pointer list, the space allocated in memory or storage and the sorted pointer list containing enough space for a pointer to each row of the table;    determining an offset value for each sort pattern in the table, the offset value determined as a function of the sort order and a number of instances for each sort pattern; and    creating the pointer to each row of the table in the allocated space, the position of the pointer in the sorted pointer list determined as a function of the sort pattern of the row and the offset value for the sort pattern of the row, wherein the offset value for the sort pattern of the row is incremented after creating the pointer.    
     
     
         13 . A method for sorting a subset of a table of a database according to a selection criteria, a sort pattern, and a sort order, comprising: 
 allocating space for a sorted table, the space allocated in memory or storage;    determining an offset value for each sort pattern in the table, the offset value determined as a function of the sort order and a number of instances for each sort pattern;    comparing each row of table with the selection criteria to determine if the row meets the selection criteria;    copying each row of the table that meets the selection criteria to the allocated space, the position of the row in the sorted table determined as a function of the sort pattern of the row and the offset value for the sort pattern of the row, wherein the offset value for the sort pattern of the row is incremented after copying the row; and    consolidating the sorted table, wherein unused allocated space is removed from the sorted table.    
     
     
         14 . A method for sorting a subset of a table of a database according to a selection criteria, a sort pattern, and a sort order, comprising: 
 allocating space for a sorted pointer list, the space allocated in memory or storage and the sorted pointer list containing enough space for a pointer to each row of the table;    determining an offset value for each sort pattern in the table, the offset value determined as a function of the sort order and a number of instances for each sort pattern;    comparing each row of table with the selection criteria to determine if the row meets the selection criteria;    creating the pointer in the allocated space for each row of the table that meets the selection criteria, the position of the pointer in the sorted pointer list determined as a function of the sort pattern of the row and the offset value for the sort pattern of the row, wherein the offset value for the sort pattern of the row is incremented after creating the pointer; and    consolidating the sorted pointer list, wherein unused allocated space is removed from the sorted pointer list.    
     
     
         15 . A method for sorting a table of a database according to an expression, comprising: 
 determining at least one unique pattern for a sort field of the table, wherein the sort field is used as part of the expression;    sorting the table into at least one bin as a function of the at least one unique pattern, wherein the at least one bin is a block of data having a same value of the sort field of the table;    determining a key for the at least one bin, wherein the key is a result of the expression using the same value of the sort field for the bin;    generating a sorted list of keys, wherein the sorted list of keys contains the key and the key corresponds to one bin; and    reordering the at least one bin as a function of the sorted list of keys.    
     
     
         16 . A method for sorting a table of a database according to an expression, comprising: 
 determining at least one unique pattern for a first sort field of the table, wherein the first sort field is used as part of the expression;    determining at least one unique pattern for a second sort field of the table, wherein the second sort field is used as part of the expression;    sorting the table into at least one bin, the table sorted in a reverse sort order first as a function of the at least one unique pattern for the second sort field and second as a function of the at least one unique pattern for the first sort field, wherein the at least one bin is a block of data having a first same value of the first sort field of the table and a second same value of the second sort field of the table;    determining a key for the at least one bin, wherein the key is a result of the expression using the first same value of the first sort field for the bin and the second same value of the second sort field for the bin;    generating a sorted list of keys, wherein the sorted list of keys contains the key and the key corresponds to one bin; and    reordering the at least one bin as a function of the sorted list of keys.    
     
     
         17 . A method for sorting a table of a database according to a first expression and a second expression, comprising: 
 determining at least one unique pattern for at least one first sort field of the table, wherein the at least one first sort field is used as part of the first expression;    determining at least one unique pattern for at least one second sort field of the table, wherein the at least one second sort field is used as part of the second expression;    sorting the table first as function of the second expression and second as a function of the first expression, the table first sorted as a function of the at least one unique pattern for the at least one second sort field of the second expression and second as function of the at least one unique pattern for the at least one first sort field of the first expression.    
     
     
         18 . A method for partitioning a table of a database as a function of at least one partition field, comprising: 
 sorting the table according to the at least one partition field; and    generating a root indirection set for each value of the at least one partition field, the root indirection set containing at least one pointer to a tuple in the table wherein the value of the at least one partition field for the root indirect set matches the value of the at least one partition field for the tuple.    
     
     
         19 . A method for joining a first table and a second table of a database as a function of at least one join field, comprising: 
 sorting the first table according to the at least one join field;    sorting the second table according to the at least one join field;    matching a tuple in the first table with a tuple in the second table, wherein a value for the at least one join field of the tuple in the first table is equal to a value for the at least one join field of the tuple in the second table; and    generating a joined table as a function of the matching tuple in the first table and the matching tuple in the second table.    
     
     
         20 . A method for storing a snapshot of data in a database, comprising: 
 creating a root indirection set for the snapshot of data;    maintaining a deleted pattern in the database, wherein the deleted pattern is not removed from a pattern set for a node in a table of the database when the pattern is deleted in the database; and    providing access to the snapshot of data using the created root indirection set, the created root indirection set accessing the deleted pattern.    
     
     
         21 . A method for performing a time series analysis on data in a database, comprising: 
 creating a root indirection set for each snapshot of data to be used in the time series analysis, wherein current data is treated as an already existing snapshot for the time series analysis;    designating a plurality of snapshots of data to be used in the time series analysis, wherein the root indirection sets of the snapshots of data are identified;    generating a query for the time series analysis, the query to be executed on all the designated snapshots of data; and    comparing query results as part of the of the time series analysis.