Naslov Izražajna snaga jezika SQL
Naslov (engleski) The expressive power of the SQL language
Autor Antonela Bogdanić
Mentor Marko Horvat (mentor)
Član povjerenstva Marko Horvat (predsjednik povjerenstva)
Član povjerenstva Tina Bosner (član povjerenstva)
Član povjerenstva Matej Mihelčić (član povjerenstva)
Član povjerenstva Marko Erceg (član povjerenstva)
Ustanova koja je dodijelila akademski / stručni stupanj Sveučilište u Zagrebu Prirodoslovno-matematički fakultet (Matematički odsjek) Zagreb
Datum i država obrane 2022-12-01, Hrvatska
Znanstveno / umjetničko područje, polje i grana PRIRODNE ZNANOSTI Matematika
Sažetak U ovome radu se bavimo proučavanjem izražajne snage jezika SQL, najviše u pogledu nemogućnosti iskazivanja rekurzivnih upita u jezgrenom dijelu SQL-a koji pokriva standard jezika iz 1992. godine. Granice izražajnosti postavljamo pomoću svojstva lokalnosti upita te dajemo skicu dokaza teorema o lokalnosti upita, koristeći pritom proširenje relacijske algebre agregatima, logiku s agregatima i logiku s brojanjem. Bavimo se važnim dodatkom jeziku SQL u standardu iz 1999. godine rekurzijom, te se osvrćemo na ograničenja vezana uz zadavanje rekurzivnih upita u tom standardu. U prvom poglavlju definiramo pojmove vezane uz relacijski model baza podataka i operatora relacijske algebre. Na konkretnom primjeru baze podataka prikazujemo djelovanje definiranih operatora. U drugom poglavlju opisujemo djelovanje operatora jezgrene verzije SQL-a koristeći pritom bazu podataka iz prvog poglavlja. Dajemo i kratak pregled povijesti SQL-a u pogledu standardizacije jezika. U zadnjem dijelu poglavlja bavimo se rekurzijom, motivacijom za uvodenje rekurzije i praktičnim primjenama rekurzivnih upita. U trećem i završnom poglavlju uvodimo proširenje relacijske algebre agregatnim funkcijama, grupiranjem i aritmetičkim operacijama u oznaci ALG\(_\text{aggr}\). Uvodimo pojam lokalnosti i iskazujemo rezultate o izražajnoj snazi SQL-a koristeći to svojstvo. U nastavku poglavlja dajemo skicu dokaza važnog rezultata (teorem 3.3.8), uvodeći pritom dva jezika za postavljanje upita bazirana na logici - logike \(\mathcal{L}_\text{aggr}\) i \(\mathcal{L}_\text{C}\). Na kraju poglavlja iskazujemo ograničenja vezana za zadavanje rekurzivnih upita te se bavimo svojstvima upita poput monotonosti, linearnosti, egzistencije i jedinstvenosti fiksne točke i slično.
Sažetak (engleski) In this paper, we deal with examining the expressive power of the SQL language, mostly in regards to the inability to express recursive queries in the core SQL language which encompasses the standard from 1992. Expressiveness boundaries are set using the feature of locality. We provide a draft of the proof of the locality of queries by using the extension of relational algebra via aggregates, aggregate logic and counting logic. We deal with an important addition to the SQL language in the standard from 1999 recursion, as well as consider the limits related to defining recursive queries in that standard. In the first chapter, we define terms related to the relational database model and relational algebra operators. We showcase the effect of the defined operators by giving a practical example. In the second chapter, we describe the effect of core SQL operators while using the database examples from the first chapter. We also provide a short overview of the history of SQL with regards to language standardization. In the last part of the chapter we deal with recursion, the motivation for introducing recursion and give practical examples of recursive queries. In the third and final chapter, we introduce the extension of relational algebra via aggregate functions, grouping and arithmetic operations, denoted by ALG\(_\text{aggr}\). We introduce the notion of locality and use it to state the results of the expressive power of SQL. Furthermore, we provide a sketch of the proof of an important result (theorem 3.3.8), while also introducing two query languages based on logic - \(\mathcal{L}_\text{aggr}\) and \(\mathcal{L}_\text{C}\). At the end of the chapter, we showcase the limitations related to defining recursive queries and also deal with query features such as monotonicity, linearity, the existence and uniqueness of a fixed point, etc.
Ključne riječi
rekurzivni upiti
standard jezika iz 1992.
relacijska algebra
agregati
logika s agregatima
logika s brojanjem
standardizacija jezika
pojam lokalnosti
Ključne riječi (engleski)
recursive queries
language standard from 1992
relational algebra
aggregates
aggregate logic
counting logic
language standardization
notion of locality
Jezik hrvatski
URN:NBN urn:nbn:hr:217:697078
Studijski program Naziv: Računarstvo i matematika Vrsta studija: sveučilišni Stupanj studija: diplomski Akademski / stručni naziv: magistar/magistra računarstva i matematike (mag. inf. et math.)
Vrsta resursa Tekst
Način izrade datoteke Izvorno digitalna
Prava pristupa Otvoreni pristup
Uvjeti korištenja
Datum i vrijeme pohrane 2022-12-14 11:31:11