Marburg, Universiẗat, Diss., 2002.

Universiẗat, Diss., 2002--Marburg.

We are now in an era where the technology has rapidly become democratized. The restrictions of relational databases to address the requirements of contemporary application domains, such as semantic web and social networking, where data has an inherited graph structure underlying in it, leads to the development of new technology called Graph Databases. Graph databases can be defined as those in which data structures for the schema and instances are modelled as graphs and data manipulation is expressed by graph-traversal operations. On the other hand, the Complexity involved in the relational model to process large queries quickly involving complex join operations leads to the development of the Join-Core. The Join Core consists of a set of tables that store the relationships of data. With join core, no relations or intermediate results need to be retrieved, generated, or transferred, only query results need to be transferred over the networks. In this study, an overview and comparison of current graph database models like AllegroGraph, FlockDB, Neo4j, Sones, DEX etc. is presented. The comparison shows that Neo4j is the most popular and highly recommended among all graph databases. Also the experimental results of Join Core against Neo4j graph database shows that join core performance is more efficient that Neo4j when the query has complex join operations involved in it.

Data is distributed across interconnected relations in relational databases. Relationships between tuples can be rearranged in distinct relations by matching the values of the join attribute, a process called equi-join operation. Unlike standard attempts to design efficient join algorithms in this thesis, an approach is proposed to align tuples in relation so that joins can be readily and effectively done. We position tuples in their respective relationships, called relations alignment, which has matching join attribute values in the corresponding positions. We also address how to align relations and perform joins on aligned relations. The experiments were conducted in this research to measure and analyze the efficiency of the proposed approach compared to standard MySQL joins.

O operador de Junção é um operador importante da Álgebra Relacional que combina os pares de tuplas que atendem a uma dada condição de comparação entre os valores dos atributos de duas relações. Quando a comparação avalia a similaridade entre pares de valores, o operador é chamado Junção por Similaridade. Esse operador tem aplicações em diversos contextos, tais como o suporte de tarefas de mineração e análise de dados em geral, e a detecção de quase-duplicatas, limpeza de dados e casamento de cadeias de caracteres em especial. Dentre os operadores de junção por similaridade existentes, a Junção por Abrangência (range join) é a mais explorada na literatura. Contudo, ela apresenta limitações, tal como a dificuldade para se encontrar um limiar de similaridade adequado. Nesse contexto, a Junção por k-vizinhos mais próximos (knearest neighbor join kNN join) é considerada mais intuitiva, e portanto mais útil que o range join. Entretanto, executar um kNN join é computacionalmente mais caro, o que demanda por abordagens baseadas na técnica de laço aninhado, e as técnicas existentes para a otimização do algoritmo são restritas a um domínio de dados em particular. Visando agilizar e generalizar a execução do kNN join, a primeira contribuição desta tese foi o desenvolvimento do algoritmo QuickNearest, baseado na técnica de divisão e conquista, que é independente do domínio dos dados, independente da função de distância utilizada, e que computa kNNjoins de maneira muito eficiente. Os experimentos realizados apontam que o QuickNearest chega a ser 4 ordens de magnitude mais rápido que os métodos atuais. Além disso, o uso de operadores de junção por similaridade em ambientes relacionais é problemático, principalmente por dois motivos: (i)emgeral o resultado tem cardinalidade muito maior do que o realmente necessário ou esperado pela maioria das aplicações de análise de dados; e (ii) as consultas que os utilizam envolvem também operações de ordenação, embora a ordem seja um conceito não associado à teoria relacional. A segunda contribuição da tese aborda esses dois problemas, tratando os operadores de junção por similaridade existentes como casos particulares de um conjunto mais amplo de operadores binários, para o qual foi definido o conceito de Wide-joins. Os operadores wide-joins recuperam os pares mais similares em geral e incorporam a ordenação como uma operação interna ao processamento, de forma compatível com a teoria relacional e que permite restringir a cardinalidade dos resultados a tuplas de maior interesse para as aplicações. Os experimentos realizados mostram que os wide-joins são rápidos o suficiente para serem usados em aplicações reais, retornam resultados de qualidade melhor do que os métodos concorrentes e são mais adequados para execução num ambiente relacional do que os operadores de junção por similaridade tradicionais. / Joins are important Relational Algebra operators. They pair tuples from two relations that meet a given comparison condition between the attribute values. When the evaluation compares the similarity among the values, the operator is called a Similarity Join. This operator has application to a variety of contexts, such as supporting data mining tasks and data analysis in general, and near-duplicate detection, data cleaning and string matching in particular. Among the existing types of similarity joins, the range join is the most explored one in the literature. However, it has several shortcomings, such as the diculty to find adequate similarity thresholds. In such context, the k-nearest neighbors join (kNN join) is considered more intuitive, and therefore more useful than the range join. However, the kNN join execution is computationally well more expensive, thus demanding implementations either based on nested loop techniques, which are generic, or on optimizing techniques but that are specific data given domains. In order to accelerate and generalize kNN join execution, the first contribution of this thesis was the development of the QuickNearest algorithm, based on the divide and conquest approach that is independent of the data domain, independent of the distance function used, and that computes kNN joins very eciently. Experiments performed with the QuickNearest algorithm show that it is up to four orders of magnitude faster than current methods. Nevertheless, using similarity join operators in relational environments remains generally troublesome, due to two main reasons: (i) the result often has a cardinality much larger than what is actually needed or expected by most of the data analysis applications; and (ii) queries that use them almost always also require sorting operations, but order concept is not present in the relational theory. The second contribution of the thesis addresses these two problems through the definition of the concept of Wide-joins, which turns the existing similarity join operators just as particular cases of a more powerful set of binary operators. Awide-join operator retrieves the pairs most similar in general and already incorporates ordering as an internal operation to its processing, what makes it fully compatible with the relational theory. The concept also provides powerful ways to restrict the result cardinality just to tuples really meaningful for the applications. In fact, the experiments have also shown that wide-joins are fast enough to be useful for real applications, they return results of better quality than competing methods, and are more suitable for execution in a relational environment than the traditional similarity join operators.

