• Summary
• LIFO Members (Directory)
• Research Teams
• CA
• GAMoC
• LMV
• Pamda
• SDS
• Research Actions
• Doctoral Research
• Seminars and Events
• Seminars (french)
• Events at LIFO
• Events out of LIFO
• Publications and Software
• Publications
• Doctoral and Habil. Theses
• Research Reports
• Software
• Technology transfer

• Contacts/Reaching LIFO
• Who's who at LIFO
• Coming to LIFO
• Teaching
• CS Department
• CS Technical Department
• INSA Centre-Val de Loire

Contact

LIFO - Bâtiment IIIA
Rue Léonard de Vinci
B.P. 6759
F-45067 ORLEANS Cedex 2

Email: contact.lifo
Tel: +33 (0)2 38 41 99 29
Fax: +33 (0)2 38 41 71 37

Go to Research Reports of Year : 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018

LIFO Research Report for Year 2017

RR-2017-01 Transforming Prefix-Constrained or Controlled Rewrite Systems
Nirina Andrianarivelo, Vivien Pelletier, Pierre Réty
Date : 2017-02-03
Abstract Download

RR-2017-02 Handling limits of high degree vertices in graph processing using MapReduce and Pregel
M. Al Hajj Hassan and Mostafa Bamha
Date : 2017-02-27
Abstract Download

RR-2017-03 Concurrent Program Verification by Code Transformation: Correctness
Allan Blanchard, Nikolai Kosmatov, Frédéric Loulergue
Date : 2017-03-08
Abstract Download

RR-2017-05 Updating of RDF/S Databases under Negative and Tuple-Generating Constraints
Mirian Halfeld Ferrari and Dominique Laurent
Date : 2017-04-12
Abstract Download

RR-2017-06 Personalized Environment for Querying Semantic Knowledge Graphs: a MapReduce Solution
Mostafa Bamha, Jacques Chabin, Mirian Halfeld Ferrari, Béatrice Markhoff, Thanh Binh Nguyen
Date : 2017-07-07
Abstract Download

---

Abstracts of Research Reports

RR-2017-01 Transforming Prefix-Constrained or Controlled Rewrite Systems
Nirina Andrianarivelo, Vivien Pelletier, Pierre Réty
Abstract : We present two techniques for transforming any prefix-cons\-trained and any controlled term rewrite system into an ordinary rewrite system. We prove that both transformations preserve the rewrite computations, and preserve termination. In this way, prefix-constrained rewriting and controlled rewriting can be run, and termination can be checked, using the usual tools for ordinary rewriting.
Keywords : controlled rewriting, prefix constrained rewriting, tree automaton.

RR-2017-02 Handling limits of high degree vertices in graph processing using MapReduce and Pregel
M. Al Hajj Hassan and Mostafa Bamha
Abstract : Even if Pregel scales better than MapReduce in graph processing by reducing iteration's disk I/O, while offering an easy programming model using "think like vertex" approach, large scale graph processing is still challenging in the presence of high degree vertices: Communication and load imbalance among processing nodes can have disastrous effects on performance. In this paper, we introduce a scalable MapReduce graph partitioning approach for high degree vertices using a master/slave partitioning allowing to balance communication and computation among processing nodes during all the stages of graph processing. Cost analysis and performance tests of this partitioning are given to show the effectiveness and the scalability of this approach in large scale systems.
Keywords : Graph processing, High degree vertices, Data skew, MapReduce programming model, Pregel, Distributed file systems.

RR-2017-03 Concurrent Program Verification by Code Transformation: Correctness
Allan Blanchard, Nikolai Kosmatov, Frédéric Loulergue
Abstract : Frama-C is a software analysis framework that provides a common infrastructure and a common behavioral specification language to plugins that implement various static and dynamic analyses of C programs. Most plugins do not support concurrency. We have proposed conc2seq, a Frama-C plugin based on program transformation, capable to leverage the existing huge code base of plugins and to handle concurrent C programs. In this paper we formalize and sketch the proof of correctness of the program trans- formation principle behind conc2seq, and present an effort towards the full mecha- nization of both the formalization and proofs with the proof assistant Coq.
Keywords :

RR-2017-05 Updating of RDF/S Databases under Negative and Tuple-Generating Constraints
Mirian Halfeld Ferrari and Dominique Laurent
Abstract : In this paper, we address the issue of updating RDF/S databases, in which constraints are imposed. Contrary to standard approaches where constraints are restricted to those inherently defined by the data model, we also consider constraints imposed by the particular application modelled by the database. All these constraints fall in two categories, called positive and negative, generalizing the well known key- foreign key constraints. Based on a chasing technique, we propose a deterministic update strategy which deals with sets of insertions and deletions over RDF/S instances, while satisfying consistency and minimal change requirements. The time complexity of our approach is polynomial.
Keywords :

RR-2017-06 Personalized Environment for Querying Semantic Knowledge Graphs: a MapReduce Solution
Mostafa Bamha, Jacques Chabin, Mirian Halfeld Ferrari, Béatrice Markhoff, Thanh Binh Nguyen
Abstract : Querying according to a personalised context is an increas- ingly required feature on semantic graph databases. We define contexts by using constraints imposed on queries and not on data sources. No correction trial is performed on an inconsistent database but answers are ensured to be valid. Data confidence according to provenance is also taken into account. As constraint validation and query evaluation are two independent modules, our approach can be tested with di↵erent query evaluators. This paper focus on a MapReduce query environment.
Keywords : graph database, RDF, constraint, context, MapReduce.