Benjamin Djahandideh

François Goasdoué

Zoi Kaoudi

Ioana Manolescu

Jorge Quiané-Ruiz
email: jquianeruiz@qf.org.qa

Stamatis Zampetakis

Jorge Quiané

Franc ¸ois Goasdou

Jorge-Arnulfo Quian É-Ruiz

How to Deal with Cliques at Work

R

INTRODUCTION

The Resource Description Framework (RDF, in short) [START_REF] Hayes | RDF Semantics. W3C Recommendation[END_REF] is a flexible data model for representing graph-structured data. In a nutshell, an RDF dataset consists of triples of the form (s, p, o), stating that a subject has a property whose value is object. Nowadays, many applications use RDF as a first-class citizen or provide support for RDF data, in areas ranging from the Semantic Web and scientific applications, such as BioPAX1 and UniProt2 , to Web 2.0 platforms, such as RDFizers3 , and databases [START_REF] Chong | An Efficient SQL-based RDF Querying Scheme[END_REF]. The RDF data model is accompanied by the SPARQL standard query language for querying RDF data. Efficient evaluation of SPARQL queries remains challenging though, due to the lack of structure and regularity in RDF graphs, and because SPARQL queries typically involve many joins over the RDF data set.

Many algorithms and architectures have been proposed to efficiently manage RDF data [START_REF] Abadi | Scalable Semantic Web Data Management using Vertical Partitioning[END_REF][START_REF] Neumann | The RDF-3X Engine for Scalable Management of RDF Data[END_REF][START_REF] Weiss | Hexastore: Sextuple Indexing for Semantic Web Data Management[END_REF]. However, scalability in RDF data management is still an open problem. The main challenge resides in the sheer size of the data itself. Many distributed systems, especially MapReducebased, have been proposed for RDF data management [START_REF] Hose | WARP: Workload-Aware Replication and Partitioning for RDF[END_REF][START_REF] Huang | Scalable SPARQL Querying of Large RDF Graphs[END_REF][START_REF] Husain | Heuristics-Based Query Processing for Large RDF Graphs Using Cloud Computing[END_REF][START_REF] Kim | From SPARQL to MapReduce: The Journey Using a Nested TripleGroup Algebra (demo)[END_REF][START_REF] Rohloff | High-Performance, Massively Scalable Distributed Systems using the MapReduce Software Framework: the SHARD Triple-Store[END_REF][START_REF] Zhang | Towards Efficient Join Processing over Large RDF Graph Using MapReduce[END_REF]. However, performance problems still remain, essentially for one of these two reasons: (i) they transfer a considerable amount of data through the network or (ii) they do not fully exploit the parallelism offered in such an environment by joining intermediary results sequentially, both of which negatively impact query performance. Other systems leverage distributed key-value stores to store and index a large number of RDF triples such as [START_REF] Crainiceanu | Rya: A Scalable RDF Triple Store For The Clouds[END_REF][START_REF] Papailiou | H 2 RDF: Adaptive Query Processing on RDF Data in the Cloud[END_REF][START_REF] Zeng | A Distributed Graph Engine for Web Scale RDF Data[END_REF]. However, as key-value stores do not support joins, these systems often perform the joins on a single node. Among the above mentioned systems, only [START_REF] Papailiou | H 2 RDF: Adaptive Query Processing on RDF Data in the Cloud[END_REF] leverages MapReduce for queries with low selectivity, while Trinity.RDF [START_REF] Zeng | A Distributed Graph Engine for Web Scale RDF Data[END_REF], based on a distributed in-memory key-value store, evaluates SPARQL queries by navigating the distributed RDF graph and using the results from one triple pattern for the next one.

