vmointtDlerawteenilbeanzukmen\25d.esMGaIl- Afarnbdeitvsokmrei2se8s.5".Gbriusn3d1l.a5g.2en01v3ondeIrnfWoromrkasthioonpss"yGstreumnednl\agiemn Fachbereich Datenbanken und Informationssysteme (DBIS) statt. Nach O sterreich im Jahr 2011 und dem Spreewald im Jahr 2012 war bereits zum dritten Mal Thuringen der Austragungsort { diesmal die kleine Gemeinde Elgersburg am Fu e der Hohen Warte im Ilm-Kreis. Organisiert wurde der Workshop vom Fachgebiet Datenbanken und Informationssysteme der TU Ilmenau.
Die Workshop-Reihe, die 1989 in Volkse bei Braunschweig vom Braunschweiger Datenbanklehrstuhl ins Leben gerufen wurde und die ersten 3 Jahre auch in Volkse blieb, hat sich inzwischen als eine Institution fur den Gedankenaustausch gerade fur Nachwuchswissenschaftler/-innen aus dem deutschsprachigen Raum im Bereich Datenbanken und Informationssysteme etabliert. Langst sind dabei die Beschrankungen auf Deutsch als Vortragssprache und reine theorie- und grundlagenorientierte Themen gefallen { auch wenn die o ene Atmosphare an abgeschiedenen Tagungsorten (und Elgersburg stellte hier keine Ausnahme dar) mit viel Zeit fur intensive Diskussionen wahrend der Sitzungen und an den Abenden geblieben sind.
Fur den diesjahrigen Workshop wurden 15 Beitrage eingereicht und von jeweils drei Mitgliedern des 13-kop gen Programmkomitees begutachtet. Aus allen eingereichten Beitragen wurden 13 fur die Prasentation auf dem Workshop ausgewahlt. Die Bandbreite der Themen reichte dabei von fast schon klassischen Datenbankthemen wie Anfrageverarbeitung (mit XQuery), konzeptueller Modellierung (fur XML Schemaevolution), Indexstrukturen (fur Muster auf bewegten Objekten) und dem Au nden von Spaltenkorrelationen uber aktuelle Themen wie MapReduce und Cloud-Datenbanken bis hin zu Anwendungen im Bereich Image Retrieval, Informationsextraktion, Complex Event Processing sowie Sicherheitsaspekten.
Vervollstandigt wurde das viertagige Programm durch zwei Keynotes von namhaften Datenbankforschern: Theo Harder stellte das WattDB-Projekt eines energieproportionalen Datenbanksystems vor und Peter Boncz diskutierte die Herausforderungen an die Optimierung von Datenbanksysteme durch moderne Hardwarearchitekturen - untersetzt mit praktischen Vorfuhrungen. Beiden sei an dieser Stelle fur ihr Kommen und ihre interessanten Vortrage gedankt. In zwei weiteren Vortragen nutzten die Sponsoren des diesjahrigen Workshops, SAP AG und Objectivity Inc., die Gelegenheit, die Datenbanktechnologien hinter HANA (SAP AG) und In niteGraph (Objectivity Inc.) vorzustellen. Hannes Rauhe und Timo Wagner als Vortragenden mochten wir daher genauso wie den beiden Unternehmen fur die nanzielle Unterstutzung des Workshops und damit der Arbeit des GI-Arbeitskreises danken.
Gedankt sei an dieser Stelle auch allen, die an der Organisation und Durchfuhrung beteiligt waren: den Autoren fur ihre Beitrage und Vortrage, den Mitgliedern des Programmkomitees fur ihre konstruktive und punktliche Begutachtung der Einreichungen, den Mitarbeitern vom Hotel am Wald in Elgersburg, dem Leitungsgremium des Arbeitskreises in Person von Gunther Specht und Stefan Conrad, die es sich nicht nehmen lie en, personlich am Workshop teilzunehmen, sowie Eike Schallehn, der im Hintergrund mit Rat und Tat zur Seite stand. Der gro te Dank gilt aber meinem Fachgebietsteam, das den Gro teil der Organisationsarbeit geleistet hat: Stephan Baumann, Francis Gropengie er, Heiko Betz, Stefan Hagedorn und Felix Beier. Ohne ihr Engagement ware der Workshop nicht moglich gewesen. Herzlichen Dank!
Komitee Programm-Komitee
Andreas Heuer, Universitat Rostock Eike Schallehn, Universitat Magdeburg Erik Buchmann, Karlsruher Institut fur Technologie Friederike Klan, Universitat Jena Gunter Saake, Universitat Magdeburg Gunther Specht, Universitat Innsbruck Holger Schwarz, Universitat Stuttgart Ingo Schmitt, Brandenburgische Technische Universitat Cottbus Kai-Uwe Sattler, Technische Universitat Ilmenau Katja Hose, Aalborg University Klaus Meyer-Wegener, Universitat Erlangen Stefan Conrad, Universitat Dusseldorf
Torsten Grust, Universitat Tubingen Organisations-Komitee
Kai-Uwe Sattler, TU Ilmenau Stephan Baumann, TU Ilmenau Felix Beier, TU Ilmenau Heiko Betz, TU Ilmenau Francis Gropengie er, TU Ilmenau
Stefan Hagedorn, TU Ilmenau 3 WattDB—a Rocky Road to Energy Proportionality
Energy efficiency is becoming more important in database
design, i. e., the work delivered by a database server should
be accomplished by minimal energy consumption. So far, a
substantial number of research papers examined and
optimized the energy consumption of database servers or single
components. In this way, our first efforts were exclusively
focused on the use of flash memory or SSDs in a DBMS context
to identify their performance potential for typical DB
operations. In particular, we developed tailor-made algorithms to
support caching for flash-based databases [
A key observation made by Tsirogiannis et al. [
Because the energy use of single-server systems is far from being energy proportional, we came up with the hypothesis that better energy efficiency may be achieved by a cluster of nodes whose size is dynamically adjusted to the current workload demand. For this reason, we shifted our research focus from inflexible single-server DBMSs to distributed clusters running on lightweight nodes. Although distributed systems impose some performance degradation compared to a single, brawny server, they offer higher energy saving potential in turn.
Current hardware is not energy proportional, because a
single server consumes, even when idle, a substantial
fraction of its peak power [
We have developed a research prototype of a distributed DBMS called WattDB on a scale-out architecture, consisting of n wimpy computing nodes, interconnected by an 1GBit/s Ethernet switch. The cluster currently consists of 10 identical nodes, composed of an Intel Atom D510 CPU, 2 GB DRAM and an SSD. The configuration is considered Amdahl-balanced, i. e., balanced between I/O and network throughput on one hand and processing power on the other.
Compared to InfiniBand, the bandwidth of the interconnecting network is limited but sufficient to supply the lightweight nodes with data. More expensive, yet faster connections would have required more powerful processors and more sophisticated I/O subsystems. Such a design would have pushed the cost beyond limits, especially because we would not have been able to use commodity hardware. Furthermore, by choosing lightweight components, the overall energy footprint is low and the smallest configuration, i. e., the one with the fewest number of nodes, exhibits low power consumption. Moreover, experiments running on a small cluster can easily be repeated on a cluster with more powerful nodes.
A dedicated node is the master node, handling incoming queries and coordinating the cluster. Some of the nodes have each four hard disks attached and act as storage nodes, providing persistent data storage to the cluster. The remaining nodes (without hard disks drives) are called processing nodes. Due to the lack of directly accessible storage, they can only operate on data provided by other nodes (see Figure 1).
All nodes can evaluate (partial) query plans and execute DB operators, e. g., sorting, aggregation, etc., but only the storage nodes can access the DB storage structures, i. e., tables and indexes. Each storage node maintains a DB buffer
S S D
S S D
D
S S D S S D
Disk
D
Disk
S S D S S D S S D
Disk
to keep recently referenced pages in main memory, whereas a processing node does not cache intermediate results. As a consequence, each query needs to always fetch the qualified records from the corresponding storage nodes.
Hence, our cluster design results in a shared-nothing architecture where the nodes only differentiate to those which have or have not direct access to DB data on external storage. Each of the nodes is additionally equipped with a 128GB Solid-State Disk (Samsung 830 SSD). The SSDs do not store the DB data, they provide swap space to support external sorting and to provide persistent storage for configuration files. We have chosen SSDs, because their access latency is much lower compared to traditional hard disks; hence, they are better suited for temp storage.
In WattDB, a dedicated component, running on the master node, controls the energy consumption, called EnergyController. This component monitors the performance of all nodes in the cluster. Depending on the current query workload and node utilization, the EnergyController activates and suspends nodes to guarantee a sufficiently high node utilization depending on the workload demand. Suspended nodes do only consume a fraction of the idle power, but can be brought back online in a matter of a few seconds. It also modifies query plans to dynamically distribute the current workload on all running nodes thereby achieving balanced utilization of the active processing nodes.
As data-intensive workloads, we submit specific TPC-H queries against a distributed shared-nothing DBMS, where time and energy use are captured by specific monitoring and measurement devices. We configure various static clusters of varying sizes and show their influence on energy efficiency and performance. Further, using an EnergyController and a load-aware scheduler, we verify the hypothesis that energy proportionality for database management tasks can be well approximated by dynamic clusters of wimpy computing nodes.
Optimizing database architecture for machine architecture: is there still hope?
Extended Abstract In the keynote, I will give some examples of how computer architecture has strongly evolved in the past decennia and how this influences the performance, and therefore the design, of algorithms and data structure for data management.
One the one hand, these changes in hardware architecture have caused the (continuing) need for new data management research. i.e. hardware-conscious database research. Here, I will draw examples from hardware-conscious research performed on the CWI systems MonetDB and Vectorwise.
This diversification trend in computer architectural characteristics of the various solutions in the market seems to be intensifying. This is seen in quite different architectural options, such as CPU vs GPU vs FPGA, but also even restricting oneself to just CPUs there seems to be increasing design variation in architecture and platform behavior. This poses a challenge to hardware-conscious database research.
In particular, there is the all too present danger to overoptimize of one particular architecture; or to propose techniques that will have only a very short span of utility. The question thus is not only to find specific ways to optimize for certain hardware features, but do so in a way that works across the full spectrum of architectural, i.e. robust techniques.
I will close the talk by recent work at CWI and Vectorwise on robustness of query evaluator performance, describing a project called ”Micro-Adaptivity” where database systems are made self-adaptive and react immediately to observed performance, self-optimizing to the combination of current query workload, observed data distributions, and hardware characteristics.
Adaptive Prejoin Approach for Performance Optimization in MapReduce-based Warehouses
Heterogeneous Information
Systems Group University of Kaiserslautern qu@informatik.uni-kl.de
Department of Computer
Science University of Kaiserslautern m_rappol@cs.uni-kl.de ∗
Heterogeneous Information
Systems Group
University of Kaiserslautern dessloch@informatik.unikl.de ABSTRACT MapReduce-based warehousing solutions (e.g. Hive) for big data analytics with the capabilities of storing and analyzing high volume of both structured and unstructured data in a scalable file system have emerged recently. Their efficient data loading features enable a so-called near real-time warehousing solution in contrast to those offered by conventional data warehouses with complex, long-running ETL processes.
However, there are still many opportunities for performance improvements in MapReduce systems. The performance of analyzing structured data in them cannot cope with the one in traditional data warehouses. For example, join operations are generally regarded as a bottleneck of performing generic complex analytics over structured data with MapReduce jobs.
In this paper, we present one approach for improving performance in MapReduce-based warehouses by pre-joining frequently used dimension columns with fact table redundantly during data transfer and adapting queries to this joinfriendly schema automatically at runtime using a rewrite component. This approach is driven by the statistics information derived from previous executed workloads in terms of join operations.
The results show that the execution performance is improved by getting rid of join operations in a set of future workloads whose join exactly fits the pre-joined fact table schema while the performance still remains the same for other workloads. 1. INTRODUCTION
By packaging complex custom imperative programs (text mining, machine learning, etc.) into simple map and reduce functions and executing them in parallel on files in a large ∗finished his work during his master study at university of kaiserslautern
scalable file system, MapReduce/Hadoop1 systems enable analytics on large amounts of unstructured data or structured data in acceptable response time.
With the continuous growth of data, scalable data stores based on Hadoop/HDFS2 have achieved more and more attention for big data analytics. In addition, by means of simply pulling data into the file system of MapReduce-based systems, unstructured data without schema information is directly analyzed with parallelizable custom programs, whereas data can only be queried in traditional data warehouses after it has been loaded by ETL tools (cleansing, normalization, etc.), which normally takes a long period of time.
Consequently, many web or business companies add
MapReduce systems to their analytical architecture. For example,
Fatma O¨zcan et al. [
Another example is the data warehousing infrastructure at Facebook which involves a web-based tier, a federated MySQL tier and a Hadoop-based analytical cluster - Hive.
Such orchestration of various analytical platforms forms a heterogeneous environment where each platform has a different interface, data model, computational capability, storage system, etc.
Pursuing a global optimization in such a heterogeneous environment is always challenging, since it is generally hard to estimate the computational capability or operational cost concisely on each autonomous platform. The internal query engine and storage system do not tend to be exposed to outside and are not designed for data integration.
In our case, relational databases and Hadoop will be integrated together to deliver an analytical cluster. Simply transferring data from relational databases to Hadoop without considering the computational capabilities in Hadoop can lead to lower performance.
As an example, performing complex analytical workloads over multiple small/large tables (loaded from relational data1one open-source implementation of MapReduce framework from Apache community, see http://hadoop.apache.org 2Hadoop Distributed File System - is used to store the data in Hadoop for analysis 1. Adaptively pre-joining tables during data transfer for better performance in Hadoop/Hive.
2.2
Hive
bases) in Hadoop leads to a number of join operations which
slows down the whole processing. The reason is that the
join performance is normally weak in MapReduce systems
as compared to relational databases [
To achieve better global performance in such an analytical synthesis with multiple platforms from a global perspective of view, several strategies can be applied.
One would be simply improving the join implementation
on single MapReduce platform. There have been several
existing works trying to improve join performance in
MapReduce systems [
Another one would be using heuristics for global performance optimization. In this paper, we will take a look at the second one. In order to validate our general idea of improving global performance on multiple platforms, we deliver our adaptive approach in terms of join performance. We take the data flow architecture at Facebook as a starting point and the contributions are summarized as follows: 2. Rewriting incoming queries according to changing ta
ble schema.
The remainder of this paper is structured as follows: Section 2 describes the background of this paper. Section 3 gives a na¨ıve approach of fully pre-joining related tables. Based on the performance observation of this na¨ıve approach, more considerations have been taken into account and an adaptive pre-join approach is proposed in Section 4, followed by the implementation and experimental evaluation shown in Section 5. Section 6 shows some related works. Section 7 concludes with a summary and future work. 2. BACKGROUND
In this section, we will introduce our starting point, i.e. the analytical data flow architecture at Facebook and its MapReduce-based analytical platform - Hive. In addition, the performance issue in terms of join is also stated subsequently. 2.1
Facebook Data Flow Architecture
Instead of using a traditional data warehouse, Facebook uses Hive - a MapReduce-based analytical platform - to perform analytics on information describing advertisement.
The MapReduce/Hadoop system offers high scalability which
enables Facebook to perform data analytics over 15PB of
data and load 60TB of new data every day [
As depicted in Figure 1, data is extracted from two types of data sources: a federated MySQL tier and a web-based tier. The former offers the category, the name and corresponding information of the advertisements as dimension data while the actions such as viewing an advertisement, clicking on it, fanning a Facebook page are extracted as fact data from the latter.
There are two types of analytical cluster: production Hive cluster and ad hoc Hive cluster. Periodic queries are performed on the production Hive cluster while the ad hoc queries are executed on the ad hoc Hive cluster. the advertiser information etc. The data sets originating in the latter mostly correspond to actions such as viewing an advertisement, clicking on it, fanning a Facebook page etc. In traditional data warehousing terminology, more often than not the data in the
Web Servers
Scribe-Hadoop Clusters
Hive replication Adhoc Hive-Hadoop
Cluster
Production Hive-Hadoop
Cluster
Federated MySQL
Hive [
Hive supports a higher-level SQL-like language called HiveQL for users who are familiar with SQL for accessing files in Hadoop/HDFS, which highly increases the productivity of using MapReduce systems. When a HiveQL query comes in, it will be automatically translated into corresponding MapReduce jobs with the same analytical semantics. For this purpose, Hive has its own meta-data store which maps the HDFS files to the relational data model. Files are logically interpreted as relational tables during HiveQL query execution.
Furthermore, in contrast to high data loading cost (using ETL jobs) in traditional data warehouses, Hive benefits from its efficient loading process which pulls raw files directly into Hadoop/HDFS and further publishes them as tables. This feature makes Hive much more suitable for dealing with large volumes of data (i.e. big data).
Join in Hadoop/Hive
There has been an ongoing debate comparing parallel
database systems and MapReduce/Hadoop. In [
Moreover, as MapReduce was not originally designed to
combine information from two or more data sources, join
implementations are always cumbersome [
As Hive is built on top of MapReduce/Hadoop, the join
operation is essentially done by corresponding MapReduce
jobs. Thus, Hive suffers from these issues even though there
have been efforts [
1014
The data from t Hadoop clusters processes dump compressing the into the Hive-Ha failures and also much load on th running the scrap avoiding extra lo any notions of str order to avoid lo database server cannot be read e data from that pa servers, there are the scrapes and b data a daily du Hadoop clusters. tables.
As shown in Fig where the data stream processes Hadoop cluster strict delivery de Hive-Hadoop clu well as any ad h data sets. The ad run production jo 350 300 ) sce250 ( iem200 t n reu150 ga rve100 a 50 0 3. FULL PRE-JOIN APPROACH
Due to the fact that the join performance is a perfortmuarne,coenbeonttal¨ıevneetchki ninkiHngivfeorwiimthpritosviinnghetroetnatl wMoarpkRloeaWddeubpcSeeerrffveoearrs-- Scribe-HadoopCalustbersc d wmoarnkcleoawdobuyldpberefotromsiinmgpalyreewlimrititneantewtohrekljooaidn wtaitshk tfrhoemsatmhee fact table: λ analytical semantics over pre-joined tables created in the data load phase. A performance gain would be expected by performing large table scan with high parallelism of increasH-ive replication ing working nodes in Hadoop instead of join. In addition, Production Hive-Hadoop tphree-jsocianleadblteabstleosrafgoer ssoymsteemwoarlklolowasdsuswtitoh csrpeeaActdiehfiocrceHCjidlovuueisn-ntHedaprdaaonotpt- Cluster r s t As shown in Figure 1,x theyrtewzoardeifferent Hive-Hadoo terns. where the data becomes available for consumption b
In an experiment, we tried to validate this strategy. An dim table: α stream processes. Onedimoftatbhlee:sβe clusters ! the prod analytical workload (TPC-H Query 3) was executed over x y z Hstadroiocpt cdleulsitveerry-dieasdulisendest,owehoexbersecutahesattjhneeeodthteor acdlhues two data sets of TPC-H benchmark (with scale factor 5 & Hive-Hadoop cluster is used toteexleocwuer priority ba 10) of the original table schema (with join at runtime) and a Federated MySQL dim table: βdwaetlal saestsa.nyThaed ahdochoacnanlaytsuiursseetrohfaqtuetrhieesusmearkseswaintt dtao fully pre-joined table schema (without join) which fullyFjiogiunres 1: Data Flow Architecture run production jobs in the same cluster. A badly w all the related dimension tables with the fact table during Figure 3: Adaptive Pre-joined Schema in Facebook the load phase, respectively. In this case, we trade storage Example overhead for better total performance. 1014
As shown on the left side of the Figure 2(a), the performance gain of the total workload (including the join) over the data set with SF 5 can be seen with 6GB storage overhead introduced by fully pre-joining the related tables into one redundant table (shown in Figure 2(b)). The overall the periodic queries on production Hive-Hadoop cluster, a frequent column set could be extracted.
One example is illustrated in Figure 3. The frequent set of additional columns has been extracted. The column r in dimension table α is frequently joined with fact table in company in the previous workloads as a filter or aggregate column, as the same for the column x in dimension table β. During next load phase, the fact table is expanded by redundantly pre-joining these two additional columns r and x with it.
Depending on the statistics information of previous queries, different frequent sets of additional columns could be found in diverse time intervals. Thus, the fact table is pre-joined in an adaptive manner.
Assume that the additional columns identified in previous queries will also frequently occur in the future ones (as in the Facebook example), the benefits of adaptive pre-join approach are two-fold:
First, when all the columns (including dimension columns) in a certain incoming query which requires a join operation have been contained in the pre-joined fact table, this query could be directly performed on the pre-joined fact table without join.
Second, the adaptive pre-join approach leads to a smaller table size in contrast to the full pre-join approach, as only subsets of the dimension tables are pre-joined. Thus, the resulting storage overhead is reduced, which plays a significant role especially in big data scenarios (i.e. terabytes, petabytes of data).
To automatically accomplish the adaptive pre-join approach, three sub-steps are developed: frequent column set extraction, pre-join and query rewrite. 4.1 Frequent Column Set Extraction
In the first phase, the statistics collected for extracting frequent set of additional columns is formated as a list of entries each which has the following form: Set : {Fact, Dim X.Col i, Dim X.Col j ... Dim Y.Col k}
The join set always starts with the involved fact table while the joint dimension columns are identified and capno pre-join ful pre-join 5GB
10GB data set size (a) Average Runtimes 5GB
10GB data set size (b) Accessed Data Volume performance can be significantly increased if workloads with the same join pattern later frequently occur, especially for periodic queries over production Hive-Hadoop cluster in the Facebook example.
However, the result of performing the same query on the data set with SF 10 size is disappointing as there is no performance gain while paying 12.5GB storage for redundancy (shown in Figure 2(b)), which is not what we expected. The reason could be that the overhead of scanning such redundant fully pre-joined tables and the high I/O cost as well offset the performance gain as the accessed data volume grows. 4. ADAPTIVE PRE-JOIN APPROACH
Taking the lessons learned from the full pre-join approach above, we propose an adaptive pre-join approach in this paper.
Instead of pre-joining full dimension tables with the fact table, we try to identify the dimension columns which occurred frequently in the select, where, etc. clauses of previous executed queries for filtering, aggregation and so on. We refer to these columns as additional columns as compared to the join columns in the join predicates. By collecting a list of additional column sets from previous queries, for example, tured from the select, where, etc. clauses or from the subqueries.
The frequent set of additional columns could be extracted
using a set of frequent itemset mining approaches [
Query Rewrite
As the table schema is changed in our case (i.e. newly generated fact table schema), initial queries need to be rewritten for successful execution. Since the fact table is pre-joined with a set of dedicated redundant dimension columns, the tables which are involved in the from clause of the original query can be replaced with this new fact table once all the columns have been covered in it.
By storing the mapping from newly generated fact table schema to the old schema in the catalog, the query rewrite process can be easily applied. Note that the common issue of handling complex sub-queries for Hive can thereby be facilitated if the columns in the sub-query have been prejoined with the fact table. 5. IMPLEMENTATION AND EVALUATION
We use Sqoop3 as the basis to implement our approach.
The TPC-H benchmark data set with SF 10 is adaptively pre-joined according to the workload statistics and transferred from MySQL to Hive. First, the extracted join pattern information is sent to Sqoop as additional transformation logic embedded in the data transfer jobs for generating the adaptive pre-joined table schema on the original data sources. Furthermore, the generated schema is stored in Hive to enable automatic query rewrite at runtime.
We tested the adaptive pre-join approach on a six-node cluster (Xeon Quadcore CPU at 2.53GHz, 4GB RAM, 1TB SATA-II disk, Gigabit Ethernet) running Hadoop and Hive.
After running the same TPC-H Query 3 over the adaptive pre-joined table schema, the result in the Figure 4(a) shows that the average runtime is significantly reduced. The join )25 BG (s lrkadoo20 iftrcxgeun15 w e10 eo m luo 5 tvaad 0 nopre-join ful pre-join adaptivepre-join task has been eliminated for this query and the additional overheads (record parsing, I/O cost) have been relieved due to the smaller size of redundancy as shown in Figure 4(b).
RELATED WORK
An adaptively pre-joined fact table is essentially a
materialized view in Hive. Creating materialized views in data
warehouses is nothing new but a technique used for query
optimization. Since 1990s, a substantial effort [
Cheetah [
CONCLUSION AND FUTURE WORK
We propose a schema adaption approach for global optimization in an analytical synthesis of relational databases and a MapReduce-based warehouse - Hive. As MapReduce systems have weak join performance, frequently used columns of dimension tables are pre-joined with the fact table according to useful workload statistics in an adaptive manner before being transfered to Hive. Besides, a rewrite component enables the execution of incoming workloads with join operations over such pre-joined tables transparently. In this way, better performance can be achieved in Hive. Note that this approach is not restricted to any specific platform like Hive. Any MapReduce-based warehouse can benefit from it, as generic complex join operations occur in almost every analytical platform.
However, the experimental results also show that the performance improvement is not stable while the data volume grows continuously. For example, when the query is executed on one larger pre-joined table, the performance gain from eliminating joins is offset by the impact caused by the record parsing overhead and high I/O cost during the scan, which results in worse performance. This concludes that the total performance of complex data analytics is effected by multiple metrics rather than a unique consideration, e.g. join.
With the continuous growth of data, diverse frameworks and platforms (e.g. Hive, Pig) are built for large-scale data analytics and business intelligent applications. Data transfer between different platforms generally takes place in the absence of key information such as operational cost model, resource consumption, computational capability etc. within platforms which are autonomous and inherently not designed for data integration. Therefore, we are looking at a generic description of the operational semantics with their computational capabilities on different platforms and a cost model for performance optimization from a global perspective of view. The granularity we are observing is a single operator in the execution engines. Thus, a global operator model with generic cost model is expected for performance improvement in several use cases, e.g. federated systems.
Moreover, as an adaptively pre-joined fact table is
regarded as a materialized view in a MapReduce-based
warehouse, another open problem left is how to handle the view
maintanence issue. The work from [
Ein Cloud-basiertes räumliches Decision Support System für die Herausforderungen der Energiewende
Hochschule Regensburg golo.klossek @stud.hs-regensburg.de
Hochschule Regensburg stefanie.scherzinger @hs-regensburg.de
Hochschule Regensburg
michael.sterner @hs-regensburg.de KURZFASSUNG Die Energiewende in Deutschland wirft sehr konkrete Fragestellungen auf: Welche Standorte eignen sich fu¨r Windkraftwerke, wo ko¨nnen Solaranlagen wirtschaftlich betrieben werden? Dahinter verbergen sich rechenintensive Datenverarbeitungsschritte, auszufu¨hren auf Big Data aus mehreren Datenquellen, in entsprechend heterogenen Formaten. Diese Arbeit stellt exemplarisch eine konkrete Fragestellung und ihre Beantwortung als MapReduce Algorithmus vor. Wir konzipieren eine geeignete, Cluster-basierte Infrastruktur fu¨r ein neues Spatial Decision Support System und legen die Notwendigkeit einer deklarativen, doma¨nenspezifischen Anfragesprache dar.
Allgemeine Begriffe Measurement, Performance, Languages.
Stichworte Cloud-Computing, MapReduce, Energiewende.
EINLEITUNG
Der Beschluss der Bundesregierung, zum Jahr 2022 aus
der Kernenergie auszusteigen und deren Anteil am
StromMix durch erneuerbare Energien zu ersetzen, fordert einen
rasanten Ausbau der erneuerbaren Energien. Entscheidend
fu¨r den Bau neuer Windkraft- und Solaranlagen sind vor
allem die zu erzielenden Gewinne und die Sicherheit der
Investitionen. Somit sind pra¨zise Ertragsprognosen von großer
Bedeutung. Unterschiedliche Standorte sind zu vergleichen,
die Ausrichtung der Windkraftanlagen zueinander in den
Windparks ist sorgfa¨ltig zu planen. Als
Entscheidungsgrundlage dienen hierzu vor allem historische Wetterdaten. Fu¨r
die Kalkulation des Ertrags von Windkraftanlagen muss
effizient auf die Datenbasis zugegriffen werden ko¨nnen. Diese
erstreckt sich u¨ber große Zeitra¨ume, da das
Windaufkommen nicht nur ja¨hrlich schwankt, sondern auch dekadenweise
variiert [
Die Standortfindung etwa fu¨r Bankfilialen und die
Zonierung, also das Ausweisen geographischer Fla¨chen fu¨r die
Landwirtschaft, sind klassische Fragestellungen fu¨r
ra¨umliche Entscheidungsunterstu¨tzungssysteme [
Die Herausforderungen an solch ein Spatial Decision Support System im Kontext der Energiewende sind vielfa¨ltig: 1. Verarbeitung heterogener Datenformate.
Wir begru¨nden kurz die Eckpunkte dieses Anforderungsprofils im Einzelnen. Dabei vertreten wir den Standpunkt, dass existierende Entscheidungsunterstu¨tzungssysteme auf Basis relationaler Datenbanken diese nicht in allen Punkten erfu¨llen ko¨nnen.
(1) Historische Wetterdaten sind zum Teil o¨ffentlich
zuga¨nglich, werden aber auch von kommerziellen Anbietern
bezogen. Prominente Vertreter sind das National Center for
Atmospheric Research [
Die Vielzahl der Quellen und somit der Formate fu¨hren zu den klassischen Problemen der Datenintegration.
(2) Daten in hoher zeitlicher Auflo¨sung, die u¨ber
Jahrzehnte hinweg erhoben werden, verursachen
Datenvolumina im Big Data Bereich. Der Deutsche Wetterdienst allein
verwaltet ein Datenarchiv von 5 Petabyte [
(3) Wir stellen die Infrastruktur fu¨r ein interdisziplina¨res Team der Regensburg School of Energy and Resources mit mehreren im Aufbau befindlichen Projekten bereit. Um den wachsenden Anforderungen unserer Nutzer gerecht werden zu ko¨nnen, muss das System elastisch auf neue Datenquellen und neue Nutzergruppen angepasst werden ko¨nnen.
(4) Unsere Nutzer sind u¨berwiegend IT-affin, doch nicht erfahren in der Entwicklung komplexer verteilter Systeme.
Mit einer doma¨nenspezifischen Anfragesprache wollen die Autoren dieses Artikels die intuitive Nutzbarkeit des Systems gewa¨hrleisten.
Unter diesen Gesichtspunkten konzipieren wir unser
System als Hadoop-Rechencluster [
Struktur. Die folgenden Kapitel liefern Details zu unserem Vorhaben. In Kapitel 2 beschreiben wir eine konkrete Fragestellung bei der Standortfindung von Windkraftwerken. In Kapitel 3 stellen wir unsere Lo¨sung als MapReduce Algorithmus dar. Kapitel 4 skizziert unsere Infrastruktur. Im 6. Kapitel wird auf verwandte Arbeiten eingegangen. Das letzte Kapitel gibt eine Zusammenfassung unserer Arbeit und zeigt deren Perspektive auf.
WINDPOTENTIALANALYSE
Ein aktuelles Forschungsprojekt der Hochschule Regensburg bescha¨ftigt sich mit der Potentialanalyse von Windkraftanlagen. Hier werden die wirtschaftlichen Aspekte, die fu¨r das Errichten neuer Windkraftanlagen entscheidend sind, untersucht. Mithilfe der prognostizierten Volllaststunden einer Windkraftanlage kann eine Aussage u¨ber die Rentabilita¨t getroffen werden. Diese ist bestimmt durch die Leistungskennlinie der Windkraftanlage und letztlich durch die zu erwartenden Windgeschwindigkeiten.
Abbildung 1 (aus [
I) Erst ab einer gewissen Windgeschwindigkeit beginnt
die Anlage Strom zu produzieren.
II) Die Leistung steigt u¨ber den wichtigsten Arbeitsbereich in der dritten Potenz zur Windgeschwindigkeit an, bis die Nennleistung der Anlage erreicht ist.
III) Die Ausgangsleistung wird auf die Nennleistung der
Anlage begrenzt. Ausschlaggebend fu¨r die Ho¨he der
Nennleistung ist die Auslegungsgro¨ße des Generators.
IV) Die Windkraftanlage schaltet sich bei zu hohen Windgeschwindigkeiten ab, um eine mechanische U¨ berbelastung zu verhindern.
Wie Abbildung 1 verdeutlicht, ist zum Errechnen der abgegeben Arbeit einer Windkraftanlage eine genaue Kenntnis der stochastischen Verteilung der Windgeschwindigkeit 1 notwendig. Mithilfe entsprechender Histogramme ko¨nnen somit potentielle Standorte fu¨r neue Windkraftanlagen verglichen, und Anlagen mit geeigneter Leistungskennlinie passend fu¨r den spezifischen Standort ausgewa¨hlt werden.
Als Datenbasis eignen sich etwa die Wetterdaten des
Forschungsinstitut des National Center for Atmospheric
Research [
Insbesondere im Binnenland ist eine hohe ra¨umliche Auflo¨sung der meteorologischen Daten wichtig. Aufgrund der 1Wir verwenden die Begriffe Windgeschwindigkeit und Windsta¨rke synonym. Streng genommen wird die Windgeschwindigkeit als Vektor dargestellt, wa¨hrend die Windsta¨rke als skalare Gro¨ße erfasst wird. Dabei kann die Windsta¨rke aus der Windgeschwindigkeit errechnet werden.
Abbildung 1: Aussagen u¨ber die Leistung in
Abh¨angigkeit zur Windgeschwindigkeit (aus [
Abbildung 2: Histogramme u¨ber die Windst¨arkeverteilung.
Orographie variieren die Windgeschwindigkeiten schon bei kurzen Distanzen stark.
Abbildung 2 skizziert die resultierende Aufgabenstellung: Geographische Fla¨chen werden kleinra¨umig unterteilt, was die Abbildung aus Gru¨nden der Anschaulichkeit stark vereinfacht darstellt. Fu¨r jeden Quadranten, bestimmt durch La¨ngen- und Breitengrad, interessiert die Ha¨ufigkeitsverteilung der Windsta¨rken (dargestellt als Histogramm).
Je nach Fragestellung wird von unterschiedlichen Zeitra¨umen und unterschiedlicher Granularita¨t der Quadranten ausgegangen. Aufgrund der schieren Gro¨ße der Datenbasis ist hier ein massiv paralleler Rechenansatz gefordert, wenn u¨ber eine Vielzahl von Quadranten hinweg Histogramme berechnet werden sollen.
Views Access Control Data Valuation
Encryption
Raw Data Backup
Data Encryption
DBMS Level
Physical Level
Backup employee-table, where each tuple has a value for attributes "first name", "surname" and "gender". In this case, it is also quite easy to calculate the monetary value for a query (r(Remp)) by simply summarizing all mval per attribute and multiply those with the number of involved rows (see Eq. (3)).
mval(r(Remp)) = mval(Ai) ∗ | r(Remp)|
(3)
X
Ai∈ Remp However, it becomes more challenging if an additional attribute "license plate number" is added, which does have some unset or unknown attribute values - in most cases NULL values. By knowing there is a NULL value for a certain record, this could be interpreted as either simply unknown whether there is any car or unset because this person has no car. So there is an uncertainty that could lead to an information gain which would be uncovered if no adequate valuation exists. Some other potentially implicit information gains are originated from joins and aggregate functions which we do mention in the regarding section.
Because the terms information gain and information loss are widely used and do not have a uniform definition, we do define them for further use. We call a situation where an attacker received new data (resp. information) information gain and the same situation in the view of the data owner an information loss.
Uncertainty Factor Some operators used for query processing obviously reduce the information content of the result set (e.g. selection, aggregations, semi joins, joins with resulting NULL values), but there is still an uncertain, implicit information gain.
Since, the information gain by uncertainty is blurry, meaning in some cases more indicative than in others, we have to distinguish uncertainty of one attribute value generated out of one source attribute value (e.g., generated NULL values) and attribute values which are derived from information of several source attribute values (e.g., aggregations).
In case of one source attribute value, an information gain by uncertainty has to be less valuable than properly set attribute values. Therefore, the monetary value should be only a percentage of the respective monetary value of an attribute value. If several source attribute values are involved, we recommend to value the computed attribute value as a percentage of the monetary value of all participating source attribute values. In general, we suggest a maximum of 50% for both valuations. Furthermore, we need to consider the overall purpose of our leakage-resistant data valuation which shall prevent extractions of large amounts of data. Therefore, the percentage needs to be increased with the amount of data, but not in a way that an unset or unknown attribute value becomes equivalent valuable than a properly set one.
For that reason, exponential growth is not a suitable option.
Additionally, we have to focus a certain area of application, because a trillion attributes (1012) are conceivable whereas a septillion attributes (1024) are currently not realistic. From the overall view on our data valuation, we assume depending on the application, that the extraction of sensitive data becomes critical when 103 up to 109 attribute values will be extracted. Therefore, the growth of our uncertainty factor UF increases much more until 109 attribute values than afterwards, which predominantly points to a logarithmic growth.
We also do not need to have a huge difference of the factor if theoretically much more attribute values shall be extracted (e.g., 1014 and more), because with respect to an extraction limiting approach, it is way too much data to return. This assumption does also refer to a logarithmic increase. We conclude that the most promising formula that was adapted to fit our needs is shown in Eq. (4).
U F = 1 30 log10(| valAi,...,Ak | + 1)
(4)
In this chapter we will describe valuation derivation for main database operations by first discussing core relational operations. Furthermore, we address specifics of join operations and finally functions (aggregate, user-defined, stored procedures) which are defined in SQL. 3.1
Core Operations of Relational Algebra
The relational algebra [
Projection The projection π attr_list(r(R)) is a unary operation and eliminates all attributes (columns) of an input relation r(R) except those mentioned in the attribute list. For computation of the monetary value of such a projection, only mval for chosen attributes of the input relation are considered while taking into account that a projection may eliminate According to the relational algebra, a selection of a certain relation σ predr(R) reduces tuples to a subset which satisfy specified predicates. Because theselection reduces the number of tuples, the calculation of the monetary value does not have to consider those filtered tuples and only the number of present tuples are relevant (shown in Eq. (6)).
mval(σ pred(r(R))) = mval(t ∈ r(R)) ∗ | σ pred(r(R))|
(6) Set Union A relation of all distinct elements (resp. tuples) of any two relations is called the union (denoted by ∪ ) of those relations. For performing set union, the two involved relations must be union-compatible – they must have the same set of attributes. In symbols, the union is represented as R1 ∪ R2 = { x : x ∈ R1 ∨ x ∈ R2} . However, if two relations contain identical tuples, within a resulting relation these tuples do only exist once, meaning duplicates are eliminated. Accordingly, the mval of a union of two relations is computed by adding mval of both relations, subtracted with mval of duplicates (shown in Eq. (7)).
mval(R1 ∪ R2) = mval(r(R1))+ mval(r(R2)) − X mval(ti ∈ r(R1 ∩ R2)
(7) i Set Difference The difference of relations R1 and R2 is the relation that contains all the tuples that are in R1, but do not belong to R2. The set difference is denoted by R1 − R2 or R1\R2 and defined by R1\R2 = { x : x ∈ R1 ∧ x ∈ / R2} . Also, the set difference is union-compatible, meaning the relations must have the same number of attributes and the domain of each attribute is the same in both R1 and R2. The mval of a set difference of two relations is computed by subtracting the mval of tuples that have both relations in common from the monetary value of R1 given by Equation (8).
mval(R1\R2) = mval(r(R1) − X mval(ti ∈ r(R1 ∩ R2) i
(8)
Cartesian Product
The Cartesian product, also known as cross product, is an
operator which works on two relations, just as set union
and set difference. However, the Cartesian product is the
costliest operator to evaluate [
mval(r(R1 × R2)) = mval(t ∈ r(R1)) ∗ | r(R1)| + mval(t ∈ r(R2)) ∗ | r(R2)|
(9)
In the context of relational databases, a join is a binary operation of two tables (resp. data sources). The result set of a join is an association of tuples from one table with tuples from another table by concatenating concerned attributes.
Joining is an important operation and most often performance critical to certain queries that target tables whose relationships to each other cannot be followed directly. Because the type of join affects the number of resulting tuples and their attributes, the monetary value of each join needs to be calculated independently. An inner join produces a result table containing composite rows of involved tables that match some pre-defined, or explicitly specified, join condition. This join condition can be any simple or compound search condition, but does not have to contain a subquery reference. The valuation of an inner join is computed by the sum of the monetary values of all attributes of a composite row multiplied by the number of rows within the result set. Because the join attribute Ajoin of two joined tables has to be counted only once, we need to subtract it (shown in Eq. (10)).
mval(r(R1 ./ R 2) = | r(R1 ./ R 2)| ∗ (mval(t ∈ r(R1)) + (mval(t ∈ r(R2)) − mval(Ajoin))
(10) An outer join does not require matching records for each tuple of concerned tables. The joined result table retains all rows from at least one of the tables mentioned in the FROM clause, as long as those rows are consistent with the search condition. Outer joins are subdivided further into left, right, and full outer joins. The result set of a left outer join (or left join) includes all rows of the first mentioned table (left of the join keyword) merged with attribute values of the right table where the join attribute matches. In case there is no match, attributes of the right table are set to NULL. The right outer join (or right join) will return rows that have data in the right table, even if there’s no matching rows in the left table enhanced by atteributes (with NULL values) of the left table. A full outer join is used to retain the non-matching information of all affected tables by including non-matching rows in the result set. To cumulate the monetary value for a query that contains a left or right outer join, we only need to compute the monetary value of an inner join of both tables and add the mval of an antijoin r(R1 . R 2) ⊆ r(R1) which includes only tuples of R1 that do not have a join partner in R2(shown in Eq. (11)). For the monetary value of a full outer join, we additionally would consider an antijoin r(R2 . R 1) ⊆ r(R2) which includes tuples of R2 that do not have a join partner given by Equation (12)).
mval(r(R1 1 R2)) = mval(r(R1 ./ R 2))+
mval(r(R1 . R 2)) mval(r(R1 1 R2)) = mval(r(R1 ./ R 2))+ mval(r(R1 . R 2)) + mval(r(R2 . R 1)) (11) (12) Semi Join A semi join is similar to the inner join, but with the addition that only attributes of one relation are represented in the result set. Semi joins are subdivided further into left and right semi joins. The left semi join operator returns each row from the first input relation (left of the join keyword) when there is a matching row in the second input relation (right of the join keyword). The right semi join is computed vice versa. The monetary value for a query that uses semi joins can be easily cumulated by multiplying the sum of monetary values for included attributes with number of matching rows of the outgoing relation (shown in Eq. (13)).
mval(r(R1 n R2)) =
mval(Ai) ∗ | r(R1 n R2)| (13) X
Ai∈ R1 Nevertheless, we do have an information gain by knowing join attributes of R1 have some join partners within R2 which are not considered. But adding our uncertainty factor UF in this equation would lead to inconsistency by cumulating the mval of a semi join compared to the mval of a combination of a natural join and a projection. In future work, we will solve this issue by presenting a calculation that is based on a combination of projections and joins to cover such an implicit information gain. 3.3
In computer science, an aggregate function is a function where the values of multiple rows are grouped together as input on certain criteria to form a single value of more significant meaning. The SQL aggregate functions are useful when mathematical operations must be performed on all or on a group of values. For that reason, they are frequently used with the GROUP BY clause within a SELECT statement. According to the SQL standard, the following aggregate function are implemented in most DBMS and the ones used most often: COUNT, AVG, SUM, MAX, and MIN.
All aggregate functions are deterministic, i.e. they return
the same value any time they are called by using the same
set of input values. SQL aggregate functions return a
single value, calculated from values within one column of a
arbitrary relation [
To be able to compute the monetary value of a derived, aggregated attribute, we need to consider two more factors.
First of all, we divided aggregate function into two groups: informative and conservative.
1. Informative are those aggregate functions where the aggregated value of a certain aggregate function leads to an information gain of the entire input of all attribute values. This means that every single attribute value participates in the computation of the aggregated attribute value. Representatives for informative aggregate functions are COUNT, AVG and SUM. 2. Conservative, on the contrary, are those functions where the aggregated value is represented by only one attribute value, but in consideration of all other attribute values. So if the aggregated value are again separated from the input set, all other attribute values will remain. Conservative aggregate functions are MAX and
MIN.
The second factor that needs to be considered is the number of attributes that are used to compute the aggregated values. In case of a conservative aggregate function, it is simple, because only one attribute value is part of the output. For that reason we recommend to leave the mval of the source attribute unchanged (shown in Eq. (14)).
mval(Ai) = mval(M AX(Ai)) = mval(M IN (Ai)) (14)
For the informative aggregate functions the computation is more challenging due to several participating attribute values. Because several input attribute values are concerned, we recommend the usage of our uncertainty factor which we already mentioned in a prior section. With the uncertainty factor it is possible to integrate the number of attribute values in a way that a higher number of concerned attributes leads to an increase in percentage terms of the monetary value of the aggregated attribute value given by Equation (15).
mval(COU N T (Ai)) = mval(SU M (Ai)) =
1 mval(AV G(Ai)) = 30 log10(| Ai| + 1) ∗ mval(Ai)
(15)
Besides the SQL aggregate functions, which return a single value, calculated from values in a column, there are also scalar functions defined in SQL, that return a single value based on the input value. The possibly most commonly used and well known scalar functions are: • UCASE() - Converts a field to upper case • LCASE() - Converts a field to lower case • LEN() - Returns the length of a text field • ROUND() - Rounds a number to a specified degree • FORMAT() - Formats how a field is to be displayed
Returned values of this scalar functions are always derived from one source attribute value, and some of them do not even change the main content of the attribute value. Therefore, we recommend that the monetary value of the source attribute stays untouched.
User-Defined Functions
User-defined functions (UDF ) are subroutines made up of one or several SQL or programming extension statements that can be used to encapsulate code for reuse. Most database management systems (DBMS) allow users to create their own user-defined functions and do not limit them to the built-in functions of their SQL programming language (e.g., TSQL, PL/SQL, etc.). User-defined functions in most systems are created by using the CREATE FUNCTION statement and other users than the owner must be granted appropriate permissions on a function before they can use it.
Furthermore, UDFs can be either deterministic or nondeterministic. A deterministic function always returns the same results if the input is the equal and a nondeterministic function returns different results every time it is called.
On the basis of the multiple possibilities offered by most DBMS, it is impossible to estimate all feasible results of a UDF. Also, due to several features like shrinking, concatenating, and encrypting of return values, a valuation of a single or an array of output values is practically impossible.
For this reason we decided not to calculate the monetary value depending on the output of a UDF, much more we do consider the attribute values that are passed to an UDF (shown in Eq. (16)). This assumption is also the most reliable, because it does not matter what happens inside an UDF – like a black box – the information loss after inserting cannot get worse.
mval(U DFoutput(Aa, .., Ag)) =
p mval(U DFinput(Ak, .., Ap)) = X mval(Ai)
(16) i=k 3.6
Stored procedures (SP) are stored similar to user-defined
functions (UDF ) within a database system. The major
difference is that stored procedures have to be called and the
return values of UDFs are used in other SQL statements in
the same way pre-installed functions are used (e.g., LEN,
ROUND, etc.). A stored procedure, which is depending on
the DBMS also called proc, sproc, StoredProc or SP, is a
group of SQL statements compiled into a single execution
plan [
Because stored procedures have such a complex structure, nesting is also legitimate and SPs are "only" a group of SQL statements, we recommend to value each single statement within a SP and sum up all partial results (shown in Eq. (17). With this assumption we do follow the principal that single SQL statements are moved into stored procedures to provide a simple access for applications which only need to call the procedures.
k mval(SP (r(Rj), .., r(Rk))) = X mval(r(Ri))
(17) i=j
Furthermore, by summing all partial result, we make sure that the worst case of information loss is considered, entirely in line with our general idea of a leakage resistant data valuation that should prevent a massive data extraction. However, since SPs represent a completed unit, by reaching the truncate threshold the whole SP will be blocked and rolled back. For that reason, we recommend smaller SPs resp. split existing SPs in DBS with an enabled leakage resistant data valuation.
RELATED WORK
Conventional database management systems mostly use access control models to face unauthorized access on data.
However, these are insufficient when an authorized
individual extracts data regardless whether she is the owner or
has stolen that account. Several methods were conceived to
eliminate those weaknesses. We refer to Park and Giordano
[
Authorization views partially achieve those crucial goals of
an extended access control and have been proposed several
times. For example, Rizvi et al. [
Contrary to this, we do not prohibit a query in its entirety.
Another approach based on views was introduced by Motro
[
In contrast, the monetary values of attributes are set while
defining the tables and the user can query the tables or views
she is used to. Moreover, the equivalence test of general
relational queries is undecidable and equivalence for
conjunctive queries is known to be NP complete [
However, none of these methods does consider the sensitivity level of data that is extracted by an authorized user.
In the field of privacy-preserving data publishing (PPDP),
on the contrary, several methods are provided for publishing
useful information while preserving data privacy. In detail,
multiple security-related measures (e.g., k-anonymity [
To the best of our knowledge, there is only the approach of
Harel et al. ([
Harel et al. introduce the Misuseability Weight (M-score) that desribes the sensitivity level of the data exposed to the user. Hence, Harel et al. focus on the protection of the quality of information, whereas our approach predominantly preserves the extraction of a collection of data (quantity of information). Harel et al. also do not consider extractions over time, logging of malicious requester and the backup process. In addition, mapping attributes to a certain monetary value is much more applicable and intuitive, than mapping to a artificial M-score.
Our extended authorization control does not limit the system to a simple query-authorization control without any protection against the insider threat, rather we allow a query to be executed whenever the information carried by the query is legitimate according to the specified authorizations and thresholds.
CONCLUSIONS AND FUTURE WORK
In this paper we described conceptual background details for a novel approach for database security. The key contribution is to derive valuations for query results by considering the most important operations of the relational algebra as well as SQL and providing specific mval functions for each of them. While some of these rules are straight forward, e.g. for core operations like selection and projection, other operations like specific join operations require some more thorough considerations. Further operations, e.g. grouping and aggregation or user-defined function, would actually require application specific valuations. To minimize the overhead for using valuation-based security, we discuss and recommend some reasonable valuation functions for these cases, too.
As the results presented here merely are of conceptual nature, our current and future research includes considering implementation alternatives, e.g. integrated with a given DBMS or as part of a middleware or driver as well as evaluating the overhead and the effectiveness of the approach.
We will also come up with a detailed recommendation of how to set monetary values appropriate to different environments and situations. Furthermore, we plan to investigate further possible use cases for data valuation, such as billing of data-providing services on a fine-grained level and controlling benefit/cost trade-offs for data security and safety.
ACKNOWLEDGMENTS
This research has been funded in part by the German Federal Ministry of Education and Science (BMBF) through the Research Program under Contract FKZ: 13N10818.
TrIMPI: A Data Structure for Efficient Pattern Matching on
Moving Objects
Tsvetelin Polomski Christian-Albrechts-University at Kiel
Hermann-Rodewald-Straße 3
24118 Kiel tpo@is.informatik.uni-kiel.de ABSTRACT Managing movement data efficiently often requires the exploitation of some indexing scheme. Taking into account the kind of queries issued to the given data, several indexing structures have been proposed which focus on spatial, temporal or spatio-temporal data. Since all these approaches consider only raw data of moving objects, they may be well-suited if the queries of interest contain concrete trajectories or spatial regions. However, if the query consists only of a qualitative description of a trajectory, e.g. by stating some properties of the underlying object, sequential scans on the whole trajectory data are necessary to compute the property, even if an indexing structure is available.
The present paper presents some results of an ongoing work on a data structure for Trajectory Indexing using Motion Property Information (TrIMPI). The proposed approach is flexible since it allows the user to define application-specific properties of trajectories which have to be used for indexing. Thereby, we show how to efficiently answer queries given in terms of such qualitative descriptions. Since the index structure is built on top of ordinary data structures, it can be implemented in arbitrary database management systems.
Keywords Moving object databases, motion patterns, indexing structures
Most index structures for trajectories considered in the literature
(e.g. [
Copyright is held by the author/owner(s).
Hans-Joachim Klein Christian-Albrechts-University at Kiel
Hermann-Rodewald-Straße 3
24118 Kiel
hjk@is.informatik.uni-kiel.de
qualitative description, e.g. return all trajectories where the
underlying object slowed down (during any time interval) and after that
it changed its course. Obviously, the motion properties slowdown
and course alteration as well as their temporal adjustment can be
computed using formal methods. The crucial point is that, even if
an indexing structure is used, the stated properties must be
computed for each trajectory and this results in sequential scan(s) on
the whole trajectory data. Time consuming processing of queries
is not acceptable, however, in a scenario where fast reaction on
incoming data streams is needed. An example of such a situation with
so-called tracks computed from radar and sonar data as input is the
detection of patterns of skiff movements typical for many piracy
attacks [
To address the efficiency problem, we propose an indexing scheme which is not primarily focused on the “time-position data” of trajectories but uses meta information about them instead.
We start with a discussion of related work in Section 2. Section 3 provides some formal definitions on trajectories and their motion properties. In section 4 we introduce the indexing scheme itself and illustrate algorithms for querying it. Section 5 summarizes the present work and outlines our future work.
RELATED WORK
In this section we provide a short overview on previous contributions which are related to our approach. We start the section by reviewing classical indexing structures for moving objects data.
Next to this, we show an approach which is similar in general terms to the proposed one and finally we review literature related to semantical aspects of moving objects.
Indexing of Spatial, Temporal and Spatio
Temporal Data
The moving object databases community has developed several
data structures for indexing movement data. According to [
Several extensions of R-Trees have been provided over the years,
thus yielding a variety of spatio-temporal index structures. An
informal schematic overview on these extensions, including also new
developments as the HTPR*-Tree [
Applying Dimensionality Reduction upon
Indexing - the GEMINI Approach
The overall approach we consider in this work is similar to the
GEMINI (GEneric Multimedia INdexIng method) indexing scheme
presented in [
In the mentioned approaches, the authors achieve encouraging results on querying most similar trajectories (or time series) to a given one. However, since the representatives of the original data are trajectories or time series, respectively, evaluating a query which only describes a motion behavior would result in the inspection of all representatives. 2.3
Semantical Properties of Movement
Semantical properties of movement data have been considered in
various works, e.g. in [
The authors of [
In [
In [
This section provides the formal notions as well as the definitions needed throughout the rest of the paper. We start with the term trajectory and then direct later our attention to motion properties and patterns. 3.1
Trajectories
In our approach we consider the trajectory τo of an object o simply as a function of time which assigns a position to o at any point in time. Since time plays only a role for the determination of temporal causality between the positions of an object, we abstract from “real time” and use any time domain instead. A time domain is any set which is interval scaled and countably infinite. The first requirement ensures that timestamps can be used for ordering and, furthermore, that the “delay” between two time assignments can be determined. The second requirement ensures that we have an infinite number of “time moments” which can be unambiguously indexed by elements of N. In the following we denote a time domain by T.
Since objects move in a space, we also need a notion for a spatial domain. In the following, let S denote the spatial domain. We require that S is equipped with an adequate metric, such as the Euclidean distance (e.g. for S = R × R), which allows us to measure the spatial distance between objects.
Having the notions of time and space we can define formally the term trajectory.
Definition 1. Let T, S and O denote a time domain, a space domain and a set of distinct objects, respectively. Then, the trajectory τo of an object o ∈ O is a function τo : T → S.
For brevity, we can also write the trajectory of an object o ∈ O in the form (o, t0, s0), (o, t1, s1) . . . for those t ∈ T where τo(t) = s is defined. A single element (o, ti, si) is called the track of object o at time ti.
We consider a motion pattern as a sequence of properties of trajectories which reveal some characteristics of the behavior of the underlying moving objects. Such properties may be expressed through any predicates which are important for the particular analysis, such as start, stop, turn, or speedup.
Definition 2. Let T be a time domain, T be the set of trajectories of an object set O over T, and IT be the set of all closed intervals over T. A motion property on T is a function p : 2T × IT → { true, f alse} .
That is, a motion property is fulfilled for a set of trajectories and a certain time interval if the appropriate predicate is satisfied. To illustrate this definition, some examples of motion properties are provided below: • Appearance: Let t ∈ T. Then we define appear(· , · ) as follows: appear({ τo} , [t, t]) = true ⇔ ∀t′ ∈ T : τo(t′) , undefined → t ≤ t′. That is, an object “appears” only in the “first” moment it is being observed. • Speedup: Let t1, t2 ∈ T and t1 < t2. Then speedup(· , · ) is defined as follows: speedup({ τo} , [t1, t2]) = true ⇔ v(τo, t1) < v(τo, t2) ∧ ∀t ∈ T : t1 ≤ t ≤ t2 → v(τo, t1) ≤ v(τo, t) ≤ v(τo, t2) where v(τo, t) denotes the velocity of the underlying moving object o at time t. That is, the predicate speedup is satisfied for a trajectory and a time interval if and only if the velocity of the underlying object is increasing in the considered time interval. Note that the increase may not be strictly monotonic.
Using motion properties, a motion pattern of a single trajectory or a set of trajectories is defined as a sequence of motion properties ordered by the time intervals in which they are fulfilled. It is important to note, that this common definition of a motion pattern allows multiple occurrences of the same motion property in the sequence.
In order to get a well-defined notion it has to be required that the time intervals in which the motion properties are fulfilled are disjoint or that meaningful preferences on the motion properties are specified in order to allow ordering in case the time intervals overlap.
In this section we explain how the proposed index is being created and used. Index creation starts with the determination of the motion pattern of each trajectory to be indexed. For this purpose, the motion predicates specified by the user are computed. The resulting motion patterns are indexed with references to the original trajectories.
The resulting index is schematically depicted in Figure 1. TrIMPI consists mainly of a data structure holding the raw trajectory data, and secondary index structures for maintaining motion patterns.
Thereby, we differentiate between indexing single motion properties and indexing motion patterns.
A query to the index can be stated either through a motion pattern or through a concrete trajectory. The index is searched for motion patterns containing the given one or the computed one, respectively. In both cases, the associated trajectories are returned. The following subsections consider the outlined procedures more precisely. 4.1
Indexing Trajectory Raw Data
Since the focus of TrIMPI is not on querying trajectories by
example, the index structure for the raw trajectory data can be rather
simple. For our implementation, we considered a trajectory record
file as proposed by [
IDo next_ ptr prev_ptr
{ track0, . . . , tracknum−1} .
IDo denotes the identifier of the underlying moving object, next_ ptr and prev_ptr are references to the appropriate records holding further parts of the trajectory, and { track0, . . . , tracknum−1} is a list of tracks of a predefined fixed length num. If a record ri for a trajectory τo gets filled, a new record r j is created for τo holding its further tracks. In this case, next_ ptrri is set up to point to r j, and prev_ ptrrj is set up to point to ri.
Using a trajectory record file, the data is not completely clustered, but choosing appropriate record size leads to partial clustering of the trajectory data in blocks. This has the advantage that extracting the complete trajectory requires only loading as much blocks as needed for storing a trajectory.
For the maintenance of motion patterns we consider two cases
single motion properties and sequences of motion properties.
Storing single motion properties allows the efficient finding of
trajectories which contain the considered motion property. This is
advantageous if the searched property is not often satisfied. Thus, for
each motion property p a “list” DBT p holding all trajectories
satisfying this property is maintained. As we shall see in Algorithm
4.3, we have to combine such lists and, thus, a simple unsorted list
would not be very favourable. Therefore, we implement these lists
through B+-Trees (ordered by the trajectory/object identifiers). An
evaluation of union and intersection of two B+-Trees with m and n
leaves can be performed in O(m log mm+n )[
The search for motion patterns with more than one motion property can be conducted through the single DBT p structures. However, if the query motion pattern is too long, too many intersections of the DBT p structures will happen and the resulting trajectories will have to be checked for containing properties that match the given order, as well. To overcome this problem, sequences of motion properties are stored in an additional B+-Tree structure DBT . The elements of DBT have the form (p, τo) where p is a motion pattern, and o ∈ O.
To sort the elements of DBT , we apply lexicographical ordering.
As a result, sequences with the same prefix are stored consecutively. Thus, storing of motion patterns that are prefixes of other motion patterns can be omitted. 4.3
Building the Index
The algorithm for the index creation is quite simple. It consists
primarily of the following steps:
• Determine the motion properties for each trajectory τo.
Consider, if needed, a sliding window or some reduction or
segmenting technique as proposed in [
for indexing. • For each generated access key, check whether it is already contained in the index. If this is not the case, store it in the index. Link the trajectory record file entry of τo to the access key.
Algorithm 4.1 is used to generate index keys of a pattern. An index key is any subpattern p′ = (p′j) mj=−01 of a pattern p = (pi)in=−01 which is defined as follows: • For each j ≤ m − 1 exists i ≤ n − 1 such that p′j = pi • For each j, k such that 0 ≤ j < k ≤ m − 1 exist i, l such that
0 ≤ i < l ≤ n − 1 and p′j = pi and p′k = pl.
To generate the list of index keys, algorithm 4.1 proceeds iteratively. At each iteration of the outer loop (lines 3 to 16) the algorithm considers a single element p of the input sequence f . On the one hand, p is being added as an index key to the (interim) result (lines 14 and 15) and on the other hand it is being appended as a suffix to each previously generated index key (inner loop - lines 5 to 13). Algorithm 4.1 utilizes two sets whose elements are lists of motion properties - supplist and entries. The set supplist contains at each iteration the complete set of index keys, including those which are prefixes of other patterns. The set entries is built in each iteration of the inner loop (lines 5 to 13) by appending the current motion property of the input sequence to any element of supplist. Thereby, at line 14 entries holds only index keys which are no prefixes of other index keys. Since the resulting lists of index keys are stored in a B+-Tree by applying a lexicographical order, sequences of motion properties which are prefixes of other sequences can be omitted. Therefore, the set entries is returned as final result (line 17).
Since the given procedure may result in the computation of up to 2k0 different indexing keys for an input sequence with k0 motion properties, a global constant G is used to limit the maximal length of index keys. Using an appropriate value for G leads to no drawbacks for the application. Furthermore, the proposed querying algorithm can handle queries longer than G.
Algorithm 4.1 Building the indexing keys Require: f is a sequence of motion properties Require: G is the maximal length of sequences to be indexed 1 function createIndexKeys( f ) 2 supplist ← empty set of lists 3 for all a ∈ f do 4 entries ← empty set of lists 5 for all l ∈ supplist do 6 new ← empty list 7 if | l| ≤ G then 8 new ← l.append(a) 9 else 10 new ← l 11 end if 12 entries ← entries ∪ { new} 13 end for 14 entries ← entries ∪ { [a]} 15 supplist ← entries ∪ supplist 16 end for 17 return entries 18 end function 4.4
Searching for Motion Patterns
Since the index is primarily considered to support queries on sequences of motion properties, the appropriate algorithm for evaluating such queries given in the following is rather simple. In its “basic” version, query processing is just traversing the index and returning all trajectories referenced by index keys which contain the queried one (as a subpattern). This procedure is illustrated in algorithm 4.2. There are, however, some special cases which have to Algorithm 4.2 Basic querying of trajectories with a sequence of motion properties Require: s is a sequence of motion properties; | s| ≤ G Require: DBT is the index containing motion patterns 1 function GetEntriesFromDBT(s) 2 result ← { τo | ∃ p s.t. s ≤ p ∧ (p, τo) ∈ DBT } 3 return result 4 end function be taken into account. The first of them considers query sequences which are “too short”. As stated in Section 4.2, it can be advantageous to evaluate queries containing only few motion properties by examination of the index structures for single motion properties. To be able to define an application specific notion of “short” queries, we provide besides G an additional global parameter α for which holds 1 ≤ α < G. In algorithm 4.3, which evaluates queries of patterns of arbitrary length, each pattern of length shorter than α is being handled in the described way (lines 3 to 8). It is important that each trajectory of the interim result has to be checked whether it matches the queried pattern (lines 9 to 13).
The other special case are queries longer than G (lines 16 to 24). As we have seen in algorithm 4.1, in such cases the index keys are cut to prefixes of length G. Thus, the extraction in this case considers the prefix of length G of the query sequence (lines 17) and extracts the appropriate trajectories (line 18). Since these trajectories may still not match the query sequence, e.g. by not fulfilling some of the properties appearing on a position after G − 1 in the input sequence, an additional check of the trajectories in the interim result is made (lines 19 to 23).
The last case to consider are query sequences with length between α and G. In these cases, the index DBT holding the index keys is searched through a call to algorithm 4.2 and the result is returned.
Finally, the function Match (algorithm 4.4) checks whether a traAlgorithm 4.3 Querying trajectories with a sequence of arbitrary length Require: s is a sequence of motion properties Require: G is the maximal length of stored sequences Require: DBTp is the index of the property p Require: 1 ≤ α < G maximal query length for searching single property indexes 1 function GetEntries(s) 2 result ← empty set 3 if | s| < α then 4 result ← T 5 for all p ∈ s do 6 suppset ← DBTp 7 result ← result ∩ suppset 8 end for 9 for all τo ∈ result do 10 if ! match(τo, s) then 11 result ← result\{ τo} 12 end if 13 end for 14 else if | s| ≤ G then 15 result ← GetEntriesFromDBT (s) 16 else 17 k ← s[0..G − 1] 18 result ← GetEntriesFromDBT (k) 19 for all τo ∈ result do 20 if ! match(τo, s) then 21 result ← result\{ τo} 22 end if 23 end for 24 end if 25 return result 26 end function jectory τo fulfills a pattern s. For this purpose, the list of motion properties of τo is being generated (line 2). Thereafter, s and the generated pattern of τo are traversed (lines 5 to 14) so that it can be checked whether the elements of s can be found in the trajectory pattern of τo in the same order. In this case the function Match returns true, otherwise it returns false.
CONCLUSIONS AND OUTLOOK
In this paper we provided some first results of an ongoing work on an indexing structure for trajectories of moving objects called TrIMPI. The focus of TrIMPI lies not on indexing spatio-temporal data but on the exploitation of motion properties of moving objects.
For this purpose, we provided a formal notion of motion properties and showed how they form a motion pattern. Furthermore, we showed how these motion patterns can be used to build a meta index. Algorithms for querying the index were also provided. In the next steps, we will finalize the implementation of TrIMPI and perform tests in the scenario of the automatic detection of piracy attacks mentioned in the Introduction. As a conceptual improvement of the work provided in this paper, we consider a flexibilisation of Algorithm 4.4 Checks whether a trajectory matches a motion pattern Require: τo is a valid trajectory Require: s is a sequence of motion properties 1 function match(τo, s) 2 motion_properties ← compute the list of motion properties of τo 3 index_s ← 0 4 index_props ← 0 5 while index_props < motion_properties.length do 6 if motion_properties[index_props] = s[index_s] then 7 index_s ← index_s + 1 8 else 9 index_props ← index_props + 1 10 end if 11 if index_s = s.length then 12 return true 13 end if 14 end while 15 return false 16 end function the definition of motion patterns including arbitrary temporal relations between motion predicates.
ACKNOWLEDGMENTS
The authors would like to give special thanks to their former student Lasse Stehnken for his help in implementing TrIMPI.
Complex Event Processing in Wireless Sensor Networks
Faculty of Computer Science and Automation
Ilmenau University of Technology
Ilmenau, Germany omran.saleh@tu-ilmenau.de ABSTRACT Most of the WSN applications need the number of sensor nodes deployed to be in order of hundreds, thousands or more to monitor certain phenomena and capture measurements over a long period of time. The large volume of sensor networks would generate continuous streams of raw events1 in case of centralized architecture, in which the sensor data captured by all the sensor nodes is sent to a central entity.
In this paper, we describe the design and implementation of a system that carries out complex event detection queries inside wireless sensor nodes. These queries filter and remove undesirable events. They can detect complex events and meaningful information by combining raw events with logical and temporal relationship, and output this information to external monitoring application for further analysis.
This system reduces the amount of data that needs to be sent to the central entity by avoiding transmitting the raw data outside the network. Therefore, it can dramatically reduce the communication burden between nodes and improve the lifetime of sensor networks.
We have implemented our approach for the TinyOS Operating System, for the TelosB and Mica2 platforms. We conducted a performance evaluation of our method comparing it with a naive method. Results clearly conrfim the effectiveness of our approach.
Keywords Complex Event Processing, Wireless Sensor Networks, Innetwork processing, centralized processing, Non-deterministic Finite state Automata 1. INTRODUCTION
Wireless sensor networks are denfied as a distributed and cooperative network of devices, denoted as sensor nodes that are densely deployed over a region especially in harsh environments to gather data for some phenomena in this mon1The terms data, events and tuples are used interchangeably. itored region. These nodes can sense the surrounding environment and share the information with their neighboring nodes. They are gaining adoption on an increasing scale for tracking and monitoring purposes. Furthermore, sensor nodes are often used in control purposes. They are capable of performing simple processing.
In the near future, it is prospective that wireless sensor networks will offer and make conceivable a wide range of applications and emerge as an important area of computing. WSN technology is exciting with boundless potential for various application areas. They are now found in many industrial and civilian application areas, military and security applications, environmental monitoring, disaster prevention and health care applications, etc.
One of the most important issues in the design of WSNs
is energy efficiency. Each node should be as energy
efficient as possible. Processing a chunk of information is less
costly than wireless communication; the ratio between them
is commonly supposed to be much smaller than one [
There is a signicfiant link between energy efficiency and superfluous data. The sensor node is going to consume unnecessary energy for the transmission of superfluous data to the central entity, which means minimizing the energy efficiency.
Furthermore, traditional WSN software systems do not apparently aim at efficient processing of continuous data or event streams. According to previous notions, we are looking for an approach that makes our system gains high performance and power saving via preventing the generation and transmission of needless data to the central entity. Therefore, it can dramatically reduce the communication burden between nodes and improve the lifetime of sensor networks.
This approach takes into account the resource limitations in terms of computation power, memory, and communication.
Sensor nodes can employ their processing capabilities to perform some computations. Therefore, an in-network complex event processing 2 based solution is proposed.
We have proposed to run a complex event processing
engine inside the sensor nodes. CEP engine is implemented
to transform the raw data into meaningful and benecfiial
events that are to be notified to the users after detecting
them. It is responsible for combining primitive events to
identify higher level complex events. This engine provides
an efficient Non-deterministic Finite state Automata (NFA)
[
Complex event processing over data stream has
increasingly become an important field due to the increasing
number of its applications for wireless sensor networks. There
have been various event detection applications proposed in
the WSNs, e.g. for detecting eruptions of volcanoes [
An increasing number of applications in such networks is confronted with the necessity to process voluminous data streams in real time fashion.
The rest of the paper is organized as follows: section 2 provides an overview of the naive approaches for normal data and complex event processing in WSNs. Related works are brieyfl reviewed in section 3. Then we introduce the overall system architecture in order to perform complex event processing in sensor networks in section 4. Section 5 discusses how to create logical query plans to evaluate sensor portion queries. Section 6 explains our approach and how queries are implemented by automata. In section 7, the performance of our system is evaluated using a particular simulator. Finally, section 8 presents our concluding remarks and future works.
NAIVE APPROACHES IN WSNS
The ideas behind naive approaches which are denfiitely different from our approach lie in the processing of data as the central architectural concept. For normal sensor data processing, the centralized approach proceeds in two steps; the sensor data captured by all the sensor nodes is sent to the sink node and then routed to the central server (base station) where it is stored in centralized database. High volume data are arriving at the server. Subsequently, query processing takes place on this database by running queries against stored data. Each query executes one time and returns a set of results.
Another approach which adopts the idea of centralized
architecture is the use of a central data stream management
system (DSMS), which simply takes the sensor data stream
as input source. Sending all sensor readings to DSMS is also
an option for WSN data processing. DSMS is denfied as a
system that manages a data stream, executes a continuous
query against a data stream and supports on-line analysis
of rapidly changing data streams [
The naive approach for Complex Event Processing in
WSNs is similar to the central architectural idea of normal
data processing, but instead of using traditional database
and data stream engine, CEP uses a dedicated engine for
processing complex events such as Esper [
Reference [
RELATED WORKS
It is preferable to perform In-Network Processing
inside sensor network to reduce the transmission cost between
neighboring nodes. This concept is proposed by several
systems such as TinyDB [
TinyDB is an acquisitional query processing system for sensor networks which maintains a single, innfiitely-long virtual database table. It uses an SQL-like interface to ask for data from the network. In this system, users specify the data they want and the rate at which the data should be refreshed, and the underlying system would decide the best plan to be executed. Several in-network aggregation techniques have been proposed in order to extend the life time of sensor network such as tree-based aggregation protocols i.e., directed diffusion.
Paper [
In [
Obviously, there is currently little work into how the idea of in-network processing can be extended and implemented to allow more complex event queries to be resolved within the network. 4. SYSTEM ARCHITECTURE
We have proposed a system architecture in which collected data at numerous, inexpensive sensor nodes are processed locally. The resulting information is transmitted to larger, more capable and more expensive nodes for further analysis and processing through specicfi node called sink node.
The architecture has three main parts that need to be modified or created to make our system better suited to queries over sensor nodes: 1- Server side: queries will be originated at server side and then forwarded to the nearest sink node. Additionally, this side mainly contains an application that runs on the user’s PC (base station). Its main purpose is to collect the results stream over the sensor network and display them. Server side application can offer more functions i.e., further filtering for the collected data, perform joining on sensor data, extract, save, manage, and search the semantic information and apply further complex event processing on incoming events after processing them locally in sensor nodes. Because sensor data can be considered as a data stream, we proposed to use a data stream management system to play a role of server side, for that we selected AnduIN data stream engine. 2- Sink side: sink node (also known as root or gateway node) is one of the motes in the network which communicates with the base station directly, all the data collected by sensors is forwarded to a sink node and then to server side. This node will be in charge of disseminating the query down to all the sensor nodes in the network that comes from server side. 3- Node side: in this side, we have made huge changes to the traditional application which runs on the nodes themselves to enable database manner queries involving filters, aggregates, complex event processing operator (engine) and other operators to be slightly executed within sensor networks. These changes are done in order to reduce communication costs and get useful information instead of raw data.
When combining on-sensor portions of the query with the server side query, most of the pieces of the sensor data query are in place. This makes our system more advanced.
Each and every sensor node of a network generates tuples. Every tuple may consist of information about the node id, and sensor readings. Query plan can specify the tuples oflw between all necessary operators and a precise computation plan for each sensor node. Figure 1 (lower plan) illustrates how our query plan can be employed. It corresponds to an acyclic directed graph of operators. We assume the dataoflw being upward. At the bottom, there is a homogeneous data source which generates data tuples that must be processed by operators belonging to query plans. Tuples are flowed through intermediate operators composed in the query graph. The operators perform the actual processing and eventually forward the data to the sink operator for transmitting the resulting information to the server side (base station). These operators adopt publish/subscribe mechanism to transfer tuples from one operator to next operator.
We differ between three different types of operators within
a query graph [
A query plan consists of one source at the bottom of a logical query graph, several inner operators, and one sink at the top and the tuples are flowing strictly upward. In our system, we have extended this plan to give the system the capability to perform the complex event processing and detecting by adding new operators. We have separated the mechanism for detecting complex events from the rest of normal processing side. We have a particular component working as an extra operator or engine within the main process, as we can see from figure 1 (upper plan). The detection mechanism takes as input primitive events from lower operators and detects occurrences of composite events which are used as an output to the rest of the system. 6. IN-NETWORK CEP SYSTEM
Various applications including WSNs require the ability to handle complex events among apparently unrelated events and find interesting and/or special patterns. Users want to be notiefid immediately as soon as these complex events are detected. Sensor node devices generate massive sensor data streams. These streams generate a variety of primitive events continuously. The continuous events form a sequence of primitive events, and recognition of the sequence supplies us a high level event, which the users are interested in.
Sensor event streams have to be automatically filtered, processed, and transformed into significative information.
In non-centralized architecture, CEP has to be performed as close to real time as possible (inside the node). The task of identifying composite events from primitive ones is performed by the Complex Event Processing engine. CEP engine provides the runtime to perform complex event processing where they accept queries provided by the user, match those queries against continuous event streams, and trigger an event or an execution when the conditions speciefid in the queries have been satisefid. The idea of this concept is close to Event-Condition-Action (ECA) concept in conventional database systems where an action has to be carried out in response to an event and one or more conditions are satisefid.
Each data tuple from the sensor node is viewed as a primitive event and it has to be processed inside the node. We have proposed an event detection system that specicfially targets applications with limited resources, such in our system. There are four phases for complex event processing in our in-network model: NFA creation, Filtering, Sequence scan and Response as shown in figure 2. 6.1
The first phase is NFA creation. NFA’s structure is created by the translation from the sequence pattern through mapping the events to NFA states and edges, where the conditions of the events (generally called event types) are associated with edges. For pattern matching over sensor node streams, NFA is employed to represent the structure of an event sequence. For a concrete example, consider the query pattern: SEQ(A a, B+ b, C c)3. Figure 3 shows the NFA created for the aforementioned pattern (A, B+, C), where state S0 is the starting state, state S1 is for the successful detection of an A event, state S2 is for the detection of a B event after event A, also state S3 is for the detection of a C event after the B event. State S1 contains a self-loop with the condition of a B event. State S3 is the accepting state, reaching this state indicates that the sequence is detected. 6.2
The second phase is to filter primitive events at early stage, generated by sensor nodes. Sensor nodes cannot understand whether a particular event is necessary or not.
When additional conditions are added to the system, possible event instances might be pruned at the first stage.
After filtering, timestamp operator will add the occurrence time of the event t. A new operator is designed for adding a timestamp t to the events (tuples) before entering the complex event processing operator. We can notice that from figure 1. The timestamp attribute value of an event t records the reading of a clock in the system in which the event was created, in this case it can reeflct the true order of the occurrences of primitive events. 6.3
The third phase is sequence scan to detect a pattern match.
We have three modes state the way in which events may contribute to scan a sequence: UNRESTRICTED, RECENT and FIRST. Every mode has a different behavior. The selection between them depends on the users and the application domain. These modes have advantages and disadvantages.
We will illustrate them below.
In the UNRESTRICTED mode, each start event e, which allows a sequence to move from the initial state to the next state, starts a separate sequence detection. In this case any event occurrence combination that matches the denfiition of the sequence can be considered as an output. By using this mode, we can get all the possibilities of event combination which satisfy the sequence. When the sequence is created, it 3Notice: In this paper, we are going to only focus on sequence operator SEQ because of the limited number of pages. is waiting for the arrival of events in its starting state. Once a new instance event e arrives, the sequence scan responds as follows: 1- It checks whether the type of instance (from attributes) and occurrence time of e satisfy a transition for one of the logical existing sequences. If not, the event is directly rejected. 2- If yes, e is registered in the system (the registration is done in the sliding window) and the sequence advances to next state. 3- If e allows for a sequence to move from the starting state to next state, the engine will create other logical sequence to process further incoming events while keeping the original sequence in its current state to receive new event. Therefore, multiple sequences work on the events at the same time. 4- Delete some sequences when their last received items are not within a time limit. It becomes impossible for them to proceed to the next state since the time limits for future transitions have already expired.
Next, we use an example to illustrate how UNRESTRICTED sequence scan works. Suppose we have the following pattern4 SEQ (A, B+, D) and sequence of events (tuples) presented as [a1, b2, a3, c4, c5, b6, d7 ...] within 6 time unit. Figure 4 shows, step by step, how the aforementioned events are processed. Once the sequence has reached the accepting state (F ), the occurrences of SEQ (A, B+, D) will be established at : { a1, b2, d7 } , { a1, b6, d7 } , { a3, b6, d7 } .
The drawback of this mode is the use of high storage to accumulate all the events that participate in the combinations in addition to computation overhead for the detection.
It consumes more energy. On other hand, it gives us all the possibilities of event combination which can be used (e.g. for further analysis). In our system, we only output one of these possibilities to reduce transmission cost overhead. All registered events are stored in a sliding window. Once the overoflw has occurred, the candidate events would be the newest registered ones from the first sequence. The engine will continue to replace the events from the first sequence as long as there is no space. When the initial event (rfist event in the first sequence combination) is replaced, the engine starts the replacement from the second sequence and so on.
The engine applies this replacement policy to ensure that the system still has several sequences to detect a composite event, because replacing the initial events would destroy the 4The terms complex event, composite event, pattern and sequence are used interchangeably. whole sequence.
In the FIRST mode, the earliest occurrence of each contributing event type is used to form the composite event output. Only the first event from a group of events which have the same type advances the sequence to the next state.
In this mode, we have just one sequence in the system. The automaton engine will examine every incoming instance e, whether the type of it and occurrence time of e satisfy a transition from the current state to next state. If it is, the sequence will register the event in the current state and advance to next state. If not, the event is directly rejected.
Suppose we have the following pattern SEQ (A, B+, C+, D) and sequence of tuples presented as [a1, a2, b3, c4, c5, b6, d7 ...] within 6 time unit. The result as shown in the upper part of figure 5 .
In the RECENT mode (as the lower part of figure 5 which has FIRST pattern and the same sequence of tuples), the most recent event occurrences of contributing event types are used to form the composite event. In RECENT mode, once an instance satisefis the condition and timing constraint to jump from a state to next state, the engine will stay in the current state unlike FIRST mode. This mode tries to nfid the most recent instance from consecutive instances for that state before moving to next state. When a1 enters the engine. It satisefis the condition to move from S0 to S1.
The engine registers it, stays in S0 and does not jump to the next state. Perhaps the new incoming instance is more recent from the last one in the current state.
The advantages of FIRST and RECENT modes are the use of less storage to accumulate all the events that participate in the combinations. Only a few events will be registered in the system in addition to low computation overhead for the detection. They consume less energy. Unlike UNRESTRICTED, they do not give all possible matches. 6.4
Once an accepting state F is reached by the engine, the engine should immediately output the event sequence. This phase is responsible for preparing the output sequence to pass it to the sink operator. The output sequence depends on the mode of the scan. This phase will start to create the response by reading the sliding window contents. In case of FIRST and RECENT modes, the sliding window contains only the events which contribute in sequence detection. In UNRESTRICTED mode, the engine randomly selects a combination of events which matches the pattern in order to reduce transmission cost.
We have completed an initial in-network complex event processing implementation. All the source code, implement
Figure 6: Total Energy Consumption ing the in-network complex event processing techniques as well as base station functionality, is written in TinyOS. Our code runs successfully on both real motes and the TinyOS Avrora simulator. The aim of the proposed work is to compare the performance of our system, in-network processor which includes complex event engine in comparison with centralized approach in wireless sensor networks and to assess the suitability of our approach in an environment where resources are limited. The comparison would be done in terms of energy efficiency (amount of energy consumed) and the number of messages transmitted per particular interval, in the entire network. The experiment was run for varying the SEQ length. We started with length 2 then 3 and finally 5. Simulations were run for 60 seconds with one event per second. The performance for different SEQ lengths and different modes with a network of 75 nodes is shown in figure 6.
The centralized architecture led to higher energy consumption because sensor nodes transmitted events to the sink node at regular periods. In our system, we used in-network complex event processing to decrease the number of transmissions of needless events at each sensor node. What we can notice from figure 6 is summarized as: 1- By increasing the SEQ length in our approach, the RAM size is increased while energy consumption is reduced. The reason is: the transmission will not occur until the sequence reaches the accepting state, few events (tuples) will be relatively satisfied. Hence, the number of transmissions after detections will be decreased. 2- FIRST is a little bit better than RECENT, and both of them are better than UNRESTRICTED in energy consumption. The gap between them is resulting from processing energy consumption, that is because UNRESTRICTED needs more processing power while the other needs less, as shown in figure 6.
Figure 7 shows the radio energy consumption for each sensor node and the total number of messages when SEQ length was 3. The nodes in the centralized architecture sent more messages than our approach (nearly three times more).
Hence, it consumed more radio energy. Additionally, the gateway nodes consumed more radio energy due to receiving and processing the messages from other sensor nodes.
In a 25 nodes network, the centralized approach consumed energy nearly 4203mJ in sink side, while our approach consumed around 2811mJ. Thus, our system conserved nearly 1392mJ (33% of the centralized approach) of the energy. In our architecture, the number of transmissions was reduced.
Therefore, the radio energy consumption is reduced not only at the sensor nodes but also at the sink nodes.
CONCLUSIONS
Sensor networks provide a considerably challenging programming and computing environment. They require advanced paradigms for software design, due to their characteristics such as limited computational power, limited memory and battery power which WSNs suffer from. In this paper, we presented our system, an in-network complex event processing, a system that efficiently carries out complex event queries inside network nodes.
We have proposed an engine to allow the system to detect complex events and valuable information from primitive events.
We developed a query plan based approach to implement the system. We provided the architecture to collect the events from sensor network, this architecture includes three sides; sensor side to perform in-network complex event processing, sink side to deliver the events from the network to AnduIN server side which has the responsibility to display them and perform further analysis.
We demonstrated the effectiveness of our system in a detailed performance study. Results obtained from a comparison between centralized approach and our approach conrfims that our in-network complex event processing in small-scale and large-scale sensor networks has shown to increase the lifetime of the network. We plan to continue our research to build distributed in-network complex event processing, in which each sensor node has a different complex event processing plan and can communicate directly between them to detect complex events.
REFERENCES
XQuery processing over NoSQL stores
University of Kaiserslautern
P.O. Box 3049 67653 Kaiserslautern,
Germany valer@cs.uni-kl.de
University of Kaiserslautern
P.O. Box 3049 67653 Kaiserslautern,
Germany csauer@cs.uni-kl.de
University of Kaiserslautern
P.O. Box 3049 67653 Kaiserslautern,
Germany haerder@cs.uni-kl.de ABSTRACT Using NoSQL stores as storage layer for the execution of declarative query processing using XQuery provides a highlevel interface to process data in an optimized manner. The term NoSQL refers to a plethora of new stores which essentially trades off well-known ACID properties for higher availability or scalability, using techniques such as eventual consistency, horizontal scalability, efficient replication, and schema-less data models. This work proposes a mapping from the data model of different kinds of NoSQL stores— key/value, columnar, and document-oriented—to the XDM data model, thus allowing for standardization and querying NoSQL data using higher-level languages, such as XQuery. This work also explores several optimization scenarios to improve performance on top of these stores. Besides, we also add updating semantics to XQuery by introducing simple CRUD-enabling functionalities. Finally, this work analyzes the performance of the system in several scenarios. Keywords NoSQL, Big Data, key/value, XQuery, ACID, CAP
We have seen a trend towards specialization in database markets in the last few years. There is no more one-sizefits-all approach when comes to storing and dealing with data, and different types of DBMSs are being used to tackle different types of problems. One of these being the Big Data topic.
It is not completely clear what Big Data means after all. Lately, it is being characterized by the so-called 3 V’s: volume—comprising the actual size of data; velocity —comprising essentially a time span in which data data must be analyzed; and variety —comprising types of data. Big Data applications need to understand how to create solutions in these data dimensions.
RDBMS have had problems when facing Big Data applications, like in web environments. Two of the main reasons 24th GI-Workshop on Foundations of Databases (Grundlagen von Datenbanken), 29.05.2012 - 01.06.2012, Lübbenau, Germany.
Copyright is held by the author/owner(s). for that are scalability and flexibility. The solution RDBMS provide is usually twofold: either (i) a horizontally-scalable architecture, which in database terms generally means giving up joins and also complex multi-row transactions; or (ii) by using parallel databases, thus using multiple CPUs and disks in parallel to optimize performance. While the latter increases complexity, the former just gives up operations because they are too hard to implement in distributed environments. Nevertheless, these solutions are neither scalable nor flexible.
NoSQL tackles these problems with a mix of techniques, which involves either weakening ACID properties or allowing more flexible data models. The latter is rather simple: some scenarios—such as web applications—do not conform to a rigid relational schema, cannot be bound to the structures of a RDBMS, and need flexibility. Solutions exist, such as using XML, JSON, pure key/value stores, etc, as data model for the storage layer. Regarding the former, some NoSQL systems relax consistency by using mechanisms such as multi-version concurrency control, thus allowing for eventually consistent scenarios. Others support atomicity and isolation only when each transaction accesses data within some convenient subset of the database data. Atomic operations would require some distributed commit protocol—like two-phase commit—involving all nodes participating in the transaction, and that would definitely not scale. Note that this has nothing to do with SQL, as the acronym NoSQL suggests. Any RDBMS that relaxes ACID properties could scale just as well, and keep SQL as querying language.
Nevertheless, when it comes to performance, NoSQL
systems have shown some interesting improvements. When
considering update- and lookup-intensive OLTP workloads—
scenarios where NoSQL are most often considered—the work
of [
When considering OLAP scenarios, RDBMS require rigid
schema to perform usual OLAP queries, whereas most NoSQL
stores rely on a brute-force processing model called
MapReduce. It is a linearly-scalable programming model for
processing and generating large data sets, and works with any
data format or shape. Using MapReduce capabilities,
parallelization details, fault-tolerance, and distribution aspects
are transparently offered to the user. Nevertheless, it
requires implementing queries from scratch and still suffers
from the lack of proper tools to enhance its querying
capabilities. Moreover, when executed atop raw files, the
processing is inefficient. NoSQL stores provide this structure,
thus one could provide a higher-level query language to take
full advantage of it, like Hive [
These approaches require learning separated query languages, each of which specifically made for the implementation. Besides, some of them require schemas, like Hive and Pig, thus making them quite inflexible. On the other hand, there exists a standard that is flexible enough to handle the offered data flexibility of these different stores, whose compilation steps are directly mappable to distributed operations on MapReduce, and is been standardized for over a decade: XQuery.
Contribution
Consider employing XQuery for implementing the large class
of query-processing tasks, such as aggregating, sorting,
filtering, transforming, joining, etc, on top of MapReduce as a
first step towards standardization on the realms of NoSQL
[
This is essentially the contribution of this work: allowing for NoSQL stores to be used as storage layer underneath a MapReduce-based XQuery engine, Brackit[?]—a generic XQuery processor, independent of storage layer. We rely on Brackit’s MapReduce-mapping facility as a transparently distributed execution engine, thus providing scalability. Moreover, we exploit the XDM-mapping layer of Brackit, which provides flexibility by using new data models. We created three XDM-mappings, investigating three different implementations, encompassing the most used types of NoSQL stores: key/value, column-based, and document-based.
The remainder of this paper is organized as follows. Section 2 introduces the NoSQL models and their characteristics. Section 3 describes the used XQuery engine, Brackit, and the execution environment of XQuery on top of the MapReduce model. Section 4 describes the mappings from various stores to XDM, besides all implemented optimizations. Section 5 exposes the developed experiments and the obtained results. Finally, Section 6 concludes this work.
This work focuses on three different types of NoSQL stores,
namely key/value, columnar, and document-oriented,
represented by Riak [
Riak is the simplest model we dealt with: a pure
key/value store. It provides solely read and write operations to
uniquely-identified values, referenced by key. It does not
provide operations that span across multiple data items and
there is no need for relational schema. It uses concepts
such as buckets, keys, and values. Data is stored and
referenced by bucket/key pairs. Each bucket defines a virtual
key space and can be thought of as tables in classical
relational databases. Each key references a unique value, and
there are no data type definitions: objects are the only unit
of data storage. Moreover, Riak provides automatic load
balancing and data replication. It does not have any
relationship between data, even though it tries by adding link
between key/value pairs. It provides the most flexibility, by
allowing for a per-request scheme on choosing between
availability or consistency. Its distributed system has no master
node, thus no single point of failure, and in order to solve
partial ordering, it uses Vector Clocks [
HBase enhances Riak’s data model by allowing columnar data, where a table in HBase can be seen as a map of maps. More precisely, each key is an arbitrary string that maps to a row of data. A row is a map, where columns act as keys, and values are uninterpreted arrays of bytes. Columns are grouped into column families, and therefore, the full key access specification of a value is through column family concatenated with a column—or using HBase notation: a qualifier. Column families make the implementation more complex, but their existence enables fine-grained performance tuning, because (i) each column family’s performance options are configured independently, like read and write access, and disk space consumption; and (ii) columns of a column family are stored contiguously in disk. Moreover, operations in HBase are atomic in the row level, thus keeping a consistent view of a given row. Data relations exist from column family to qualifiers, and operations are atomic on a per-row basis. HBase chooses consistency over availability, and much of that reflects on the system architecture. Auto-sharding and automatic replication are also present: shardling is automatically done by dividing data in regions, and replication is achieved by the master-slave pattern.
MongoDB fosters functionality by allowing more RDBMSlike features, such as secondary indexes, range queries, and sorting. The data unit is a document, which is an ordered set of keys with associated values. Keys are strings, and values, for the first time, are not simply objects, or arrays of bytes as in Riak or HBase. In MongoDB, values can be of different data types, such as strings, date, integers, and even embedded documents. MongoDB provides collections, which are grouping of documents, and databases, which are grouping of collections. Stored documents do not follow any predefined schema. Updates within a single document are transactional. Consistency is also taken over availability in MongoDB, as in HBase, and that also reflects in the system architecture, that follows a master-worker pattern.
Overall, all systems provide scaling-out, replication, and parallel-computation capabilities. What changes is essentially the data-model: Riak seams to be better suited for problems where data is not really relational, like logging. On the other hand, because of the lack of scan capabilities, on situations where data querying is needed, Riak will not perform that well. HBase allows for some relationship between data, besides built-in compression and versioning. It is thus an excellent tool for indexing web pages, which are highly textual (thus benefiting from compression), as well as interrelated and updatable (benefiting from built-in versioning). Finally, MongoDB provides documents as granularity unit, thus fitting well when the scenario involves highly-variable or unpredictable data.
BRACKIT AND MAPREDUCE
Several different XQuery engines are available as options
for querying XML documents. Most of them provide
either (i) a lightweight application that can perform queries
on documents, or collections of documents, or (ii) an XML
database that uses XQuery to query documents. The
former lacks any sort of storage facility, while the latter is just
not flexible enough, because of the built-in storage layer.
Brackit1 provides intrinsic flexibility, allowing for different
storage levels to be “plugged in”, without lacking the
necessary performance when dealing with XML documents [
Compilation The compilation process in Brackit works as follows: the parser analyzes the query to validate the syntax and ensure that there are no inconsistencies among parts of the statement. If any syntax errors are detected, the query compiler stops processing and returns the appropriate error message. Throughout this step, a data structure is built, namely an AST (Abstract Syntax Tree). Each node of the tree denotes a construct occurring in the source query, and is used through the rest of the compilation process. Simple rewrites, like constant folding, and the introduction of let bindings are also done in this step.
The pipelining phase transforms FLWOR expressions into
pipelines—the internal, data-flow-oriented representation of
FLWORs, discussed later. Optimizations are done atop
pipelines, and the compiler uses global semantics stored in
the AST to transform the query into a more-easily-optimized
form. For example, the compiler will move predicates if
possible, altering the level at which they are applied and
potentially improving query performance. This type of
operation movement is called predicate pushdown, or filter
pushdown, and we will apply them to our stores later on. More
optimizations such as join recognition, and unnesting are
present in Brackit and are discussed in [
The system hitherto cited processes collections stored in
HDFS as text files, and therefore does not control details
about encoding and management of low-level files. If the
DBMS architecture [
It represents each query in MapReduce as sequence of jobs, where each job processes a section of a FLWOR pipeline. In order to use MapReduce as a query processor, (i) it breaks FLWOR pipelines are into map and reduce functions, and (ii) groups these functions to form a MapReduce job. On (i), it converts the logical-pipeline representation of the FLWOR expression—AST—to a MapReduce-friendly version. MapReduce uses a tree of splits, which represents the logical plan of a MapReduce-based query. Each split is a non-blocking operator used by MapReduce functions. The structure of splits is rather simple: it contains an AST and pointers to successor and predecessor splits. Because splits are organized in a bottom-up fashion, leaves of the tree are map functions, and the root is a reduce function—which produces the query output.
On (ii), the system uses the split tree to generate
possibly multiple MapReduce job descriptions, which can be
executed in a distributed manner. Jobs are exactly the ones
used on Hadoop MapReduce [
XDM MAPPINGS
This section shows how to leverage NoSQL stores to work as storage layer for XQuery processing. First, we present mappings from NoSQL data models to XDM, adding XDMnode behavior to these data mappings. Afterwards, we discuss possible optimizations regarding data-filtering techniques. Riak Riak’s mapping strategy starts by constructing a key/value tuple from its low-level storage representation. This is essentially an abstraction and is completely dependent on the storage used by Riak. Second, we represent XDM operations on this key/value tuple. We map data stored within Riak utilizing Riak’s linking mechanism. A key/value pair kv represents an XDM element, and key/value pairs linked to kv are addressed as children of kv. We map key/value tuples as XDM elements. The name of the element is simply the name of the bucket it belongs to. We create one bucket for the element itself, and one extra bucket for each link departing from the element. Each child element stored in a separated bucket represents a nested element within the key/value tuple. The name of the element is the name of the link between key/values. This does not necessarily decrease data locality: buckets are stored among distributed nodes based on hashed keys, therefore uniformly distributing the load on the system. Besides, each element has an attribute key which Riak uses to access key/value pairs on the storage level.
It allows access using key/value as granularity, because every single element can be accessed within a single get operation. Full reconstruction of an element el requires one access for each key/value linked to el. Besides, Riak provides atomicity using single key/value pairs as granularity, therefore consistent updates of multiple key/value tuples cannot be guaranteed.
HBase HBase’s mapping strategy starts by constructing a columnar tuple from the HDFS low-level-storage representation. HBase stores column-family data in separated files within HDFS, therefore we can use this to create an efficient mapping. Figure 2 presents this XDM mapping, where we map a table partsupp using two column families: references and values, five qualifiers: partkey, suppkey, availqty, supplycost, and comment. We map each row within an HBase table to an XDM element. The name of the element is simply the name of the table it belongs to, and we store the key used to access such element within HBase as an attribute in the element. The figure shows two column families: references and values. Each column family represents a child element, whose name is the name of the column family. Accordingly, each qualifier is nested as a child within the column-family element from which it descends.
MongoDB MongoDB’s mapping strategy is straight-forward. Because it stores JSON-like documents, the mapping consists essentially of a document field → element mapping. We map each document within a MongoDB collection to an XDM element. The name of the element is the name of the collection it belongs to. We store the id —used to access the document within MongoDB—as an attribute on each element. Nested within the collection element, each field of the document represents a child element, whose name is the name of the field itself. Note that MongoDB allows fields to be of type document, therefore more complex nested elements can be achieved. Nevertheless, the mapping rules work recursively, just as described above.
Nodes
We describe XDM mappings using object-oriented notation.
Each store implements a Node interface that provides node
behavior to data. Brackit interacts with the storage using
this interface. It provides general rules present in XDM [
Overall, each instance of these objects represents one unit of data from the storage level. In order to better grasp the mapping, we describe the HBase abstraction in more details, because it represents the more complex case. Riak’s and MongoDB’s representation follow the same approach, but without a “second-level node”. Tables are not represented within the Node interface, because their semantics represent where data is logically stored, and not data itself. Therefore, they are represented using a separated interface, called Collection. Column families represent a first-levelaccess. Qualifiers represent a second-level-access. Finally, values represent a value-access. Besides, first-level-access, second-level-access, and value-access must keep track of current indexes, allowing the node to properly implement XDM operations. Figure 3 depicts the mapping. The upper-most part of the picture shows a node which represents a data row from any of the three different stores. The first layer of nodes—with level = 1st —represents the first-level-access, explained previously. The semantic of first-level-access differs within different stores: while Riak and MongoDB interpret it as a value wrapper, HBase prefers a column family wrapper. Following, HBase is the only implementation that needs a second-level-access, represented by the middle-most node with level = 2nd, in this example accessing the wrapper of regionkey = “1”. Finally, lower-level nodes with level = value access values from the structure.
Optimizations We introduce projection and predicate pushdowns optimizations. The only storage that allows for predicate pushdown is MongoDB, while filter pushdown is realized on all of them. These optimizations are fundamental advantages of this work, when compared with processing MapReduce over raw files: we can take “shortcuts” that takes us directly to the bytes we want in the disk.
Filter and projections pushdown are an important optimization for minimizing the amount of data scanned and processed by storage levels, as well as reducing the amount of data passed up to the query processor. Predicate pushdown is yet another optimization technique to minimize the amount of data flowing between storage and processing layers. The whole idea is to process predicates as early in the plan as possible, thus pushing them to the storage layer.
On both cases we traverse the AST, generated in the beginning of the compilation step, looking for specific nodes, and when found we annotate the collection node on the AST with this information. The former looks for path expressions (PathExpr ) that represent a child step from a collection node, or for descendants of collection nodes, because in the HBase implementation we have more than one access level within storage. The later looks for general-comparison operators, such as equal, not equal, less than, greater than, less than or equal to, and greater than or equal to. Afterwards, when accessing the collection on the storage level, we use the marked collections nodes to filter data, without further sending it to the query engine.
NoSQL updates
The used NoSQL stores present different API to persist data.
Even though XQuery does not provide data-storing
mechanisms on its recommendation, it does provide an extension
called XQuery Update Facility [
The insert function stores a value within the underlying store. We provide two possible signatures: with or without db:insert($table as xs:string, $key as xs:string, $value as node()) as xs:boolean The delete function deletes a values from the store. We also provide two possible signatures: with or without $key, therefore allowing for deletion of a giveng key, or droping a given table.
db:delete($table as xs:string,
$key as xs:string) as xs:boolean
EXPERIMENTS
The framework we developed in this work is mainly
concerned with the feasibility of executing XQuery queries atop
NoSQL stores. Therefore, our focus is primarily on the proof
of concept. The data used for our tests comes from the
TPCH benchmark [
Figure 4 shows the gathered latency times of the best schemes of each store, using log-scale. As we can see, all approaches take advantage from the optimization techniques. The blue column of the graph—full table scan—shows the latency when scanning all data from TPC-H tables. The red column —single column scan—represents the latency when scanning a simple column of each table. Filter pushdown optimizations explain the improvement in performance when compared to the first scan, reducing the amount of data flowing from storage to processing level. The orange column— predicate column scan—represents the latency when scanning a single column and where results were filtered by a predicate. We have chosen predicates to cut in half the amount of resulting data when compared with single column scan. The querying time was reduced in approximately 30%, not reaching the 50% theoretically-possible-improvement rate, 6.
CONCLUSIONS
We extended a mechanism that executes XQuery to work with different NoSQL stores as storage layer, thus providing a high-level interface to process data in an optimized manner. We have shown that our approach is generic enough to work with different NoSQL implementations.
Whenever querying these systems with MapReduce—taking advantage of its linearly-scalable programming model for processing and generating large-data sets—parallelization details, fault-tolerance, and distribution aspects are hidden from the user. Nevertheless, as a data-processing paradigm, MapReduce represents the past. It is not novel, does not use schemas, and provides a low-level record-at-a-time API: a scenario that represents the 1960’s, before modern DBMS’s. It requires implementing queries from scratch and still suffers from the lack of proper tools to enhance its querying capabilities. Moreover, when executed atop raw files, the processing is inefficient—because brute force is the only processing option. We solved precisely these two MapReduce problems: XQuery works as the higher-level query language, and NoSQL stores replace raw files, thus increasing performance. Overall, MapReduce emerges as solution for situations where DBMS’s are too “hard” to work with, but it should not overlook the lessons of more than 40 years of database technology.
Other approaches cope with similar problems, like Hive,
and Scope. Hive [
REFERENCES
Independence, and Parallelism. PhD thesis, University
of Kaiserslautern, 12 2012.
[
VLDB Endow., 1(2):1265–1276, Aug. 2008.
[
Definitive Guide. Oreilly Series. O’Reilly Media,
Incorporated, 2010.
[
R. Ramakrishnan, and R. Sears. Benchmarking cloud
serving systems with ycsb. In Proceedings of the 1st
ACM symposium on Cloud computing, SoCC ’10,
pages 143–154, New York, NY, USA, 2010. ACM.
[
Measuring elasticity for cloud databases. In Proceedings of the The Second International Conference on Cloud Computing, GRIDs, and
Virtualization, 2011.
[
Media, 2011.
[
Datenbank-Spektrum, 14:38–48, 2005.
[
ACM.
[
REC-xpath-datamodel-20070123/, January 2007.
[