The rapidly growing number of scientific publications poses numerous challenges for researchers engaged in literature analyses. Structured methodologies like systematic literature reviews are becoming increasingly expensive, considering their attempt to cover all relevant publications. Despite the increasing efforts needed, the importance of literature reviews also leads to an increasing growth in their number. While there are support techniques (e.g., guidelines, tools, checklists) for conducting literature analyses, a concise and clear overview of such techniques for assessing the quality of the analysis itself is missing. Such an overview can help researchers identify techniques for their work, understand ambiguities between them, support peer reviews, and guide future research by highlighting open gaps. In this paper, we address this lack of an overview by identifying existing techniques for assessing the quality of systematic literature reviews, comparing their properties, and discussing their pros and cons. For this purpose, we elicited 14 techniques through a systematic literature search covering 15 years (2007–2021). Overall, our contributions can help researchers identify feasible techniques for assessing the quality of literature analyses and can guide the development of new techniques, thereby facilitating the conduct and improving the quality of literature analyses.

Today’s processor landscape is increasingly heterogeneous with the availability of co-processors. This landscape impacts query engines, as they need to be reworked to keep competitive performance by leveraging the underlying architectures. Such a rework might be costly if, for each external processor or SDK, peripheral components needed to be developed as well; resulting in redundant effort and adoption difficulties. In this paper, we propose an approach to overcome these shortcomings through ADAMANT – a query executor equipped with interfaces to plug-in new co-processors without reworking other components of a query engine. ADAMANT consists of 1) pluggable interfaces that allow interaction with co-processors, encapsulating operator implementations, and 2) a unified runtime that handles the execution on arbitrary co-processors, with a chunked execution model for scalable query processing. To evaluate ADAMANT’s versatility, we plug different implementations of a CPU/GPU-based system (using OpenCL, OpenMP, & CUDA) and analyze their performance on TPC-H queries. We identify a 4x performance difference between an arbitrary chunked execution vs. a more architecturally conscious pipelined execution. Furthermore, our comparisons with HeavyDB show complex performance variations from speed-ups up to a factor of 2x from our hardware-conscious execution. We envision initiatives like ADAMANT to ease the study of complex optimizations required in co-processor systems, paving the way for efficient and portable data management tools without cutbacks.

Abstract Using heterogeneous processing devices, like GPUs, to accelerate relational database operations is a well-known strategy. In this context, the operation is highly interesting for two reasons. Firstly, it incurs large processing costs. Secondly, its results (i.e., aggregates) are usually small, reducing data movement costs whose compensation is a major challenge for heterogeneous computing. Generally, for computation on GPUs, one relies either on sorting or hashing. Today, empirical results suggest that hash-based approaches are superior. However, by concept, hashing induces an unpredictable memory access pattern conflicting with the architecture of GPUs. This motivates studying why current sort-based approaches are generally inferior. Our results indicate that current sorting solutions cannot exploit the full parallel power of modern GPUs. Experimentally, we show that the issue arises from the need to synchronize parallel threads that access the shared memory location containing the aggregates via . Our quantification of the optimal performance motivates us to investigate how to minimize the overhead of atomics. This results in different variants using atomics, where the best variants almost mitigate the atomics overhead entirely. The results of a large-scale evaluation reveal that our approach achieves a 3x speed-up over existing sort-based approaches and up to 2x speed-up over hash-based approaches.

Abstract GPU accelerated query execution is still ongoing research in the database community, as GPUs continue to be heterogeneous in their architectures varying their capabilities (e.g., their newest selling point: tensor cores). Hence, many researchers come up with optimal operator implementations for a specific device generation involving tedious operator tuning by hand. Alternatively, there is a growing availability of GPU libraries providing optimized operators for various applications. However, the question arises of how mature these libraries are and whether they are fit to replace handwritten operator implementations not only w.r.t. implementation effort and portability but also performance. In this paper, we investigate various general-purpose libraries that are both portable and easy to use for arbitrary GPUs to test their production readiness on the example of database operations. To this end, we develop a framework to show the support of GPU libraries for database operations that allows a user to plug-in new libraries and custom-written code. Our framework allows for easy pluggability of new libraries for query execution using a simple task model. Using this framework, we develop multiple libraries (ArrayFire, Thrust, and boost.compute) supporting many database operations. We use these libraries to experiment with different devices to see the impact of the underlying device. Based on our experiments, we see a significant diversity in terms of performance among libraries. Furthermore, one of the fundamental database primitives—hashing, and thus hash joins—is currently not supported, leaving important tuning potential unused.

