Set number 1
No redundant FDs.
Set number 2
FD 2 is redundant using FDs: 1
Set number 3
No redundant FDs.
Set number 4
No redundant FDs.
Set number 5
FD 3 is redundant using FDs: 1 2
Set number 6
FD 1 is redundant using FDs: 4 5
FD 2 is redundant using FDs: 6 4
FD 3 is redundant using FDs: 5 6
FD 4 is redundant using FDs: 1 2
FD 5 is redundant using FDs: 3 1
FD 6 is redundant using FDs: 2 3
Set number 7
FD 1 is redundant using FDs: 2
Set number 8
FD 1 is redundant using FDs: 2 3
little joey wrote:Lots of WAs, so I may be making a conceptual error...
Am I right that the line
If more than one sequence of FDs can be used to show another FD is redundant, any such sequence is acceptable, ...
means that we only have to print one sequence, and not all sequences separated by "--OR--", like in the sample output?
Can someone verify this I/O?
It's correct, only one sequence should be printed. The "--OR--" example in the output is a bit misleading. Your output is correct.
.. wrote:I not yet start coding, but wonder how to interpret:
Each FD in an acceptable proof sequence must, however, be necessary.
Does necessary mean that we must use non-redundant FS in the proof? If yes, then how should we handle the set number 6?
Necessary means that if one element is taken away from the proof sequence, it no longer makes the FD in question redundant. However, your other interpretation could be valid (as the example output does not contradict this), and I didn't think of that one. The problem statement does bring an example where all the FD's are redundant, which means that redundant FD's have to be used sometimes in a proof sequence.
Set number 1
FD 11 is redundant using FDs: 12
FD 19 is redundant using FDs: 1 33 12 24
FD 31 is redundant using FDs: 7 30 33 36 37
FD 38 is redundant using FDs: 22 30 12 17 24 41 10
To prove that FD 1 is redundant, you can either have the sequence "2 3" or the sequence "4 5 7"; they are equally valid, even though the second one is longer than the first. The sequence "4 5 6 7" also proves the redundancy of FD 1, but contains the 'unnecessary' FD 6, so it is not a valid answer.
Can anybody tell me if my answer to the above test with 42 functional dependencies is correct?
The output is:
------
Set number 1
FD 11 is redundant using FDs: 12
FD 19 is redundant using FDs: 34 30 17 16 5 15 14 12
FD 31 is redundant using FDs: 33 30 18 16 5 15 7 13 12
FD 38 is redundant using FDs: 30 22 17 4 14 6 7 13 12
------
I'd be grateful to those who got AC, if they could give me some tricky tests.