Abstract. A data cube is a popular organization for summary data. A cube is simply a multidimensional structure that contains in each cell an aggregate value, i.e., the result of applying an aggregate function to an underlying relation. In practical situat

LOGLINEAR-BASEDQUASICUBES267theanswertothissub-querydoesnotrequireretrievinganyofthevaluesintheretainedlistofcellsforthechunkorestimatinganyofthecellsvalues.

Thesub-querycoverstherespectivechunkonlypartially.Inthiscase,weneedtoestimateorretrieve(fromthelistofretainedcells)theindividualcellvaluesandaggregatethem.Inlargerqueries,itislikelythatmanysub-querieswillspancompletechunksandthere-fore,therunningtimewillbespedupconsiderably.

2.4.Incrementallyupdatingthemodels

Inthissubsectionweshowthatmaintainingourmodelsincrementallyisaneasytask.Thisfactmakesourtechniqueveryusableforcompressionofdatacubes.

Wemakearealisticassumption:althoughthecorecuboidexistsinthediskonlyinitscompressedform,theoriginal,uncompressedcubeisavailableontertiarystorage(tape),soanyofthecells’valuescanberetrievedatwill(albeit,payingthepriceofslowaccesstoit).Anynewdatathatcomestothewarehousecorrespondstooneofthefollowingthreecases:

1.Acellvalueinthebasecuboidischangedtoanewvalue.(Thismayoccurforinstance,inadatacubethatcontainssalesbyproduct,storeandlocation,butnottime;anewsalewillmakeacellvaluechange.)Inthiscase,afterthelocationandincrementofthecellareknown,wemustidentifythechunktowhichthecellbelongs.Thechunkmaybeofthefollowingtypes:

STAT-SPAR:inthiscase,thecellisaretainedone,andwemustmodifythecelladdingtheincrementalvalue.Thereisnoneedtoaccessthetertiarystorage,sincetherealvalueofthecellisavailableondisk.

STAT-MODL: rstdeterminewhetherthecellisanoutlier.Ifso,changetheoldretainedvalueforthenewone.Otherwise,determinewhetherthenewvalueiswithinthe xederrorlevelcomparedwiththevaluegeneratedbythemodel.Thenewvaluecanbecomputedasthesumoftheincrementplustheoldvalue(availablefromtertiarystorage).Ifthenewvaluefallswithinthemaximumestimationerror,justdiscardtheincrement,otherwise,insertthevalueinoutlierset.(Thenewvaluemustbestoredintertiarystorage,replacingtheoldvalue.)

2.Thecellwasanullcellinthebasecuboid.Inthiscase,wemust ndoutwhichchunkitbelongsto.Thestateofthatchunkwillbeoneofthefollowing:

STAT-NULL:changethechunkstatetoSTAT-SPAR,keepthecellassinglesetandalsomodifythechunk’sdescriptionstructure.(Noneedtoaccesstertiarystorage.) STAT-SPAR:modifythechunk’sdescription,determineifthechunkisdenseenoughafterthenewcellarrives,ifso,trytomodelthischunk.Otherwise,justretainthecell.(Accessthetertiarystorageonlyifthecellisnotretained,inordertostoreitontape.)