proportionof1sinthenode.4

Thesearchforhomogeneousnodesinvolvesrepeatedsplittingofnodes.TheGiniindexguaranteesthatanysplitimproves(ormaintains)thehomogeneityofdescendantnodes[2].Formally,letvbearelationmapnodewhichissplitintotwosubnodesv1andv2.ThenG(v)≥α1G(v1)+α2G(v2),whereαiis|vi|/|v|.Inotherwords,thereductionofasplit,de nedas G=G(v) α1G(v1) α2G(v2),isnon-negative.

Obviously,thebestsplitisasplitthatmaximizes G.Wecallsuchasplitamaximalsplit.Ifthenumberofpossiblesplitsis nite,therenecessarilyexistssuchasplit.Themethodofgeneratingsoundnessandcompletenessbasesisfoundedonthesearchforasplitthatmaximizesthegaininhomogeneity.Thismethodisdiscussednext.

4.3FindingaGoodnessBasis

Wedescribeaprocedureofbuildingasoundnessbasis.Theprocedureofbuildingacom-pletenessbasisissimilar.

Itisimportanttonotethattheprocedurestobediscussedinthissectionareperformedonsamplesoftherelations.Therefore,inthediscussionthatfollows,thetermsrelationandrelationmapusuallyrefertosamplesoftherelationsandmapsofthesesamples.Thus,althoughthebestsplitsarefoundusingonlysamples,theresultingviewsarelaterusedasagoodnessbasisfortheentirerelation.Careshouldbetakentoensurethatwedrawsampleswhosesizesaresu cientforrepresentingdistributionpatternsoftheoriginalrelation.

Asoundnessbasisisapartitionofthestoredrelations,inwhicheachrelationispar-titionedintoviewsthatarehomogeneouswithrespecttosoundness.Sincetheprocedureofpartitioningisrepeatedforeachrelation,itissu cienttoconsiderthisprocedureforasinglerelation.Weassumethatinformationonthecorrectnessofarelationinstancehasalreadybeenconvertedtoacorrespondingrelationmap.

Findingahomogeneouspartitionofarelationcanbeviewedasatree-buildingprocedure,wheretherootnodeofthetreeistheentirerelation,itsleafnodesarehomogeneousviewsofthisrelation,anditsintermediatenodesareviewsproducedbythesearchesformaximalsplits.Wecallthistreestructureasoundnesstree.Westartbylabelingtheentirerelationmapastherootofthetree.Wethenconsiderallthepossiblesplits,eitherhorizontalorvertical(butnotboth),andselectthesplitthatgivesmaximumgaininhomogeneity.Obviously,thebrute-forcetechniquedescribedhereisextremelyexpensive.Inpracticeweapplyseveral,substantiativeimprovements[11].

Whenthemaximalsplitisfound,webreaktherootnodeintothetwosubnodesthatachievedthemaximalsplit.Next,wesearchforamaximalsplitineachofthetwosubnodesoftherootanddividethemintwodescendentnodeseach.Theprocedureisrepeatedoneach

Ingeneral,theGiniindexisde nedformapswhoseelementsareofkdi erenttypes;theindexusedhereismuchsimpler,becauseourmapsarebinary.4