Varje databassystem innehåller en frågeoptimering som utför frågeomskrivning. Tyvärr är utvecklingen av frågeoptimerare fortfarande en mycket utmanande uppgift. En del av utmaningarna kommer från de invecklade och rika dragen i frågespråk, vilket gör resonemang om skriva om regler svårt. I detta dokument föreslår vi en maskinkontrollerbar denotationell semantik för SQL, det de facto språket för interaktion med relationsdatabaser, för rigorös validering av omskrivningsregler. Till skillnad från tidigare föreslagna semantik som antingen inte är mekaniserade eller bara täcker en liten mängd SQL språkfunktioner, täcker våra semantik alla viktiga funktioner i SQL, inklusive väskor, korrelerade subqueries, aggregering, och index. Vår mekaniserade semantik, som kallas HoTT SQL, är baserad på K-relation och homotopy-teori, där vi betecknar relationer som matematiska funktioner från tuples till univalenta typer. Vi har implementerat HoTT SQL i Coq, som bara tar mindre än 300 rader kod, och har visat ett brett spektrum av SQL omskrivningsregler, inklusive de från databasforskning litteratur (t.ex., magiska uppsättningen omskrivningar) och verkliga frågeoptimerare (t.ex., subquery eliminering), där flera av dem har aldrig tidigare visat sig vara korrekt. Dessutom, medan frågan likvärdighet är i allmänhet obeslutbar, har vi genomfört ett automatiserat beslutsförfarande med HoTT SQL för konjunktiva frågor: en välstuderad decidable fragment av SQL som omfattar många verkliga frågor.
Specifikt, Chu et al. definiera en ny semantik för SQL baserad på K-relation och homotopy-teori och utveckla ett Coq-bibliotek för att interaktivt bevisa likvärdighet mellan SQL-frågor REF ].
HoTTSQL: proving query rewrites with univalent SQL semantics
{'venue': 'PLDI 2017', 'journal': None, 'mag_field_of_study': ['Computer Science']}