Efficient knn computation for high-dimensional data is an important, yet challenging task. Today, most information systems use a column-store back-end for relational data. For such systems, multi-dimensional indexes accelerating selections are known. However, they cannot be used to accelerate knn queries. Consequently, one relies on sequential scans, specialized knn indexes, or trades result quality for speed. To avoid storing one specialized index per query type, we envision multipurpose indexes allowing to efficiently compute multiple query types. In this paper, we focus on additionally supporting knn queries as first step towards this goal. To this end, we study how to exploit total orders for accelerating knn queries based on the sub-space distance equalities observation. It means that non-equal points in the full space, which are projected to the same point in a sub space, have the same distance to every other point in this sub space. In case one can easily find these equalities and tune storage structures towards them, this offers two effects one can exploit to accelerate knn queries. The first effect allows pruning of point groups based on a cascade of lower bounds. The second allows to re-use previously computed sub-space distances between point groups. This results in a worst-case execution bound, which is independent of the distance function. We present knn algorithms exploiting both effects and show how to tune a storage structure already known to work well for multi-dimensional selections. Our investigations reveal that the effects are robust to increasing, e.g., the dimensionality, suggesting generally good knn performance. Comparing our knn algorithms to well-known competitors reveals large performance improvements up to one order of magnitude. Furthermore, the algorithms deliver at least comparable performance as the next fastest competitor suggesting that the algorithms are only marginally affected by the curse of dimensionality.

Entity resolution (ER) is a process to identify records that refer to the same real-world entity. In recent years, facing the ever-increasing data volume, both blocking techniques and parallel computation have been proposed for ER to reduce its running time and improve efficiency. It is popular and convenient to apply the MapReduce programming model for parallel computation. With the default load balancing strategy, if the block sizes are skewed, an imbalanced reducer load will occur and significantly increase the runtime. One possible solution is block-splitting: breaking the overpopulated blocks into smaller sub-blocks, to improve efficiency. In this paper we analyze the advantages and disadvantages of state-of-the-art block splitting methods (BlockSplit and BlockSlicer), and we propose two approaches: TLS and BOS to overcome the identified drawbacks. We comprehensively evaluate and compare our proposed solutions, with Spark implementations, using real-world and synthetic datasets with different properties. The results show that all of them can balance the reducer load with the help of the greedy partition assignment strategy. When memory of used cluster is not abundant given a dataset, a high number of reducers is required to reduce the GC time to improve efficiency. Partitcularly, our TLS and BOS have overwelmingly lower overhead due to the ability of block-wise composite key assignment.

Reproducibility and generalizability are important criteria for today’s data management society. Hence, stand-alone solutions that work well in isolation, but cannot convince at system level lead to a frustrating user experience. As a consequence, in our demo, we take the step of accelerating queries on scientific data by integrating the multi-dimensional index structure Elf into the main-memory-optimized database management system MonetDB. The overall intention is to show that the stand-alone speed ups of using Elf can also be observed when integrated into a holistic system storing scientific data sets. In our prototypical implementation, we demonstrate the performance of an Elf-backed MonetDB on the standard OLAP-benchmark, TPC-H, and the genomic multi-dimensional range query benchmark from the scientific data community. Queries can be run live on both benchmarks by the audience, while they are able to create different indexes to accelerate selection performance.

