Finding an Optimal Cover for a Kind of Set of Functional Dependencies in Polynomial Time

Xiaoning Peng; Zhijun Xiao

A smaller cover makes numerous algorithms (e.g., the classic synthesizing algorithm) need less storage space and less run time. Maier proves that the problem of finding an optimal cover (possible fewest attributes) is NP-complete. For a single-ended set of functional dependencies (the left side of every functional dependency has a single attribute), it is shown here that the optimal cover of a single-ended set of functional dependencies can be found in polynomial time, using the notion of mini cover. A simplified graphical representation (FD-graph) for a set of functional dependencies is introduced. It is provable that the transitive reduction of the FD-graph of a single-ended set of functional dependencies can be transformed into corresponding mini cover and further optimal cover.

Select Volume / Issues:

• Volume 5,Issue 4, July 2014

Year:

2014

Type of Publication:

Article

Keywords:

Functional Dependency; Mini Cover; Optimal Cover; Relational Database; Transitive Reduction

Journal:

IJECCE

Volume:

5

Number:

4

Pages:

990-992

Month:

July