Title Izražajna snaga jezika SQL
Title (english) The expressive power of the SQL language
Author Antonela Bogdanić
Mentor Marko Horvat (mentor)
Committee member Marko Horvat (predsjednik povjerenstva)
Committee member Tina Bosner (član povjerenstva)
Committee member Matej Mihelčić (član povjerenstva)
Committee member Marko Erceg (član povjerenstva)
Granter University of Zagreb Faculty of Science (Department of Mathematics) Zagreb
Defense date and country 2022-12-01, Croatia
Scientific / art field, discipline and subdiscipline NATURAL SCIENCES Mathematics
Abstract 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.
Abstract (english) 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.
Keywords
rekurzivni upiti
standard jezika iz 1992.
relacijska algebra
agregati
logika s agregatima
logika s brojanjem
standardizacija jezika
pojam lokalnosti
Keywords (english)
recursive queries
language standard from 1992
relational algebra
aggregates
aggregate logic
counting logic
language standardization
notion of locality
Language croatian
URN:NBN urn:nbn:hr:217:697078
Study programme Title: Computer Science and Mathematics Study programme type: university Study level: graduate Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
Type of resource Text
File origin Born digital
Access conditions Open access
Terms of use
Created on 2022-12-14 11:31:11