Description

When designing tables in a relational database, the term "functional dependency" (FD) is used to describe relationships between attributes. A functional dependency describes the relationship between the values of attributes in one set and those in another set. The notation $X \to Y$ is used to mean that once the attributes in set $X$ are assigned values, the attributes in set $Y$ are determined. For example, in a data table with attributes "Social Security Number" ($S$), "Name" ($N$), "Address" ($A$), and "Phone" ($P$), where each person has a unique value of $S$, the attributes $N$, $A$, and $P$ are determined by $S$. This is written as $S \to \{N, A, P\}$.

Write a program to find all redundant dependencies in a set of dependencies. A dependency is redundant if it can be derived from the other dependencies in the set. For example, if the set includes $A \to B$, $B \to C$, and $A \to C$, then the third dependency is redundant because $C$ can be derived from the first two dependencies ($A$ determines $B$, and $B$ determines $C$). Among $A \to B$, $B \to C$, $C \to A$, $A \to C$, $C \to B$, and $B \to A$, all dependencies are redundant.

You are required to write a program to identify the redundant dependencies from the given set.

Input Format

The first line contains an integer $n$ not exceeding $100$, which is the number of functional dependencies in the file.

From the second line onward, each line contains one functional dependency, and all dependencies are distinct. Each line consists of two non-empty attribute lists separated by the characters $\verb!-!$ and $\verb!>!$. Each list consists solely of uppercase letters. There are no spaces or tabs in any FD line. No trivial dependencies (such as $A \to A$) will appear. Although the FDs are not explicitly numbered in the file, their order corresponds to indices $1$ through $n$.

Output Format

Output each redundant dependency on its own line, along with a sequence of other dependencies that shows it is redundant. The format is $\texttt{FD}\ x\ \texttt{is redundant using FDs:}\ p_1\ p_2 \cdots p_k$ where $x$ is the index of the redundant dependency, and $p_1, p_2, \cdots, p_k$ is a sequence of dependency indices that proves $x$ is redundant.

If multiple sequences of functional dependencies can be used to show a dependency is redundant, output the shortest proof sequence.

If no redundant dependencies are present among the given FDs, output No redundant FDs.

3
A->BD
BD->C
A->C

FD 3 is redundant using FDs: 1 2

6
P->RST
VRT->SQP
PS->T
Q->TR
QS->P
SR->V

FD 3 is redundant using FDs: 1
FD 5 is redundant using FDs: 4 6 2

Hint

Explanation for Sample 1

Dependency $3$ is redundant because $A \to C$ can be derived from the first two dependencies $A \to \{B, D\}$ and $\{B, D\} \to C$.

Translated by ChatGPT 5