Efficient evaluation of selection predicates is a performance-critical task, for instance to reduce intermediate result sizes being the input for further operations. With analytical queries getting more and more complex, the number of evaluated selection predicates per query and table rises, too. This leads to numerous multi-column selection predicates. Recent approaches to increase the performance of main-memory databases for selection-predicate evaluation aim at optimally exploiting the speed of the CPU by using accelerated scans. However, scanning each column one by one leaves tuning opportunities open that arise if all predicates are considered together. To this end, we introduce Elf, an index structure that is able to exploit the relation between several selection predicates. Elf features cache sensitivity, an optimized storage layout, fixed search paths, and slight data compression. In a large-scale evaluation, we compare its query performance to state-of-the-art approaches and a sequential scan using SIMD capabilities. Our results indicate a clear superiority of our approach for queries returning less than 10 percent of all tuples - a selectivity almost one order of magnitude larger than observed for related indexing approaches. For TPC-H queries with multi-column selection predicates, we achieve a speedup between factor five and two orders of magnitude, mainly depending on the selectivity of the predicates. Further scaling experiments reveal that for large data sets, these speedup factors are expected to increase, due to more densely populated data spaces. Finally, our results indicate that using a delta-store like concept to support periodic insertions results in virtually no performance penalty for reasonable sizes of a write-optimized Elf as delta store.

In the published version of EnumerateCmp in the Section 3.3 on Page 936 [1], see also Algorithm 1, a small error is included in Line 5. In the first call of EnumerateCsgRec, too many nodes ( X ∪ N ) will be excluded for the emission of complements, leading to the fact that, in general, not all complements will be emitted correctly.

Searching in sorted arrays of keys is a common task with a broad range of applications. Often searching is part of the performance critical sections of a database query or index access, raising the question what kind of search algorithm to choose and how to optimize it to obtain the best possible performance on real-world hardware. This paper strives to answer this question by evaluating a large set of optimized sequential, binary and k-ary search algorithms on a modern processor. In this context, we consider hardware-sensitive optimization strategies as well as algorithmic variations resulting in an eight-dimensional evaluation space. As a result, we give insights on expected interactions between search algorithms and optimizations on modern hardware. In fact, there is no single best optimized algorithm, leading to a set of advices on which variants should be considered first given a particular array size.

Evaluating selection predicates is a data-intensive task that reduces intermediate results, which are the input for further operations. With analytical queries getting more and more complex, the number of evaluated selection predicates per query and table rises, too. This leads to numerous multicolumn selection predicates. Recent approaches to increase the performance of main-memory databases for selection-predicate evaluation aim at optimally exploiting the speed of the CPU by using accelerated scans. However, scanning each column one by one leaves tuning opportunities open that arise if all predicates are considered together. To this end, we introduce Elf, an index structure that is able to exploit the relation between several selection predicates. Elf features cache sensitivity, an optimized storage layout, fixed search paths, and slight data compression. In our evaluation, we compare its query performance to state-of the-art approaches and a sequential scan using SIMD capabilities. Our results indicate a clear superiority of our approach for multicolumn selection predicate queries with a low combined selectivity. For TPC-H queries with multi-column selection predicates, we achieve a speed-up between a factor of five and two orders of magnitude, mainly depending on the selectivity of the predicates.

Employing special-purpose processors (e.g., GPUs) in database systems has been studied throughout the last decade. Research on heterogeneous database systems that use both general-and special-purpose processors has addressed either transaction-or analytic processing, but not the combination of them. Support for hybrid transaction-and analytic processing (HTAP) has been studied exclusively for CPU-only systems. In this paper we ask the question whether current systems are ready for HTAP workload management with cooperating general- and special-purpose processors. For this, we take the perspective of the backbone of database systems: the storage engine. We propose a unified terminology and a comprehensive taxonomy to compare state-of-the-art engines from both domains. We show similarities and differences, and determine a necessary set of features for engines supporting HTAP workload on CPUs and GPUs. Answering our research question, our findings yield a resolute: not yet.

