An optimal reformulation algorithm
The reformulation algorithm described in [1] can be downloaded as a java .jar file : solveroptref.jar
A program to compute dependencies from a table can be downloaded : Tane
The command line takes four arguments into account :
- file1: is the file containing the table with a tuple per line and each value separated by ','
- file2: is the file containing the dependencies, one per line in the Tane format: 1 3 5 -> 3 (no attribut 0, it starts at 1)
- timelimit (default:10s) : the timelimit in seconds to compute the reformulation
- type (default:1) : 1,2,3 depending on which objective function is considered, 1 to minimize arity, 2 to minimize the memory size, 3 to minimize the size combined with DFA compression
Some files can be dowloaded on the Data Sets page, included renaultR104tab.txt and renaultR104fds.txt used in the following example:
java -jar optrefsolver.jar renaultR104tab.txt renaultR104fds.txt 10 1
The output includes informations on the table itself as well as information on the reformulation. It also displays the dependencies used to obtain the optimal reformulation as well as the resulting set of subscopes giving the reformulation itself :
name & nbtuple & arity & memS & nbDep & maxArity & gain & memsize & time(ms) & greedy & timegreedy
renaultR104tab.txt & 164 & 9 & 1476 & 11 & 4* & 2.25 & 656 & 0.05 & 5 & 0.03 & \\
best score 4 - dfa size : 111
canonicFD 1 7 -> 2
canonicFD 1 -> 4
canonicFD 3 -> 5
canonicFD 1 7 -> 6
canonicFD 3 -> 7
0 6 1
0 6 5
0 3
2 4
2 6
0 2 7 8 [nt:164][s:656][dfas:37]
NBnode: 21
References
[1] Reformulating Positive Table Constraints using Functional Dependencies
Hadrien Cambazard and Barry O'Sullivan, CP 2008, September 2008.