The goal of this thesis is to design and implement a SQL frontend for Bobox framework which is being developed by Department of software engineering MFF UK. The development of the Bobox framework is motivated by the effort to simplify writing parallel software. The Bobox framework is one of many system implementations for processing stream data and provides runtime environment for evaluating execution plans in the parallel environment. This thesis deals with implementation of a frontend for this framework. The input is a query in SQL language and information about database structure. Frontend will perform syn- tactic and semantic analysis and then translate the input query into intermediate code. The output of this frontend is the intermediate code in the form of relatio- nal algebra written as XML and is used as the input for the following optimizing backend.

No description available.

This thesis deals with the design and implementation of an optimizer and a transformer of relational queries. Firstly, the thesis describes the theory of the relational query compilers. Secondly, we present the data structures and algorithms used in the implemented tool. Finally, the important implementation details of the developed tool are discussed. Part of the thesis is the selection of used relational algebra operators and design of an appropriate input. Input of the implemented software is a query written in a XML file in the form of relational algebra. Query is optimized and transformed into physical plan which will be executed in the parallelization framework Bobox. Developed compiler outputs physical plan written in the Bobolang language, which serves as an input for the Bobox. Powered by TCPDF (www.tcpdf.org)

Apesar de muito trabalho ter sido dispendido sobre linguagens de consulta a Sistemas de Gerenciamento de Bancos de Dados Relacionais, existem somente dois paradigmas básicos para essas linguagens, que são representados pela Structured Query Language – SQL e pela Query by Example – QBE. Apesar dessas linguagens de consultas serem computacionalmente completas, elas tem a desvantagem de não permitir ao usuário nenhuma interação gráfica com a informação contida na base de dados. Um dos principais desenvolvimentos na área de base de dados diz respeito às ferramentas que proveêm aos usuários um entendimento simples da base de dados e uma extração amigável da informação. A linguagem descrita neste trabalho possibilita que usuários criem consultas graficamente por meio de diagramas de fluxo de dados. Além da linguagem de consulta gráfica, este trabalho mostra também a ferramenta de apoio Data Flow Query Language - DFQL, que é um editor/executor de consultas construído para suportar essa linguagem, através de um conjunto de operadores representados graficamente, e a execução desses diagramas, analisando a rede e gerando os comandos correspondentes em SQL para realização da consulta. Esses comandos são submetidos ao sistema de gerenciamento de banco de dados e o resultado é mostrado/gravado conforme a consulta feita. / In spite of many works done on query languages, all existing languages are direct extensions of Structured Query Language – SQL and query-By-Example – QBE. These two languages were developed in the beginning of the Relational Database Management Systems – RDBMS development. Althoug these languages are computationally complete, they take the disadvantage of not supporting graphical interaction with data. One of the the main developments in the database area concerns tools to provide users a simple understand of database content, and friendly extraction of the information. The language described in this work enables users to create graphical queries using data flow diagrams. Besides the graphical query language, this work also shows the Data Flow Query Language - DFQL tool. This tool is a query editor/executer that supports this language, using a set of operators represented graphicaly, and the diagram execution is done by analising the network and producing the respective commands in SQL to realize the query. This commands are sent to the DBMS and the result is shown/recorded according to the query.

Semantic query optimization is an important issue in many contexts of databases including information integration, view maintenance and data warehousing and can substantially improve performance, especially in today's database systems which contain gigabytes of data. A crucial issue in semantic query optimization is query containment. Several papers have dealt with the problem of conjunctive query containment. In particular, some of the literature admits SQL like query languages with aggregate operations such as sum/count. Moreover, since real SQL requires a richer semantics than set semantics, there has been work on bag-semantics for SQL, essentially by introducing an interpreted column. One important technique for reasoning about query containment in the context of bag semantics is to translate the queries to alternatives using aggregate functions and assuming set semantics. Furthermore, in SQL, order by is the operator by which the results are sorted based on certain attributes and, clearly, ordering is an important issue in query optimization. As such, there has been work done in support of ordering based on the application of the domain. However, a final step is required in order to introduce a rich semantics in support. In this work, we integrate set and bag semantics to be able to reason about real SQL queries. We demonstrate an ordered bag semantics for SQL using a relational algebra with aggregates. We define a set algebra with various expressions of interest, then define syntax and semantics for bag algebra, and finally extend these definitions to ordered bags. This is done by adding a pair of additional interpreted columns to computed relations in which the first column is used in the standard fashion to capture duplicate tuples in query results, and the second adds an ordering priority to the output. We show that the relational algebra with aggregates can be used to compute these interpreted columns with sufficient flexibility to work as a semantics for standard SQL queries, which are allowed to include order by and duplicate preserving select clauses. The reduction of a workable ordered bag semantics for SQL to the relational algebra with aggregates - as we have developed it - can enable existing query containment theory to be applied in practical query containment.

