Patent Document ID: 8639667
Application ID: 12380858
Patent Flag: 1

Claim One:
1. A method for use by a computer for automatically generating a pattern tableau of a conditional functional dependency of a relation instance, the method comprising steps performed by the computer of: (a) adding an individual pattern to the tableau; if that pattern has; (i) the highest support from among a plurality of candidate tableau patterns; (ii) a confidence that is greater than or equal to a local confidence threshold ĉ, this step being carried out based on a determined cover, determined local support and a determined local confidence of each of the plurality of candidate patterns; and (b) repeating step a) until the global support of the tableau is at least equal to a global support threshold; wherein in the steps (a) and (b): (i) each of said patterns is a tuple having at least one antecedent attribute and at least one consequent attribute; (ii) a cover of a pattern is a row of the relation instance having a tuple that matches the antecedent of that pattern; (iii) the local support of a pattern is a fraction of tuples of the relation instance that are covers of that pattern; (iv) the local confidence of a pattern is a ratio of its keepers to its covers, the keepers of a pattern being the number of its covers determined after removing from the relation instance the fewest rows needed to eliminate all disagreements between the consequent of the pattern and the consequents of the tuples of the remaining row; (v) the global support of a tableau is the fraction of the tuples of the relation instance covered by at least one of the patterns of the tableau; and (vi) and the tuples of iii) and iv) are tuples that are not covers of patterns already chosen for the tableau; and wherein the conditional functional dependency is composed of an embedded functional dependency (FD) X→Y in combination with the pattern tableau, where X and Y are subsets of a relational schema for the relation instance, the relation instance comprising a plurality of tuples having attributes, and wherein, in accordance with the functional dependency (FD) X→Y, any two of the tuples that agree on the values of all the attributes in subset X must agree on the values of all the attributes in subset Y; wherein the pattern tableau defines a subset of the tuples of the relation instance for which the embedded functional dependency holds; wherein the plurality of candidate tableau patterns is initially a single pattern that matches every tuple of the relation instance; wherein the method further comprises the computer adding a child of a pattern to the plurality of candidate tableau patterns when all of the parents of that child have been determined to meet criterion (a)(i) but not criterion (a)(ii); wherein the child of a parent pattern is one in which in which exactly one match-all attribute in the parent pattern is replaced with an attribute constant that appears in the relation instance; and wherein a parent of a child pattern is a pattern in which exactly one attribute constant in the child pattern is replaced with a match-all attribute.