Vi utvecklar en ny metod, baserad på det statistiska begreppet Vapnik-Chervonkis dimension, för att utvärdera selektiviteten (utgångskardinaliteten) av SQL-frågor - ett avgörande steg för att optimera genomförandet av storskalig databas och data mining verksamhet. Det stora teoretiska bidraget från detta arbete, som är av oberoende intresse, är uttryckligen bundet till VC-dimensionen av ett område som definieras av alla möjliga resultat av en samling (klass) av frågor. Vi bevisar att VC-dimensionen är en funktion av det maximala antalet booleska operationer i valet predikat och det maximala antalet utvalda och gå med i en enskild fråga i samlingen, men det är varken en funktion av antalet frågor i samlingen eller av storleken (antal tuples) i databasen. Vi utnyttjar detta resultat och utveckla en metod som, med tanke på en klass av frågor, bygger ett koncis slumpmässigt urval av en databas, så att med stor sannolikhet utförandet av någon fråga i klassen på provet ger en korrekt uppskattning för selektiviteten av frågan på den ursprungliga stora databasen. Sannolikheten för fel håller samtidigt för selektivitetsskattningar av alla frågor i samlingen, vilket samma urval kan användas för att utvärdera selektiviteten av flera frågor, och provet behöver uppdateras endast efter större ändringar i databasen. Provrepresentationen som beräknas med vår metod är vanligtvis tillräckligt liten för att lagras i huvudminnet. Vi presenterar omfattande experimentella resultat, validerar vår teoretiska analys och visar fördelarna med vår teknik jämfört med komplexa selektivitetsberäkningstekniker som används i PostgreSQL och Microsoft SQL Server.
REF beräknade en övre gräns för VC-dimensionen av klasser av SQL-frågor och använde den för att utveckla en provtagningsbaserad algoritm för att uppskatta storleken på utdata (selektivitet) av frågor körs på en datauppsättning.
The VC-Dimension of Queries and Selectivity Estimation Through Sampling
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}