currentleafnodeofthetreeuntilaheuristicstop-splittingruleissatis edoneveryleafnode:splittingofanodestopswhenitcanprovideonlymarginalimprovementinhomogeneity.Thissituationusuallyariseswhenamaximalsplitonanodecannotseparateelementsofonetypefromelementsoftheothertypeinthisnode.Thisindicatesthatthisnodehasafairlyhomogeneousdistributionofbothtypesofelements.

Thestop-splittingrulesmentionedearlierarenecessary,becauseotherwiseatreecouldgrowuntilalltheelementsofeveryleafareofonetype.Thiscouldresultinalargenumberofsmallnodes.Italsomeansthattheremightbetoofewsampleelementsinthisnode,whichmakesthesoundnessestimateofthenodeunreliable.Ourstop-splittingruleis G·n≥threshold,wherenisthenumberofelementsinthenode[11].Ananalogousprocedureisusedforbuildingacompletenesstree.

Eachleafnodeofeverysoundnesstreecontributesoneviewtothesoundnessbasisandeachleafnodeofeverycompletenesstreecontributesoneviewtothecompletenessbasis.Together,thesesoundnessandcompletenessbasesformagoodnessbasis.Notethatthisprocessisperformedonlyonceoneveryrelation,andthegoodnessbasisneednotbechangedorupdatedlater.Theassumptionhereisthattheinformationisstatic.Whenaleafnodeisconvertedtoaview,inadditiontotherowsandcolumnsofthenode,theviewincludesthekeyattributeforthesetuples.

5

5.1EstimatingtheQualityofQueriesProjection-SelectionQueries

Assumenowaqueryissubmittedtothisdatabaseextension.Atthispoint,weconsideronlyselection-projectionqueriesonasinglerelation(andinwhichselectionsarebasedonranges).Inthissectionwediscusstheestimationofsoundnessofsuchqueries.Theconsiderationsforestimatingcompletenessarenearlyidentical.InthenextsectionwediscussqueriesthatinvolveCartesianproducts.

Becauseabasispartitionseachrelation,ananswertoaqueryintersectswithacertainnumberofbasisviews.Hence,eachofthesebasisviewscontainsacomponentoftheanswerasitssubview.Thekeyfeatureofbasisviewsistheirhomogeneitywithrespecttosoundness.Consequently,eachcomponentoftheanswerinheritsitssoundnessfromabasisview.AsshowninProposition1(see[11]forproof),thesoundnessofaviewwhichcomprisesdisjointcomponentsisaweightedsumofthesoundnessoftheindividualcomponents.Thisprovidesuswithaneasywaytodeterminethesoundnessoftheentireanswer.Asaspecialcase,whentheentireansweriscontainedinasinglebasisview,thesoundnessoftheanswerissimplythesoundnessofthecontainingview.

Proposition1Lett1andt2beleafnodesofasoundnesstreewithsoundnesss1ands2respectively,andletqbeananswertoaqueryQ.Supposealsothatq=(q∩t1)∪(q∩t2).