EFFICIENT DISCOVERY OF KEYS IN A DATABASE

• US 20080046474A1
• Filed: 08/17/2006
• Published: 02/21/2008
• Est. Priority Date: 08/17/2006
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Sismanis, John
• Granted Patent: US 8,838,648 B2
• Time in Patent Office: Days
• US Class Current: 707/200
• CPC Class Codes: G06F 16/217 Database tuning G06F16/2282 takes precedence; database performance monitoring G06F11/3409

Abstract

A method and system for discovering keys in a database. A minimal set of non-keys of the database are found. The database includes at least two entities and at least two attributes. The minimal set of non-keys includes at least two non-keys. Each entity independently includes a value of each attribute. A set of keys of the database is generated from the minimal set of non-keys. Each key of the generated set of keys independently is a unitary key consisting of one attribute or a composite key consisting of at least two attributes.

Claims

1. A method for discovering keys in a database, said method comprising:

finding a minimal set of non-keys of the database, said database comprising a plurality of entities and a plurality of attributes, said minimal set of non-keys comprising a plurality of non-keys, each entity independently comprising a value of each attribute; and

generating a set of keys of the database from the minimal set of non-keys, each key of the generated set of keys independently being a unitary key consisting of one attribute of the plurality of attributes or a composite key consisting of at least two attributes of the plurality of attributes.

2. The method of claim 1, wherein said generating the set of keys comprises:

forming a complement set of key candidates from each non-key in the minimal set of non-keys; and

generating a fall set of keys from the intersections of the complement sets of key candidates.

3. The method of claim 2, wherein said generating the set of keys further comprises:

generating a minimal set of keys by removing from the full set of keys all keys that cover other keys in the full set of keys.

4. The method of claim 1, wherein at least one key of the generated set of keys is a composite key.

5. The method of claim 1, wherein the method further comprises:

generating a prefix tree comprising hierarchical levels and nodes distributed at said levels and linked together hierarchically by paths within the tree, a root node of said nodes being at the highest level of said levels, said levels corresponding to said attributes on a one-to-one basis, each node comprising one or more cells, each cell comprising the value of one of said attributes, all child nodes of any one node of said nodes having a common prefix of the path through the tree from the root node to the any one node,

wherein said finding the minimal set of non-keys comprises traversing selected segments of selected slices of the prefix tree, and wherein said traversing comprises finding non-keys of the database via analysis of the cells of the leaf nodes visited during said traversing.

6. The method of claim 5, wherein the selected slices consist of all slices of the prefix tree.

7. The method of claim 5, wherein the selected slices do not include any slice subsumed by a selected slice whose selected segments have been previously traversed.

8. The method of claim 5, wherein the selected slices do not include any slice corresponding to one and only one entity.

9. The method of claim 5, wherein the selected slices do not include any segment covered by a segment previously found to correspond to a non-key.

10. The method of claim 5, wherein said finding non-keys via said analysis of the cells of the leaf nodes visited during said traversing comprises determining that any visited leaf node comprises a non-key if said any visited leaf node comprises more than one cell or consists of one cell having a count of 1, and wherein said count is the number of identical paths in the tree from the root node to the visited leaf node.

11. The method of claim 5, wherein said traversing comprises recursively traversing the segments of the selected slices of the prefix tree.

12. The method of claim 5, wherein said traversing each selected slice comprises:

recursively traversing all children of a unique node of the prefix tree that identifies each selected slice; and

recursively merging the child nodes descending from the unique node that identifies each selected slice.

13. The method of claim 12, wherein said recursively merging comprises performing a recursive merge of input nodes descending from the unique node that identifies each slice of the selected slices, and wherein said performing said recursive merge comprising generating a new node that includes a unique cell for each distinct attribute value of the input nodes being merged.

14. The method of claim 13, wherein the input nodes comprise multiple nodes having a same attribute value, wherein the multiple nodes are merged into one cell of the new node, and wherein the child cells of the multiple nodes having a same attribute value are merged into a child cell of this one cell of the new node.

15. The method of claim 5, wherein said traversing comprises selectively storing the found non-keys in a non-key container, and wherein said selectively storing does not store in the non-key container any newly found non-key that is covered by a non-key currently in the non-key container.

16. The method of claim 5, wherein said traversing comprises selectively storing the found non-keys in a non-key container, and wherein said selectively storing comprises replacing an existing non-key currently in the non-key container by a newly found non-key that covers the existing non-key.

17. A computer program product, comprising a computer usable medium having a computer readable program code embodied therein, said computer readable program code containing instructions that when executed by a processor of a computer system implement a method for discovering keys in a database, said method comprising:

finding a minimal set of non-keys of the database, said database comprising a plurality of entities and a plurality of attributes, said minimal set of non-keys comprising a plurality of non-keys, each entity independently comprising a value of each attribute; and

generating a set of keys of the database from the minimal set of non-keys, each key of the generated set of keys independently being a unitary key consisting of one attribute of the plurality of attributes or a composite key consisting of at least two attributes of the plurality of attributes.

18. The computer program product of claim 17, wherein the method further comprises:

generating a prefix tree comprising hierarchical levels and nodes distributed at said levels and linked together hierarchically by paths within the tree, a root node of said nodes being at the highest level of said levels, said levels corresponding to said attributes on a one-to-one basis, each node comprising one or more cells, each cell comprising the value of one of said attributes, all child nodes of any one node of said nodes having a common prefix of the path through the tree from the root node to the any one node,

wherein said finding the minimal set of non-keys comprises traversing selected segments of selected slices of the prefix tree, and wherein said traversing comprises finding non-keys of the database via analysis of the cells of the leaf nodes visited during said traversing.

19. A computer system comprising a processor and a computer readable memory unit coupled to the processor, said memory unit containing instructions that when executed by the processor implement a method for discovering keys in a database, said method comprising:

finding a minimal set of non-keys of the database, said database comprising a plurality of entities and a plurality of attributes, said minimal set of non-keys comprising a plurality of non-keys, each entity independently comprising a value of each attribute; and

generating a set of keys of the database from the minimal set of non-keys, each key of the generated set of keys independently being a unitary key consisting of one attribute of the plurality of attributes or a composite key consisting of at least two attributes of the plurality of attributes.

20. The computer system of claim 19, wherein the method further comprises:

generating a prefix tree comprising hierarchical levels and nodes distributed at said levels and linked together hierarchically by paths within the tree, a root node of said nodes being at the highest level of said levels, said levels corresponding to said attributes on a one-to-one basis, each node comprising one or more cells, each cell comprising the value of one of said attributes, all child nodes of any one node of said nodes having a common prefix of the path through the tree from the root node to the any one node,

wherein said finding the minimal set of non-keys comprises traversing selected segments of selected slices of the prefix tree, and wherein said traversing comprises finding non-keys of the database via analysis of the cells of the leaf nodes visited during said traversing.