Frågeoptimering är en integrerad del av relationella databashanteringssystem. En viktig uppgift i frågeoptimering är selektivitetsuppskattning, dvs. med tanke på en fråga P, måste vi uppskatta andelen poster i databasen som uppfyller P. Många kommersiella databassystem upprätthåller histogram för att approximera frekvensfördelningen av värden i attributen för relationer. Flera viktiga komponenter i ett databashanteringssystem (DBMS) kräver en noggrann uppskattning av selektiviteten hos en viss fråga. Till exempel, frågeoptimerare använder det för att utvärdera kostnaderna för olika frågeutförande planer och välja den föredragna. I detta dokument presenterar vi en teknik baserad på en flerupplösningsvågsdekomposition för att bygga histogram på de underliggande datadistributionerna, med applikationer till databaser, statistik och simulering. Histogram som bygger på den kumulativa datadistributionen ger mycket goda approximationer med begränsad rymdanvändning. Vi ger snabba algoritmer för att konstruera histogram och använda dem på ett on-line-sätt för selektivitetsbedömning. Våra histogram ger också snabba ungefärliga svar på OLAP frågor när de exakta svaren inte krävs. Vår metod fångar den gemensamma fördelningen av flera attribut effektivt, även när attributen är korrelerade. Experiment bekräftar att våra histogram erbjuder betydande förbättringar i noggrannhet över slumpmässig provtagning och andra tidigare metoder. Den uppsättning predikat som vi kommer att överväga i detta dokument är uppsättningen av urvalsförfrågningar, i synnerhet intervallpredikat av formen a < X < b, där X är ett icke-negativt attribut för domänen för en relation R och a och b är konstanter. Mängden lika grundämnen är den delmängd av intervallet som har a = b. Den uppsättning av ensidiga intervall predikat är det speciella fallet av intervall predikat där a = -ok eller b = cm. (Vi tar se = v1 och sn = 1.) Frekvensen fi av vi är antalet tuples där X har värde vi. Den kumulativa frekvensen ci av vi är antalet tuples t E R med t.X 5 vi, dvs. ci = '&r fj. Datadistributionen av X är uppsättningen par 7 = {(VI, fr ),
Matias m.fl. I REF föreslogs först användningen av Haar-wavelet koefficienter som synops för att korrekt uppskatta valmöjligheten för områdesförfrågningar.
Wavelet-based histograms for selectivity estimation
{'venue': "SIGMOD '98", 'journal': None, 'mag_field_of_study': ['Computer Science']}