Exact and approximate aggregation in constraint qu

ExactandApproximateAggregationinConstraintQueryLanguagesMichaelBenediktBellLaboratories263ShumanBlvdNaperville,IL60566E-mail:[e-mail]atories600MountainAvenueMurrayHill,NJ07974E-mail:[e-mail]theproblemofhowtoextendconstraintquerylanguageswithaggregateoper-ators.Wedealwithstandardrelationalaggregation,andalsowithaggregatesspecictospatialdata,suchasvolume.Westudyseveralapproaches,includingtheadditionofanewclassofap-proximateaggregateoperatorswhichallowanerrortoleranceinthecomputation.WeshowhowtechniquesbasedonVC-dimensioncanbeusedtogivelanguageswithapproximationoperators,butalsoshowthattheselanguageshaveanumberofshortcomings.Wethengiveasetofresultsshowingthatitisimpossibletogetconstraint-basedlanguagesthatadmitdenableaggregationoperators,bothforexactoperatorsandforapproximateones.Theseresultsarequiterobust,inthattheyshowthatclosureunderaggregationisproblematicevenwhentheclassoffunctionspermittedinconstraintsisexpanded.Thismotivatesadierentapproachtotheaggregationproblem.WeintroducealanguageFO+Poly+Sum,whichpermitsstandarddiscreteaggregationoperatorstobeappliedtotheoutputsofrange-restrictedconstraintqueries.Weshowthatthislanguagehasanumberofattractiveclosureandexpressivityproperties,andthatitcancomputevolumesoflinear-constraintdatabases.1IntroductionNewapplicationsofdatabasetechnology,suchasGeographicalInformationSystems,havespurredaconsiderableamountofresearchintogeneralizationsofthestandardrelationalmodeltodealwiththemanipulationofgeometricorspatialdata.Onecommonapproachtomodelingspatialdatabaseistoconsiderinputdatabasesasgivenbyasetofwell-behavedrelationsineuclideanspace{forexample,byasetofsemi-linearorsemi-algebraicsets.Thereareanumberofproposedquerylanguagesthatextendclassicalrelationalalgebratothissetting,languagesthatallowtheuseofvariousgeometricoperationsinmanipulatingspatialdatabases.Oneofthemostwell-developedmodelsforspatialqueriesistheconstraintdatabasemodel[23].Inthismodel,spatialdatabasesarerepresentedassetsoflinearorpolynomialconstraints.Databasesarequeriedusingstandardrelationalcalculuswithlinear(resp.polynomial)inequalitiesasselectioncriteria,see[4,5,6,19,20,32,38].Theselanguages,denotedbyFO+LinandFO+Poly,havebecomethedominantonesintheconstraintdatabaseliterature.Theyhaveaveryimportantclosureproperty:theapplicationofaFO+Linquerytoalinearconstraintsetyieldsanewsetoflinearconstraints;similarlyFO+Polyqueriesonsetsdenablewithpolynomialconstraintsproducesetsthatcanstillbedenedwithpolynomialconstraints.1ConstraintQueryLanguages,then,giveanaturalanalogofrelationalcalculusinthegeometriccontext.Acrucialquestion,though,concernshowtoextendstandardaggregationconstructsfromtherelationalmodeltothegeometricsetting.Thisquestionhastwocomponents.First,wewouldlikeourlanguagestobeabletoapplystandardSQLoperatorssuchasTOTALandAVGtospatialqueries,whenevertheseoperatorsmakesense.Sincetheoutputofqueriesinconstraintquerylanguages(andinotherspatialquerylanguages)maybemerelynitelyrepresentable(thatis,representablebysomenitemeans,e.g.,anitesetofconstraints)andnotnite,theaggregationoperatorscannotbeallowedtobeappliedtoanyconstraintqueryoutput.Oneproblemthen,istodesignalanguagethatallowsthesafeapplicationofclassicalaggregates.Thesecondcomponentofthe‘aggregationquestion’concernsaggregationnotionsthatarespecictothespatialdatabases.Mostcommonly,givenadatabaseandtheoutputofaqueryoverit,onewishestoformnewqueriesaboutthevolumeofthisoutput.OnemayalsoextendstandardaggregatessuchasAVG,andaskfortheaveragevalueofapolynomialoveraspatialobject.SuchaggregatesarisebothfrompracticalconcernsofGIS,andalsoasthenaturalcontinuousanalogsofclassicalaggregationqueries.Thus,wewouldliketoextendconstraintquerylanguagestoincorporatetheabilitytocalculatevolumesandotheraggregatesarisinginthespatialsetting.Inattemptingtoaddaggregationtoconstraintquerylanguages,oneimmediatelyencounterssomedauntingobstacles.Whilestandardconstraintdatabasesareclosedunderrst-orderoperationssuchasjoinandprojection,theyareclearlynotclosedundertakingofvolumes.Thisfactiswell-knownintheliterature[23,27,12],andstemsfromthefactthatneitherthesemi-linearnorsemi-algebraicsetsareclosedunderintegrals.Totakeanexamplefromthesemi-algebraicsetting,aqueryaskingforthevolumeofinitialslicesoftheepigraphof1=xoutputsthegraphofthelnfunction,whileiteratingvolumequeriesinthisfashionwouldgiveasoutputtranscendentalfunctionsthatarenotevenexpressibleusingeldoperations,logarithmsandexponents.Thus,onecannothopetoaddageneralvolumeoperatortoexistingrst-orderconstraintquerylanguagessuchasFO+Polyandgetaclosedlanguagewhilestillremainingwithinthedomainofpolynomialconstraintdatabases.Thereareseveralapproachestothevolumeproblemmentionedabove.First,onecouldweakentherequirementthatvolumesbecomputedexactlyandinsteadaimonlytocomputeapproximatevolumes.Thusaquerymighthaveatoleranceassociatedwitheachinstanceofavolumeoperator,withoutputrequiredonlytobecorrectwithinthegiventolerance.Thereareanumberofpracticalandtheoreticalmotivationsfo