In this demo, we present CliqueSquare [15], an efficient highly-parallel RDF data management platform, on top of Hadoop, for storing and querying big RDF datasets. Clique-Square introduces a novel RDF data storage scheme and query optimization algorithm (based on query variable cliques, thus the name) which both enable efficient and scalable query evaluation. Generally speaking, CliqueSquare aims at reducing both the number of MapReduce jobs and the amount of data transferred through the network. The demo highlights the following three key features: (i) Data Partitioning -we show how the data storage provided by Clique-Square helps to perform many queries without any network traffic; (ii) Job Minimization -we show the benefits in query performance achieved by CliqueSquare as a result of having as few MapReduce jobs as possible; (iii) Redundancy Exploration through DAG-shaped plans -we show how DAGshaped plans may help reduce the intermediary results and thus, lead to better query performance.

CLIQUESQUARE

We introduce CliqueSquare, a platform based on Hadoop. CliqueSquare relies on a novel RDF data partitioning scheme and a novel query optimization algorithm. These two components allow CliqueSquare to minimize the number of Map-Reduce jobs as well as the network traffic. Figure 1 outlines the data partitioner and the query processor, each of which is briefly outlined in this Section. A comprehensive description of CliqueSquare can be found in [15]. Shuffling. All partitions corresponding to the same value are placed on the same compute node. For instance, all the stud1 values, regardless of whether they appear as subjects, objects or properties, are located on node n1 (Figure 1). To cope with skew issues that may be raised by over-popular values in the data, CliqueSquare defines a special partition for the rdf:type property (which is part of the RDF standard and thus very popular) as in [START_REF] Husain | Data Intensive Query Processing for Large RDF Graphs Using Cloud Computing Tools[END_REF], and splits other partitions that are too large based on a predefined threshold [15].

Data Partitioner

ReduceGrouping. Finally, CliqueSquare groups all the subject, respectively property, and object, partitions inside a node based on the property value, and stores each resulting group into HDFS. Looking inside node n1 (Figure 1), we observe that we have two files for the property member; one based on the subject partition and one based on the object.

Query Processor

Query processing in CliqueSquare relies on a novel query optimization model and algorithm based on cliques in query variable graphs. The whole process is illustrated in the upper-right part of Figure 1. Given an incoming Basic Graph Pattern (BGP) SPARQL query q, the Query Parser outputs a variable graph representing q. This graph is then used by the Plan Optimizer to produce a logical query plan. Finally, the Job Translator transforms the logical plan to a sequence of MapReduce jobs utilizing CliqueSquare operators that can be executed in Hadoop. In the following we focus on the plan optimization procedure.

Variable graph. Besides representing an initial query, CliqueSquare also uses variable graphs to represent (partially) evaluated queries, in which some or all joins have been enforced. Formally: ?g p8 ?h (t8) ?g p9 ?i (t9) ?i p10 ?j (t10) ?j p11 ?k (t11) } GV of a BGP query q is a labeled multigraph (N, E, V ), where V is the set of variables from q, N is the set of nodes, and E ⊆ N × V × N is a set of labeled undirected edges such that: (i) each node n ∈ N corresponds to a set of triple patterns in q; (ii) there is an edge (n1, v, n2) ∈ E between two distinct nodes n1, n2 ∈ N iff their corresponding sets of triple patterns join on the variable v ∈ V .

Figure 2 shows a query (Q1) and its variable graph, where every node represents a single triple pattern.

Variable clique. At the core of the CliqueSquare query processing mechanism lies the concept of variable clique for representing n-way joins. A variable clique is a set of nodes connected with edges all labeled by the same variable. A maximal clique comprises all the nodes incident to an edge with the same variable. For example, in variable graph G1, the maximal clique of d is {t3, t4, t5, t6}. We term any nonempty subset of a maximal clique as partial clique.

Based on variable graphs and cliques, CliqueSquare uses two main operations during its optimization algorithm, namely clique decomposition and clique reduction.

Clique decomposition. As first step toward building a query plan, CliqueSquare decomposes a variable graph into several cliques. Formally: Definition 2.2 (Clique decomposition). Given a variable graph GV = (N, E, V ), a clique decomposition of GV is a set of variable cliques (maximal or partial) of GV which covers all nodes of N , i.e., each node n ∈ N appears in at least one clique, such that the size of the decomposition is strictly smaller than the number of nodes |N |.