Analysis of genomes has a wide range of applications from disease susceptibility studies to plant breeding research. For example, di↵erent types of barley have di↵ering characteristics regarding draught or salt tolerance. Thus, a typical use case is comparing two plant genomes and try to deduce which genes are responsible for a certain resistance. For this, we need to find di↵erences in large volumes of aligned genome data, which is already available in large genome databases. The challenge is to eciently retrieve the genotypes of a certain range of the genome, and then, to determine variants and their impact on the plant organism. State-of-the-art tools are fixed pipelines with a fixed parametrization. However, in practice, users want to interactively analyse genome data and need to customize the parametrization. In this demonstration, we show how we can support flexible ad-hoc analyses of arbitrary plant genomes using SQL with a small set of user-defined aggregation functions and dynamic parametrization. Furthermore, we demonstrate how genome analysis workflows for variant calling can be applied to our system and provide insights about the performance of our system.

Satisfying the performance needs of tomorrow typically im-plies using modern processor capabilities (such as single in-struction, multiple data) and co-processors (such as graphics processing units) to accelerate database operations. Algo-rithms are typically hand-tuned to the underlying (co-)pro-cessors. This solution is error-prone, introduces high imple-mentation and maintenance cost and one implementations is not portable to other (co-)processors. To this end, we argue for a combination of database research with modern software-engineering approaches. We emphasize our vision of generating optimized database algorithms tailored to used (co-)processors from a common code base. With this, we maximize performance while minimizing implementation and maintenance effort of hardware-tailored database operations. 1.

Improvements in DNA sequencing technologies allow to sequence complete human genomes in a short time and at acceptable cost. Hence, the vision of genome analysis as standard procedure to support and improve medical treatment becomes reachable. In this vision paper, we describe important data-management challenges that have to be met to make this vision come true. Besides genome-analysis performance, data-management capabilities such as data provenance and data integrity become increasingly important to enable comprehensible and reliable genome analysis. We argue to meet these challenges by using main-memory database technologies, which combine fast processing capabilities with extensive data-management capabilities. Finally, we discuss possibilities of integrating genome-analysis tasks into DBMSs and derive new research questions.

The past years saw the emergence of highly heterogeneous server architectures that feature multiple accelerators in addition to the main processor. Efficiently exploiting these systems for data processing is a challenging research problem that comprises many facets, including how to find an optimal operator placement strategy, how to estimate runtime costs across different hardware architectures, and how to manage the code and maintenance blowup caused by having to support multiple architectures. In prior work, we already discussed solutions to some of these problems: First, we showed that specifying operators in a hardware-oblivious way can prevent code blowup while still maintaining competitive performance when supporting multiple architectures. Second, we presented learning cost functions and several heuristics to efficiently place operators across all available devices. In this demonstration, we provide further insights into this line of work by presenting our combined system Ocelot/HyPE. Our system integrates a hardware-oblivious data processing engine with a learning query optimizer for placement decisions, resulting in a highly adaptive DBMS that is specifically tailored towards heterogeneous hardware environments.

In the recent past, the amount of high-dimensional data, such as feature vectors extracted from multimedia data, increased dramatically. A large variety of indexes have been proposed to store and access such data efficiently. However, due to specific requirements of a certain use case, choosing an adequate index structure is a complex and time-consuming task. This may be due to engineering challenges or open research questions. To overcome this limitation, we present QuEval, an open-source framework that can be flexibly extended w.r.t. index structures, distance metrics, and data sets. QuEval provides a unified environment for a sound evaluation of different indexes, for instance, to support tuning of indexes. In an empirical evaluation, we show how to apply our framework, motivate benefits, and demonstrate analysis possibilities.

The relationship between XML data clustering and schema matching is bidirectional. On one side, clustering techniques have been adopted to improve matching performance, and on the other side schema matching is the backbone of the clustering technique. This paper presents a new approach for clustering XML schema based on schema matching. In particular, we develop and implement an XML schema matching system, which determines semantic similarities between XML schemas based on the Prüfer sequence representation of schema trees. The proposed computation similarity algorithm makes use of the semantic meaning of XML elements as well as the hierarchical features of XML schemas. The computed similarities are then exploited by an agglomerative clustering algorithm to group similar schemas. Our experimental results show that the proposed approach is fast and accurate in clustering heterogeneous XML schemas.

