Izražajna snaga jezika SQL

master's thesis

• 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
• Created on: 2022-12-14 11:31:11