Verification of dependency constraints algorithm 1 (MapReduce)

Inter-columns corrections algorithm 2

Map1(key,value)

// key : data source name

// value : Source contents //set of tuples

Begin

For all tuple in value do

EmitIntermediate("X_i ;Y_ij ", "1")// count occurences of X_i ;Y_ij

End For

End Map1

Reduce1(key,values)

// key : X_i ;Y_ij

//value : a list of counts

int α_i = 0

file f

For all X_i ;Y_ij in values do

α_i += ParseInt(X_i ;Y_ij )

End for

Emit(α_i)

Write(f, α_i)

End Reduce1

Map2(key,value)

// key : f

// value : f contents

For all word X_i in value do

EmitIntermediate(X_i, "1") // count occurences of X_ij

End For

End Map2

Reduce2(key, values )

//key : X_i

//values : a list of counts

int ß_i=0;

Boolean validDF=0

For all v in values do

ß_i += ParseInt(X_i) // count occurences of X_i

End for

Emit(ß_i)

If ß_i =1 then

validDF=1

End if

End Reduce2

Begin inter-columns corrections

Input: DD Data Dictionary S data source, X, Y subsets of

columns from S,

SubCat Dominant subcategory of S

Output: S' the data source with automatic corrections

E2 ← CreateV alidDFs(DDV S;X; Y; SubCat)

S0 ← CorrectionsDFs(S;E2)

End inter-columns corrections

Function CreateValidDFs

Input: DDVS,X,Y,SubCat

Output: E2

// Get from DDVS the concerned categories X and Y

E1= {SELECT *ALL FROM DDVS

WHERE DDVS.CATEGORY = X UNION

SELECT *ALL FROM DDVS

WHERE DDVS.CATEGORY = Y}

// Get from DDVS all correct values (x_i,y_i)

E2= {SELECT A.Subcat, B.Subcat FROM E1 A, E1 B

WHERE A.PRIMARYKEY=B.FOREIGNKEY}

End Function CreateValidDFs

Function CorrectionsDFs

Input: E2, S

Output: S'

For l_j from S (j=1;n) do // l_j tuple from S, n (number of tuples)

While (S_x[j]6=DDVS_x[l]) AND (l ≤ nl) do

// nl number of tuples of DDVS

If S_X[j]= DDV S_X[l] then

S_y[j]=DDV S_y[l]

Else

l++

End If

End While

End For

End Function CorrectionsDFs