3) Department of Redundancy Department

When designing tables for a relational database, a functional dependency (FD) is used to express the relationship between the different fields. A functional dependency is concerned with the relationship of values of one set of fields to those of another set of fields. The notation X->Y is used to denote that when supplied values to the field(s) in set X, the assigned value for each field in set Y can be determined. For example, if a database table is to contain fields for the social security number (S), name (N), address (A), and phone (P) and each person has been assigned a unique value for S, the S field functionally determines the N, A and P fields. This is written as S->NAP.
Develop a program that will identify each redundant FD in each input group of FDs. An FD is redundant if it can be derived using other FDs in the group. For example, if the group contains the FDs A->B, B->C, and A->C, then the third FD is redundant since the field set C can be derived using the first two. (The A fields determine values for the B fields, which in turn determine values for the fields in C.) In the group A->B, B->C, C->A, A->C, C->B, and B->A, all the FDs are redundant.

Input
The input file contains an arbitrary number of groups of FDs. Each group is preceded by a line containing an integer no larger than 100 specifying the number of FDs in that group. A group with zero FDs indicates the end of the input. Each FD in the group appears on a separate line containing two non-empty lists of field names separated by the characters - and >. The lists of field names contain only uppercase alphabetic characters. Functional dependency lines contain no blanks or tabs. There are no trivially redundant FDs (for example, A->A). For identification purposes, groups are numbered sequentially, starting with 1; the FDs are also numbered sequentially, starting with 1 in each group.

Output
For each group, in order, your program must identify the group, each redundant FD in the group, and a sequence of the other FDs in the group which were used to determine the indicated FD is redundant. If more than one sequence of FDs can be used to show another FD is redundant, any such sequence is acceptable, even if it is not the shortest proof sequence. Each FD in an acceptable proof sequence must, however, be necessary. If a group of FDs contains no redundancy, display No redundant FDs.

Dle zadání je vstupem programu soubor (přiložený file.txt). Program přečte vstup (pokud není v zadaném formátu, výstup bude pravděpodobně chybný), uloží si vstupní písmena (nalevo od ->) do pole in odvozená písmena do pole der. Písmena jsou převedena na čísla 1-26, aby odpovídali číslování v matici odvod. Řádky obou polí jsou ukončeny 0.
Vlastní algoritmus poté prochází přes všechny řádky funkčních závislostí a řeší, zda je aktuální řádek A odvoditelný z ostatních. To se zjišťuje následovně:
K testu se využívá matice, kde každý řádek odpovídá písmenu a ve sloupcích jsou uloženy pořadová čísla funkčních závislostí která jsou potřeba pro odvození daného písmene. Nejprve se pro všechna vstupní písmena aktuálního řádku nastaví, že je lze odvodit právě z aktuálního řádku. Poté procházíme všechny řádky funkčních závislostí J (pokud to není aktuální řádek A) a zjišťujeme, zda lze ze všechna jeho vstupní písmena odvodit z nějakého řádku. Když ne, pokračujme tímto testem pro další řádek (J++).
Pokud lze odvodit ze všech písmen právě procházeného řádku J nějakou funkční závislost, nastaví se, že z odvozených písmen lze odvodit ty samé řádky funkčních závislostí jako ze vstupních a navíc právě procházený. Procházení pak pokračuje znovu od začátku (J=1).
Test končí, když jsme prošli všechny řádky a v žádném jsme nenašli další odvození (J=nfd). Poté si zjistíme, ze kterých řádků jsou odvoditelné odvozená písmena aktuálního řádku A a vypíšeme je.
Pokračujeme dalším řádkem (A++) a zjišťujeme, zda ho lze odvodit z jiných řádků.
Další popis viz komentáře ve zdrojovém textu.

V hlavní smyčce procházíme přes všechny řádky (n). Vnitřní smyčka proběhne taktéž n-krát, protože opakovaných průchodů přes ni může být maximálně c, což je počet použitých písmen ( ~ konstanta), a akce v ní prováděné taktéž nezávisí na n, ale na c. Časová složitost je tedy O(n²).

3
A->BD	Set number 1
BD->C	FD 3 is redundant using FDs: 1 2
A->C
6
P->RST
VRT->SQP	Set number 2
PS->T	FD 3 is redundant using FDs: 1
Q->TR	FD 5 is redundant using FDs: 4 6 2
QS->P
SR->V
5
A->B
A->C	Set number 3
B->D	FD 5 is redundant using FDs: 1 3
C->D
A->D
3
A->B	Set number 4
B->C	No redundant FDs
A->D
6	Set number 5
A->B	FD 1 is redundant using FDs: 2 6
A->C	FD 2 is redundant using FDs: 1 4
B->A	FD 3 is redundant using FDs: 4 5
B->C	FD 4 is redundant using FDs: 3 2
C->A	FD 5 is redundant using FDs: 6 3
C->B	FD 6 is redundant using FDs: 5 1
0