O operador de Junção é um operador importante da Álgebra Relacional que combina os pares de tuplas que atendem a uma dada condição de comparação entre os valores dos atributos de duas relações. Quando a comparação avalia a similaridade entre pares de valores, o operador é chamado Junção por Similaridade. Esse operador tem aplicações em diversos contextos, tais como o suporte de tarefas de mineração e análise de dados em geral, e a detecção de quase-duplicatas, limpeza de dados e casamento de cadeias de caracteres em especial. Dentre os operadores de junção por similaridade existentes, a Junção por Abrangência (range join) é a mais explorada na literatura. Contudo, ela apresenta limitações, tal como a dificuldade para se encontrar um limiar de similaridade adequado. Nesse contexto, a Junção por k-vizinhos mais próximos (knearest neighbor join kNN join) é considerada mais intuitiva, e portanto mais útil que o range join. Entretanto, executar um kNN join é computacionalmente mais caro, o que demanda por abordagens baseadas na técnica de laço aninhado, e as técnicas existentes para a otimização do algoritmo são restritas a um domínio de dados em particular. Visando agilizar e generalizar a execução do kNN join, a primeira contribuição desta tese foi o desenvolvimento do algoritmo QuickNearest, baseado na técnica de divisão e conquista, que é independente do domínio dos dados, independente da função de distância utilizada, e que computa kNNjoins de maneira muito eficiente. Os experimentos realizados apontam que o QuickNearest chega a ser 4 ordens de magnitude mais rápido que os métodos atuais. Além disso, o uso de operadores de junção por similaridade em ambientes relacionais é problemático, principalmente por dois motivos: (i)emgeral o resultado tem cardinalidade muito maior do que o realmente necessário ou esperado pela maioria das aplicações de análise de dados; e (ii) as consultas que os utilizam envolvem também operações de ordenação, embora a ordem seja um conceito não associado à teoria relacional. A segunda contribuição da tese aborda esses dois problemas, tratando os operadores de junção por similaridade existentes como casos particulares de um conjunto mais amplo de operadores binários, para o qual foi definido o conceito de Wide-joins. Os operadores wide-joins recuperam os pares mais similares em geral e incorporam a ordenação como uma operação interna ao processamento, de forma compatível com a teoria relacional e que permite restringir a cardinalidade dos resultados a tuplas de maior interesse para as aplicações. Os experimentos realizados mostram que os wide-joins são rápidos o suficiente para serem usados em aplicações reais, retornam resultados de qualidade melhor do que os métodos concorrentes e são mais adequados para execução num ambiente relacional do que os operadores de junção por similaridade tradicionais. / Joins are important Relational Algebra operators. They pair tuples from two relations that meet a given comparison condition between the attribute values. When the evaluation compares the similarity among the values, the operator is called a Similarity Join. This operator has application to a variety of contexts, such as supporting data mining tasks and data analysis in general, and near-duplicate detection, data cleaning and string matching in particular. Among the existing types of similarity joins, the range join is the most explored one in the literature. However, it has several shortcomings, such as the diculty to find adequate similarity thresholds. In such context, the k-nearest neighbors join (kNN join) is considered more intuitive, and therefore more useful than the range join. However, the kNN join execution is computationally well more expensive, thus demanding implementations either based on nested loop techniques, which are generic, or on optimizing techniques but that are specific data given domains. In order to accelerate and generalize kNN join execution, the first contribution of this thesis was the development of the QuickNearest algorithm, based on the divide and conquest approach that is independent of the data domain, independent of the distance function used, and that computes kNN joins very eciently. Experiments performed with the QuickNearest algorithm show that it is up to four orders of magnitude faster than current methods. Nevertheless, using similarity join operators in relational environments remains generally troublesome, due to two main reasons: (i) the result often has a cardinality much larger than what is actually needed or expected by most of the data analysis applications; and (ii) queries that use them almost always also require sorting operations, but order concept is not present in the relational theory. The second contribution of the thesis addresses these two problems through the definition of the concept of Wide-joins, which turns the existing similarity join operators just as particular cases of a more powerful set of binary operators. Awide-join operator retrieves the pairs most similar in general and already incorporates ordering as an internal operation to its processing, what makes it fully compatible with the relational theory. The concept also provides powerful ways to restrict the result cardinality just to tuples really meaningful for the applications. In fact, the experiments have also shown that wide-joins are fast enough to be useful for real applications, they return results of better quality than competing methods, and are more suitable for execution in a relational environment than the traditional similarity join operators.