For example, one clique decomposition in the variable graph G1 is D1 = {{t1, t2, t3}, {t3, t4, t5, t6}, {t6, t7}, {t7, t8, t9}, {t9, t10},{t10, t11}}; this decomposition follows the distribution of colors on the graph edges in Figure 2. There are more than one ways to decompose the graph; we discuss all alternatives in [15]. From a query optimization perspective, choosing a clique decomposition corresponds to selecting a set of n-way joins to evaluate.

Clique reduction. After having identified a clique decomposition, CliqueSquare shrinks the variable graph into a smaller one. We formally define this process as follows:

Definition 2.3 (Clique reduction). Given a variable graph GV = (N, E, V ) and one of its clique decompositions D, the reduction of GV based on D is the variable graph G ′ V = (N ′ , E ′ , V ) such that: (i) every clique c ∈ D correspond to a node n ′ ∈ N ′ , whose set of triple patterns is the union of the nodes involved in c ⊆ N ; (ii) there is an edge

(n ′ 1 , v, n ′ 2 ) ∈ E ′ between two distinct nodes n ′ 1 , n ′ 2 ∈ N ′ iff
their corresponding sets of triple patterns join on the variable v ∈ V .

For example, given the above clique decomposition D1, CliqueSquare reduces G1 into a variable graph composed of one node for each maximal clique in G1 and its corresponding edges. From a query optimization perspective, clique reduction corresponds to applying the joins identified by the given decomposition.

CliqueSquare algorithm. CliqueSquare query optimization algorithms develops possible sequences of clique decompositions followed by clique reduction, until all the query predicates have been applied (Algorithm 1). Overall, Clique-Square takes as an input a variable graph G of an incoming query and a list of variable graphs states modeling the successive evaluation steps that led to G. As a result, Clique-Square outputs a set of logical query plans QP , each of which is an alternative way to evaluate the incoming query. More in detail, CliqueSquare starts processing the variable graph G of the initial query, where each node consists of a single triple pattern, and the empty queue states. At each recursive call, cliqueDecompositions (line 6) returns a set of clique decompositions of G, which is used by cliqueReduction (line 8) to reduce G into G ′ . G ′ is in turn recursively processed, until it consists of a single node. CliqueSquare builds the corresponding logical query plan out of the list of variable graphs comprised in states (line 3).

Depending on the clique decomposition alternative that is chosen, eight different instantiations of Algorithm 1 are possible [15]. Each instantiation results in a different plan space. In our demonstration, the user is allowed to choose between four of the most prominent ones and perceive the benefit of our winner algorithm MSC (minimum simple covers of partial cliques) in terms of efficiency (short optimization times) and effectiveness (rapidly evaluated plans). For more details on the different algorithms as well as their formal properties we point the reader to [15].

Figure 3 shows the runtimes for HadoopRDF [START_REF] Husain | Heuristics-Based Query Processing for Large RDF Graphs Using Cloud Computing[END_REF] (the state-of-the art Hadoop-based RDF store) and CliqueSquare with two clique decompositions: MSC+ (minimum simple covers of maximal cliques) and MSC. We ran these experiments on 7 nodes of our cluster, detailed in Section 3.1, using five different queries over a 2 billion triples dataset from the LUBM benchmark. We observe in these results that CliqueSquare is more than one order of magnitude faster than HadoopRDF. We also see the high effectiveness of our algorithm MSC, producing plans up to one order of magnitude faster than MSC+ (our second best decomposition algorithm). More experiments are described in [15].

DEMONSTRATION

Our goal is to demonstrate CliqueSquare performing a variety of queries with different characteristics and illustrate its efficiency. The audience is invited to interact with the system to compose queries, explore the internals of different optimization algorithms, select and monitor the execution process of plans in two available clusters.

Setup