Semantic query optimization is an important issue in many contexts of databases including information integration, view maintenance and data warehousing and can substantially improve performance, especially in today's database systems which contain gigabytes of data. A crucial issue in semantic query optimization is query containment. Several papers have dealt with the problem of conjunctive query containment. In particular, some of the literature admits SQL like query languages with aggregate operations such as sum/count. Moreover, since real SQL requires a richer semantics than set semantics, there has been work on bag-semantics for SQL, essentially by introducing an interpreted column. One important technique for reasoning about query containment in the context of bag semantics is to translate the queries to alternatives using aggregate functions and assuming set semantics. Furthermore, in SQL, order by is the operator by which the results are sorted based on certain attributes and, clearly, ordering is an important issue in query optimization. As such, there has been work done in support of ordering based on the application of the domain. However, a final step is required in order to introduce a rich semantics in support. In this work, we integrate set and bag semantics to be able to reason about real SQL queries. We demonstrate an ordered bag semantics for SQL using a relational algebra with aggregates. We define a set algebra with various expressions of interest, then define syntax and semantics for bag algebra, and finally extend these definitions to ordered bags. This is done by adding a pair of additional interpreted columns to computed relations in which the first column is used in the standard fashion to capture duplicate tuples in query results, and the second adds an ordering priority to the output. We show that the relational algebra with aggregates can be used to compute these interpreted columns with sufficient flexibility to work as a semantics for standard SQL queries, which are allowed to include order by and duplicate preserving select clauses. The reduction of a workable ordered bag semantics for SQL to the relational algebra with aggregates - as we have developed it - can enable existing query containment theory to be applied in practical query containment.

Apesar de muito trabalho ter sido dispendido sobre linguagens de consulta a Sistemas de Gerenciamento de Bancos de Dados Relacionais, existem somente dois paradigmas básicos para essas linguagens, que são representados pela Structured Query Language – SQL e pela Query by Example – QBE. Apesar dessas linguagens de consultas serem computacionalmente completas, elas tem a desvantagem de não permitir ao usuário nenhuma interação gráfica com a informação contida na base de dados. Um dos principais desenvolvimentos na área de base de dados diz respeito às ferramentas que proveêm aos usuários um entendimento simples da base de dados e uma extração amigável da informação. A linguagem descrita neste trabalho possibilita que usuários criem consultas graficamente por meio de diagramas de fluxo de dados. Além da linguagem de consulta gráfica, este trabalho mostra também a ferramenta de apoio Data Flow Query Language - DFQL, que é um editor/executor de consultas construído para suportar essa linguagem, através de um conjunto de operadores representados graficamente, e a execução desses diagramas, analisando a rede e gerando os comandos correspondentes em SQL para realização da consulta. Esses comandos são submetidos ao sistema de gerenciamento de banco de dados e o resultado é mostrado/gravado conforme a consulta feita. / In spite of many works done on query languages, all existing languages are direct extensions of Structured Query Language – SQL and query-By-Example – QBE. These two languages were developed in the beginning of the Relational Database Management Systems – RDBMS development. Althoug these languages are computationally complete, they take the disadvantage of not supporting graphical interaction with data. One of the the main developments in the database area concerns tools to provide users a simple understand of database content, and friendly extraction of the information. The language described in this work enables users to create graphical queries using data flow diagrams. Besides the graphical query language, this work also shows the Data Flow Query Language - DFQL tool. This tool is a query editor/executer that supports this language, using a set of operators represented graphicaly, and the diagram execution is done by analising the network and producing the respective commands in SQL to realize the query. This commands are sent to the DBMS and the result is shown/recorded according to the query.

In Relational Algebra, the operator Division (÷) is an intuitive tool used to write queries with the concept of for all, and thus, it is constantly required in real applications. However, as we demonstrate in this MSc work, the division does not support many of the needs common to modern applications, particularly those that involve complex data analysis, such as processing images, audio, genetic data, large graphs, fingerprints, and many other non-traditional data types. The main issue is the existence of intrinsic comparisons of attribute values in the operator, which, by definition, are always performed by identity (=), despite the fact that complex data must be compared by similarity. Recent works focus on supporting similarity comparison in relational operators, but no one treats the division. MSc work proposes the new Similarity-aware Division (÷) operator. Our novel operator is naturally well suited to answer queries with an idea of candidate elements and exigencies to be performed on complex data from real applications of high-impact. For example, it is potentially useful to support agriculture, genetic analyses, digital library search, and even to help controlling the quality of manufactured products and identifying new clients in industry. We validate our proposal by studying the first two of these applications. / O operador de Divisão (÷) da Álgebra Relacional permite representar de forma simples consultas com o conceito de para todos, e por isso é requerido em diversas aplicações reais. Entretanto, evidencia-se neste trabalho de mestrado que a divisão não atende às necessidades de diversas aplicações atuais, principalmente quando estas analisam dados complexos, como imagens, áudio, textos longos, impressões digitais, entre outros. Analisando o problema verifica-se que a principal limitação é a existência de comparações de valores de atributos intrínsecas à Divisão Relacional, que, por definição, são efetuadas sempre por identidade (=), enquanto objetos complexos devem geralmente ser comparados por similaridade. Hoje, encontram-se na literatura propostas de operadores relacionais com suporte à similaridade de objetos complexos, entretanto, nenhuma trata a Divisão Relacional. Este trabalho de mestrado propõe investigar e estender o operador de Divisão da Álgebra Relacional para melhor adequá-lo às demandas de aplicações atuais, por meio de suporte a comparações de valores de atributos por similaridade. Mostra-se aqui que a Divisão por Similaridade é naturalmente adequada a responder consultas diversas com um conceito de elementos candidatos e exigências descrito na monografia, envolvendo dados complexos de aplicações reais de alto impacto, com potencial por exemplo, para apoiar a agricultura, análises de dados genéticos, buscas em bibliotecas digitais, e até mesmo para controlar a qualidade de produtos manufaturados e a identificação de novos clientes em indústrias. Para validar a proposta, propõe-se estudar as duas primeiras aplicações citadas.