University, Diss., 1999--Osnabrück.

Information integration has been widely addressed over the last several decades. However, it is far from solved due to the complexity of resolving schema and data heterogeneities. In this paper, we propose out attempt to alleviate such difficulty by realizing keyword search functionality for integrating information from heterogeneous databases. Our solution does not require predefined global schema or any mappings between databases. Rather, it relies on an operator called keyword join to take a set of lists of partial answers from different data sources as input, and output a list of results that are joined by the tuples from input lists based on predefined similarity measures as integrated results. Our system allows source databases remain autonomous and the system to be dynamic and extensible. We have tested our system with real dataset and benchmark, which shows that our proposed method is practical and effective. / Singapore-MIT Alliance (SMA)

Upcoming processors are combining different computing units in a tightly-coupled approach using a unified shared memory hierarchy. This tightly-coupled combination leads to novel properties with regard to cooperation and interaction. This paper demonstrates the advantages of those processors for a stream-join operator as an important data-intensive example. In detail, we propose our HELLS-Join approach employing all heterogeneous devices by outsourcing parts of the algorithm on the appropriate device. Our HELLS-Join performs better than CPU stream joins, allowing wider time windows, higher stream frequencies, and more streams to be joined as before.

abstract: Skyline queries extract interesting points that are non-dominated and help paint the bigger picture of the data in question. They are valuable in many multi-criteria decision applications and are becoming a staple of decision support systems. An assumption commonly made by many skyline algorithms is that a skyline query is applied to a single static data source or data stream. Unfortunately, this assumption does not hold in many applications in which a skyline query may involve attributes belonging to multiple data sources and requires a join operation to be performed before the skyline can be produced. Recently, various skyline-join algorithms have been proposed to address this problem in the context of static data sources. However, these algorithms suffer from several drawbacks: they often need to scan the data sources exhaustively to obtain the skyline-join results; moreover, the pruning techniques employed to eliminate tuples are largely based on expensive tuple-to-tuple comparisons. On the other hand, most data stream techniques focus on single stream skyline queries, thus rendering them unsuitable for skyline-join queries. Another assumption typically made by most of the earlier skyline algorithms is that the data is complete and all skyline attribute values are available. Due to this constraint, these algorithms cannot be applied to incomplete data sources in which some of the attribute values are missing and are represented by NULL values. There exists a definition of dominance for incomplete data, but this leads to undesirable consequences such as non-transitive and cyclic dominance relations both of which are detrimental to skyline processing. Based on the aforementioned observations, the main goal of the research described in this dissertation is the design and development of a framework of skyline operators that effectively handles three distinct types of skyline queries: 1) skyline-join queries on static data sources, 2) skyline-window-join queries over data streams, and 3) strata-skyline queries on incomplete datasets. This dissertation presents the unique challenges posed by these skyline queries and addresses the shortcomings of current skyline techniques by proposing efficient methods to tackle the added overhead in processing skyline queries on static data sources, data streams, and incomplete datasets. / Dissertation/Thesis / Doctoral Dissertation Computer Science 2014