Automatic Elimination Of Functional Dependencies Between Columns

Abstract

In business systems, one or more methods can be used to reduce an amount of redundant data. In one implementation, a method to reduce redundancy within a data model in a database, in which the data model is represented by at least one table, includes determining a number of distinct values of partial keys in a table. Each partial key represents at least one row in the table. The method includes reordering one or more columns of the table by cardinality of partial keys, in which the cardinality of a partial key represents a number of distinct values of the partial key. The method further includes determining whether pairs of partial keys are functionally dependent and eliminating one or more columns having functional dependencies from the table.

1 . A method comprising:
 reducing redundancy within a data model in a database, wherein the data model is represented by a table comprising a plurality of rows, wherein each row includes a plurality of partial keys and a plurality of key figures representing first data records, the plurality of partial keys identifying locations of second data records, the reducing comprising:   determining a number of distinct values of partial keys in the table;   determining whether pairs of partial keys are functionally dependent by defining a function from each partial key to every other partial key of the table reordered based on a cardinality of the partial keys; and   eliminating, based on the defined function, one or more columns having functional dependencies from the table to reduce the redundancy within the data model, wherein the reducing, the determining the number, the determining whether, and the eliminating are implemented by at least one processor.   
     
     
         2 . The method in accordance with  claim 1 , further comprising:
 placing the one or more eliminated columns into a separate table so that the column with a highest cardinality is in the leftmost position, and the column with the lowest cardinality is in the rightmost position.   
     
     
         3 . The method in accordance with  claim 2 , wherein partial key K(i) comprises a partial key with an index i and a value Kri for a tuple t(r) in row with index r, and wherein the number of distinct values of K(i) comprises cardinality |K(i)|. 
     
     
         4 . The method in accordance with  claim 3 , wherein the tuple t comprises k key figures and d partial keys K( 1 ), . . . , K(d). 
     
     
         5 . The method in accordance with  claim 4 , wherein a table T comprises n tuples and d+k columns, wherein the n tuples comprise rows. 
     
     
         6 . The method in accordance with  claim 5 , wherein a function F(x)=y comprises a mapping between partial keys x and y in a same tuple. 
     
     
         7 . The method in accordance with  claim 6 , wherein a flag fd comprises Boolean values of true or false. 
     
     
         8 . The method in accordance with  claim 7 , wherein determining whether pairs of partial keys are functionally dependent further comprises:
 defining function F from each partial key to every other partial key to its right in a reordered table for each row in table T; and   determining a functional dependency exists when the function F(Kri)=Krj is the same function for each tuple t(r) in the table for values of index i from 1 to (d−1) and for values of j from (i+1) to d.   
     
     
         9 . The method in accordance with  claim 8 , wherein when a tuple t is in the table T and F(Kri) is not equal to Krj, a functional dependency does not exist between columns i and j. 
     
     
         10 . The method in accordance with  claim 9 , wherein determining whether pairs of partial keys are functionally dependent for each i from 1 to (d−1) and j from (i+1) to d comprises:
 setting the flag fd to true; 
 for each tuple t in T, determining whether F(Kri) is defined, wherein F(Kri) is set equal to Krj upon determining that F(Kri) is not defined; 
 looping through the tuples t in T; and 
 generating a report indicating that column i is functionally dependent on column j if flag fd is true after the looping through the tuples t in T. 
 
     
     
         11 . The method in accordance with  claim 10 , wherein determining whether F(Kri) is defined comprises:
 upon determining that F(Kri) is defined, determining whether F(Kri) is equal to Krj, wherein determining that F(Kri) is equal to Krj permits looping through the tuples t in T, and wherein determining that F(Kri) is not equal to Krj comprises:
 concluding that K(i) is not functionally dependent on K(j); 
 setting flag fd to false; and 
 breaking the looping through the tuples t in T. 
   
     
     
         12 - 19 . (canceled) 
     
     
         20 . An article comprising a machine-readable medium storing instructions operable to cause a machine to perform operations comprising:
 reducing redundancy within a data model in a database, wherein the data model is represented by a table comprising a plurality of rows, wherein each row includes a plurality of partial keys and a plurality of key figures representing first data records, the plurality of partial keys identifying locations of second data records, the reducing comprising:   determining a number of distinct values of partial keys in the table;   determining whether pairs of partial keys are functionally dependent by defining a function from each partial key to every other partial key of the table reordered based on a cardinality of the partial keys; and   eliminating, based on the defined function, one or more columns having functional dependencies from the table to reduce the redundancy within the data model.   
     
     
         21 . A system comprising:
 at least one processor; and   at least one memory including code which when executed by the at least one processor causes operations comprising:   reducing redundancy within a data model in a database, wherein the data model is represented by a table comprising a plurality of rows, wherein each row includes a plurality of partial keys and a plurality of key figures representing first data records, the plurality of partial keys identifying locations of second data records, the reducing comprising:   determining a number of distinct values of partial keys in the table;   determining whether pairs of partial keys are functionally dependent by defining a function from each partial key to every other partial key of the table reordered based on a cardinality of the partial keys; and   eliminating, based on the defined function, one or more columns having functional dependencies from the table to reduce the redundancy within the data model.   
     
     
         22 . The system in accordance with  claim 21 , further comprising:
 placing the one or more eliminated columns into a separate table so that the column with a highest cardinality is in the leftmost position, and the column with the lowest cardinality is in the rightmost position.