Estimating the quality of data in relational databases(10)

Thesoundnessofqis

s(q)=s1·|q∩t1||q∩t2|+s2·|q||q|

Thispropositioniseasilygeneralizedfornleafnodes,andtheanalogouspropositionistrueforcompleteness.Inpractice,weonlyhaveestimatesofs1ands2.Hence,theformulabecomes:|q∩t2||q∩t1|+s ·s (q)=s ·21|q||q|

Thevarianceoftheestimates (q)canbealsocomputed[11].

5.2EstimatingtheGoodnessofCartesianProducts

Toallowmoregeneralqueries,weconsidernowqueriesthatincludeCartesianproducts.Thefollowingproposition(see[11]forproof)describeshowtocomputethesoundnessandcompletenessoftheCartesianproductgiventhesoundnessandcompletenessofitsoperands.Proposition2Letr1andr2berelationswithsoundnessandcompletenesss1,c1ands2,c2respectively.Thesoundnessandcompletenessofther1×r2are

s(r1×r2)=k·s1+p·s2k·c1+p·c2,c(r1×r2)=k+pk+p

respectively,wherekandparethenumberofnon-keyattributesintherelationsr1andr2respectively.

Inpractice,wehaveonlyestimatesofthesoundnessandcompleteness,andtheformulasfromthepropositionbecome:

s (r1×r2)=k·c 1+p·c 2k·s 1+p·s 2,c (r1×r2)=k+pk+p

wheres 1,s 2,c 1,c 2areestimatesforsoundnessandcompletenessofthecorrespondingrela-tions.Forderivationofthevarianceoftheestimatessee[11].

5.3EstimatingtheGoodnessofGeneralQueries

Sofarwehaveshownhowtoestimatethesoundnessandcompletenessofselection-projectionqueriesonasinglerelation,andofCartesianproductsoftworelations.TocomputesoundnessandcompletenessofarbitraryCartesianproduct-selection-projectionqueriesitisnecessarytoshowhowtocomputegoodnessestimatesoversequencesofrelationalalgebraoperations.Theestimationofeachoperationinasequencerequiressoundnessandcompletenessbaseswitheachviewhavingitsassociatedsoundnessorcompletenessestimate.In[11]we