We use a cluster of 8 nodes, where each node has: one 2.93GHz Quad Core Xeon processors; 4×4GB of main memory; 2×600GB SAS hard disks configured in RAID 1; 1 Gigabit network; Linux CentOS release 6.4. We divide this cluster into two equal-size clusters to directly compare different techniques of CliqueSquare in some of the scenarios we consider. We use the popular RDF benchmark LUBM [START_REF] Guo | LUBM: A Benchmark for OWL Knowledge Base Systems[END_REF].

Demo Scenarios

To better showcase CliqueSquare to the demo attendees, we guide them through three different scenarios where they can see different aspects of CliqueSquare.

(1) Network traffic. We aim at showing how CliqueSquare significantly reduces the amount of data to transfer through the network by exploiting our sophisticated data partitioning scheme. In this scenario, the audience is invited to see how CliqueSquare efficiently executes queries using a maponly job incurring no network traffic at all. For this, the audience can choose to run one out of three predefined queries: one that retrieves all the graduate students and the courses that they participate in (Q1); one query that retrieves the name, the address, and the research interest of every full professor that works in a specific university (Q2); one query extending Q2 by having no restriction on the university (Q3).

(2) Number of MapReduce jobs. We show the audience the importance of plans with few jobs by letting them execute and compare query plans with different numbers of jobs, created by CliqueSquare for the same query. For the latter, the following two queries are provided: a query that returns the undergraduate students whose advisor is an associate professor and teaches a course they take (Q4); one query that asks for the undergraduate students of "University 3", whose advisor is a full professor, the courses they attend, and the email address of their advisor (Q5).

(3) Redundancy exploration. Last but not least, we aim at showing to the audience the benefits in query performance of having in some cases DAG-shaped, rather than tree-shaped, query plans. DAG-shaped plans result into reading at least one relation more than once, justifying the use of term "redundancy". The audience is able to compare the running time of DAG-shaped with tree-shaped query plans. For this, the audience is invited to run one query asking for graduate students of a department which belongs to the university they hold a degree from (Q6).

Demo Interaction

CliqueSquare comes with an intuitive and interactive graphical user interface to showcase each of the aforementioned scenarios. Figure 4 illustrates its three most important graphical interfaces. As a first step, in the left-side graphical interface, the audience is able to: (i) select one of the predefined queries to demonstrate one of the aforementioned scenarios; (ii) observe the variable graph CliqueSquare creates for each selected query; (iii) modify any of the predefined queries to adapt each demo scenario at will; Then, in the center graphical interface of Figure 4, the audience can: (iv) select one or two of the decomposition algorithms to run; (v) navigate through different visuals of a query plan (logical, physical, MapReduce plan) (vi) select different query plans to study and run; (vii) create their own personalized query workloads for realistic evaluations of CliqueSquare; (viii) visualize each of the steps of the query optimization process in CliqueSquare; Finally, in the right-side graphical interface, the audience is invited to: (ix) run their personalized query workloads; (x) monitor the progress of the MapReduce jobs resulting from their choices.

Figure 1 :

 1 Figure 1: CliqueSquare architecture. data three times). CliqueSquare exploits this data replication to partition and store RDF data three times, based on the subject, property, and object of triples. Overall, Clique-Square proceeds to store RDF data in three main steps: MapPartitioning. Triples are partitioned based on their subject, property, and object values, which generates three partitions. At the bottom-left of Figure 1 files with -S extension belong to the subject partition, files with -P to the property partition, and files with -O to the object partition.

Figure 2 :

 2 Figure 2: Query Q1 and its variable graph G1.

Algorithm 1 : 2 if |G| = 1 then 3 QP 8 GFigure 3 :

 12383 Figure 3: Query evaluation time for LUBM20K.

Figure 4 :

 4 Figure 4: CliqueSquare graphical user interface.

http://www.biopax.org

http://dev.isb-sib.ch/projects/uniprot-rdf/

http://smile.mit.edu/wiki/RDFizers