隨著雲端運算的服務租用理念越來越受到重視，SaaS 服務供應商在提供服務的時候無不希望可以以最少的成本服務最多的客戶，於是吸引了許多的研究者投入精力以及時間，希望可以設計出讓租戶們共享資源又能夠有客製化空間的解決方案。服務供應商為了順利推廣多租戶軟體開發，其中一項關鍵技術是支援 SQL 語句自動轉換機制，目的是協助 SQL 語句轉換成以多租戶資料架構邏輯表達的 SQL 語句，讓租戶應用程式的軟體開發人員能夠專注在自身的應用程式開發。 開發 SQL 語句自動轉換機制，必須先選定資料庫的資料架構，本論文採用 Universal Table Layout 這個 SaaS 多租戶資料共享常見的資料架構。 我們參考知名 SaaS 廠商 Force.com 的 Universal Table Layout 資料架構，並提出一些修正。其次，我們應用關聯式代數抽象化來設計 SQL 語句的轉換規則，這些理論結果不僅在表達轉換機制上更具有一般性，並且讓轉換規則的理解也變得更加容易。我們以這些理論推導為基礎實現一個實驗的工具，最後透過幾個實驗，觀察及探討實驗數據所呈現的意義。

In Relational Algebra, the operator Division (÷) is an intuitive tool used to write queries with the concept of for all, and thus, it is constantly required in real applications. However, as we demonstrate in this MSc work, the division does not support many of the needs common to modern applications, particularly those that involve complex data analysis, such as processing images, audio, genetic data, large graphs, fingerprints, and many other non-traditional data types. The main issue is the existence of intrinsic comparisons of attribute values in the operator, which, by definition, are always performed by identity (=), despite the fact that complex data must be compared by similarity. Recent works focus on supporting similarity comparison in relational operators, but no one treats the division. MSc work proposes the new Similarity-aware Division (÷) operator. Our novel operator is naturally well suited to answer queries with an idea of candidate elements and exigencies to be performed on complex data from real applications of high-impact. For example, it is potentially useful to support agriculture, genetic analyses, digital library search, and even to help controlling the quality of manufactured products and identifying new clients in industry. We validate our proposal by studying the first two of these applications. / O operador de Divisão (÷) da Álgebra Relacional permite representar de forma simples consultas com o conceito de para todos, e por isso é requerido em diversas aplicações reais. Entretanto, evidencia-se neste trabalho de mestrado que a divisão não atende às necessidades de diversas aplicações atuais, principalmente quando estas analisam dados complexos, como imagens, áudio, textos longos, impressões digitais, entre outros. Analisando o problema verifica-se que a principal limitação é a existência de comparações de valores de atributos intrínsecas à Divisão Relacional, que, por definição, são efetuadas sempre por identidade (=), enquanto objetos complexos devem geralmente ser comparados por similaridade. Hoje, encontram-se na literatura propostas de operadores relacionais com suporte à similaridade de objetos complexos, entretanto, nenhuma trata a Divisão Relacional. Este trabalho de mestrado propõe investigar e estender o operador de Divisão da Álgebra Relacional para melhor adequá-lo às demandas de aplicações atuais, por meio de suporte a comparações de valores de atributos por similaridade. Mostra-se aqui que a Divisão por Similaridade é naturalmente adequada a responder consultas diversas com um conceito de elementos candidatos e exigências descrito na monografia, envolvendo dados complexos de aplicações reais de alto impacto, com potencial por exemplo, para apoiar a agricultura, análises de dados genéticos, buscas em bibliotecas digitais, e até mesmo para controlar a qualidade de produtos manufaturados e a identificação de novos clientes em indústrias. Para validar a proposta, propõe-se estudar as duas primeiras aplicações citadas.