Search

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. 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.

U okviru ovog diplomskog rada proučeni su i opisani postupci statičke i dinamičke analize programskog kôda aplikacije te je analizirana njihova primjenjivost za otkrivanje, izlučivanje i izmjenu pristupa bazi podataka iz aplikacije. Ocijenjena je složenost pojedinih postupaka analize i mogućnost njihova programskog ostvarenja s obzirom na različite oblike opisa aplikacije, kao što su izvorni kod, međukod ili izvodivi kod te različite načine ostvarenja pristupa bazi podataka, kao što su izravna uporaba SQL upita ili primjena objektno-relacijskog preslikavanja. Na osnovu zaključaka provedene analize, odabran je Apache Calcite razvojni okvir kao osnova za oblikovanje i programsko ostvarenje alata za otkrivanje, izlučivanje i izmjenu pristupa bazi podataka iz aplikacije. Za svaki pronađeni pristup bazi podataka određen je upit kojim se ostvaruje pristup i izgrađen je model koji opisuje uporabu dijelova podatkovne sheme baze podataka u pojedinim cjelinama aplikacije. As part of this master thesis, a numerous methods for static and dynamic analysis of the application code are considered with the special focus on their applicability for detecting, extracting and modifying database access points. The individual complexity of each analysis procedure is evaluated keeping in mind the possibility of their software implementation with regard to various forms of describing the application, such as source code, intermediate or executable code, and various database access methods such as direct use of SQL queries or using object-relational mapping. Based on the conclusions of the analysis carried out, the Apache Calcite framework was selected as the basis for the custom multi-cloud rewriter library developed not only to dynamically intercept and rewrite queries, but also extract information about parts of the database schema used in queries.

Relacijska algebra

Promatraju se jezici za postavljanje upita u relacijskim bazama podataka. Osim klasičnih jezika koji su ekvivalentni relacijskoj algebri odnosno relacijskom računu, uvode se i proširenja tih jezika pomoću rekurzije i negacije. Proučava se ekspresivnost uvedenih jezika, te kompleksnost izvrednjavanja upita u njima.