In today's competitive business environment, enterprises businesses are subjected to continuously adapt change to ensure achieving targeted goals. As enterprise businesses are managed by enterprise information systems, adaptation to changes at information system level is important. It raises the need for architectures and mechanisms that support such adaptation at finer granularity. Rule-based information systems using service-oriented computing [1] and aspect-oriented [2] approach promises high adaptability in this domain. In this research we propose an adaptable ECA (Event-Condition-Action) centric architecture and implementation mechanism based on service-oriented computing and aspect-oriented programming for rule-based enterprise information systems ensuring high adaptability.

The general concept of grouping and aggregation appears to be a fitting paradigm for various issues in data integration, but in its common form of equality-based grouping, a number of problems remain unsolved. We propose a generic approach to user-defined grouping as part of a SQL extension, allowing for more complex functions, for instance integration of data mining algorithms. Furthermore, we discuss high-level language primitives for common applications.

New applications from the areas of analytical data processing and data integration require powerful features to condense and reconcile available data. As outlined in [1], the general concept of grouping and aggregation appears to be a fitting paradigm for a number of these issues, but in its common form of equality based groups or with current extensions like simple user-defined functions to derive group-by values on a per tuple basis and restricted aggregate functions a number of problems remain unsolved. We describe two extensions to the grouping mechanism, a generic one to support holistic user-defined grouping functions and higher level construct that provides similarity based grouping suitable in a number of applications like duplicate detection and elimination.

The transaction closure framework provides means to describe and reason about different kind of dependencies between interrelated transactions. In this paper, we investigate execution dependencies for describing certain control flows among related transactions of a transaction closure. In particular, we consider the transitivity property for all kinds of transaction execution dependencies and present a complete and minimal set of rules for reasoning about the transitivity of execution dependencies. Furthermore, we analyze the relationship between execution and termination dependencies and point out that some dependency combinations are incompatible. Using derived transitive dependencies, we are able to conclude how arbitrary transactions of a transaction closure are transitively interrelated and, thus, to detect contradictory dependency specifications as well as superfluous transactions.

Complex applications consist of a large set of transactions which are interrelated. There are different kinds of dependencies among transactions of a complex application, e.g. termination or execution dependencies which are constraints on the occurrence of significant transaction events. The authors analyze a set of (orthogonal) transaction dependencies. They do not follow traditional approaches which consider advanced transaction structures as a certain kind of nested transactions. They introduce the notion of transaction closure as a generalization of nested transactions. A transaction closure comprises all transactions which are (transitively) initiated by one (root) transaction. By specifying dependencies among transactions of a transaction closure they are then able to define well-known transaction structures like nested transactions as well as advanced activity structures, e.g. workflows, in a common framework. In particular they consider the transitivity property for all kinds of transaction dependencies discussed in the paper. Thus, they are able to conclude how two arbitrary transactions are transitively interrelated. This issue is fundamental for understanding the entire semantics of a complex application.

TROLL is a language particularly suited for the early stages of information system development, when the universe of discourse must be described. In TROLL the descriptions of the static and dynamic aspects of entities are integrated into object descriptions. Sublanguages for data terms, for first-order and temporal assertions, and for processes, are used to describe respectively the static properties, the behavior, and the evolution over time of objects. TROLL organizes system design through object-orientation and the support of abstractions such as classification, specialization, roles, and aggregation. Language features for state interactions and dependencies among components support the composition of the system from smaller modules, as does the facility of defining interfaces on top of object descriptions.

We propose an object-oriented logical formalism to conceptionally model applications in an interoperable environment. Such an environment consists of heterogeneous and autonomous local (database) systems. Applications in such an environment use several resources and services. Their conceptual modelling involves re-specification of existing systems in terms of homogeneous views, modelling of behavior and system dynamics, modelling of logically distributed components in an open environment and the modelling of communication relationships and dependencies between components. We introduce a formal object-oriented language capable of dealing with these requirements and illustrate its use to model applications in an interoperable environment.