Arnaud Castelltort
email: castelltort@lirmm.fr

Anne Laurent
email: laurent@lirmm.fr

Managing and Querying Historical NoSQL GraphDatabases: the HNTP Criteria

Keywords:

Graphs allow to represent many cases from the real world, for instance ontologies, social networking or chemical databases. Graph databases, and especially NoSQL graph databases (e.g., Neo4j) have been designed to deal with such data. This new generation of databases focus on relations rather than on the objects themselves. NoSQL graph databases provide efficient tools to implement robust solutions against big data. In such databases, managing historical data may be important in order to store and analyze evolutions and to understand how relations within and between graph entities evolve. Many works have been done in information systems to keep track of actions and successive states of the data and actions applied on it (updates, deleting, creating, archiving, ...). However, it is hard to handle in NoSQL graph database systems. In this paper, we thus propose to discuss the challenges of implementing historical features in graph databases by introducing and discussing the HNTP criteria solutions should meet.

Introduction

Operational applications often focus on the current state of the system without concentrating efforts on the management of history and versions. When modelling an organisation for instance, the objects (e.g., people, units), their associated information (e.g., name, address) and the relationships between them (e.g., membership, leadership) are considered without focusing on the timeline and history. Systems only capture the current state as a snapshot without considering their dynamic.

When dealing with data, maintaining history is yet one of the key points for understanding and managing systems. It has thus been integrated from thebeginning of database systems, providing tools for storing and querying both the data and the changes. History can be considered to deal with many goals. In some cases, change management in databases aim at dealing with legal requirements, for instance to be able to retrieve which people did an action, the versions of a document (e.g., forensics, legal archives) [START_REF] Olivier | On metadata context in database forensics[END_REF].

In other cases, change management aims at maintaining systems and being able to restore them in case of tampered data and breakdowns (Disaster Recovery Plans). Moreover, the failures having caused the breakdown can sometimes be identified. In many other cases, change management systems are designed to understand how systems work. This is for instance the case for Custumer-Relationship Management (CRM) systems, medical systems or scientific data [START_REF] Buneman | Archiving scientific data[END_REF]. In these cases, history is intrinsic. Evolutions are then studied in order to detect trends, to retrieve the causes for some behaviour, etc. As shown in the case of data warehouses in [START_REF] Yang | Maintaining temporal views over non-temporal information sources for data warehousing[END_REF], data may not be historical by nature although it is important to store and query temporal views. IJRIT Change management have been studied all over the history of databases and data representation and query (e.g., relational model, temporal logic, temporal databases, versions of ontologies, XML or RDF repositories).

In this paper, we focus on the framework of graph data.

Graph data are ubiquitous. In such databases, the focus is put on the relationships between entities, such as social networks, media networks, biological networks, etc. Many tools and systems have been built to deal with such data, ranging from theoretical models to popular implemented systems. As well theoretically as in implemented systems, it has been shown that NoSQL graph databases are much more efficient on linked data than relational model [START_REF] Batra | Comparative analysis of relational and graph databases[END_REF].

Several query methods and languages are proposed withing the graph NoSQL database [START_REF] Holzschuher | Performance of graph query languages: comparison of cypher, gremlin and native access in neo4j[END_REF]. We thus consider this type of database systems. However, very few work have focused on change management in such NoSQL graph databases [START_REF] Khurana | Efficient snapshot retrieval over historical graph data[END_REF][START_REF] Ren | On querying historical evolving graph sequences[END_REF].

We thus discuss below how such systems should manage temporal changes, by providing and discussing the main criteria to be fulfilled.

The paper is organised as follows. Section 2 recalls the main work from the literature dealing with history management and what NoSQL graph databases are. Section 3 introduces the criteria we propose for managing change in graph NoSQL datatabases. Section 4 discusses these criteria and their links, while Section 5 concludes and presents some parts of our further work.

Related Work

NoSQL Graph Databases

Graphs have been considered for many years by mathematicians and computer scientists. They represent entities and their relations, as nodes and vertices. The design of dedicated database engines goes back to the early 80's [START_REF] Angles | Survey of graph database models[END_REF]. They were then surpassed by XML models, before getting back in the recent years, especially with NoSQL models. NoSQL models have emerged in the early 2000's and are often classified into several categories (key-value, column, document, graph NoSQL databases) [START_REF] Cattell | Scalable SQL and NoSQL data stores[END_REF][START_REF] Han | Survey on nosql database[END_REF]. IJRIT NoSQL graph databases [START_REF] Robinson | Graph Databases. O'Reilly[END_REF] have been proposed to manage the large networks that can be found in all domains. When comparing NoSQL and relational models in the context of graph data, it is shown that NoSQL models overpass relational ones [START_REF] Holzschuher | Performance of graph query languages: comparison of cypher, gremlin and native access in neo4j[END_REF][START_REF] Rodriguez | The graph traversal pattern[END_REF].

The current leader of NoSQL graph databases is Neo4j [START_REF]Technology radar[END_REF].

In NoSQL graph databases, entities and relationships are equipped with a set of properties that are represented by key-value pairs. Keys allow to retrieve in a very e#cient manner the associated values. Figure 1 displays an example of such key-value pairs both on nodes and relationships.

In this Figure ,A, B and C are node identifiers and R1, R2, R3 are relationship identifiers. All these entities have properties represented as key-value pairs. The values can be of di#erent forms (numeric, strings, date, etc.), including collections. For instance, nodes may represent people and units from an organisation and which are linked via relationships and properties may store information on these people and units, as shown in Figure 2. IJRIT The tools to traverse such data can be classified into three mains categories, depending on the level which queries are given at, from high-level declarative levels to low level:

• API: the data can be accessed through programmatic APIs (e.g., Java for orientDB, Neo4j databases);

• functional: the data can be accessed through functions that can be combined (e.g., gremlin language);

• declarative: the data can be accessed through a declarative query language (e.g., cypher for Neo4j databases).

Cypher can be seen as being close to SPARQL. It can indeed also manage pattern mining, close to an intuitive query by example manner. However, SPARQL has not been fully adopted by developers and has been designed for the particular data model of RDF. Cypher has thus be proposed as a new tool. It has been shown that the choice of the query tool impacts the performances [START_REF] Batra | Comparative analysis of relational and graph databases[END_REF].

We claim that these works must be extended in order to meet the requirements of history management for NoSQL graph databases. In the next section, we introduce change management concepts and related works about it.

Change Management

Change management can be viewed at several levels, both in terms of model being addressed and in terms of semantics. Regarding the latter point, managing changes can be simply seen at considering only two low-level operations (i.e., adding and deleting) which are the basis for all changes. It can also embed very sophisticated operations, namely high-level operations that cannot be listed in an exhaustive manner [START_REF] Klein | Change management for distributed ontologies[END_REF].

Change management has been considered in the relational model in many works for both modelling the data structures [START_REF] Sudarshan | Meaningful change detection in structured data[END_REF][START_REF] Date | Temporal data and the relational model[END_REF][START_REF] Ozsoyoglu | Temporal and real-time databases: a survey[END_REF] and querying such databases, as introduced in temporal SQL [START_REF] Kulkarni | Temporal features in sql:2011[END_REF][START_REF]The TSQL2 Temporal Query Language[END_REF].

It has also been studied in the context of object-oriented databases [START_REF] Barnerjee | Semantics and implementation of schema evolution in object-oriented databases[END_REF]. In a more general manner, temporal databases have attracted many works and discussions [START_REF]Temporal databases: theory, design, and implementation[END_REF]. IJRIT Change management has been considered for semi-structured databases and XML [START_REF] Chawathe | Representing and querying changes in semistructured data[END_REF][START_REF] Marian | Change-centric management of versions in an xml warehouse[END_REF].

Regarding change management when dealing with graph data and ontologies, it has also attracted research as in [START_REF] Motik | Representing and querying validity time in rdf and owl: A logic-based approach[END_REF][START_REF] Papavasileiou | High-level change detection in rdf(s) kbs[END_REF][START_REF] Plessers | Understanding ontology evolution: A change detection approach[END_REF]. In this framework, work have been proposed, mainly aiming at helping to discover trends and detect changes.

Moreover, works do not often provide implemented and scalable systems. When dealing with implementation strategies, [START_REF] Khurana | Efficient snapshot retrieval over historical graph data[END_REF] introduces an original model for temporal graph change study. [START_REF] Ren | On querying historical evolving graph sequences[END_REF] proposes an approach for e#fficiently computing graph queries (such as shortest path) through several snapshot graphs.

[12] explores the possibility to use NoSQL databases for processing large RDF repositories and shows the interest of such frameworks. In these works, authors focus on the indexing of historical information stored in successive snapshots in order to optimise query performance but do not provide a full system for storing and maintaining historical views.

By analyzing the different types of history management systems in databases, we have extracted some criteria that we believe a historisation management system on a graph databases system should have to work and more over be adopted in the NoSQL database framework.

For this purpose, we both rely on the very rich literature and on our knowledge in software architecture and implemented industrial systems. In the next section, we detail the main characteristics a system for NoSQL graph databases must fulfil to be considered as managing history.

HNTP Criteria

We aim at proposing a framework for representing historical NoSQL graph databases that allows to maintain and query the system. We thus propose to extend the model. In this section, we discuss the main criteria such a solution must fulfil.

The main criteria we propose are the HNTP ones, detailed below,

• H standing for History,

• N standing for Non-Intrusivity,

• T standing for Time-independence,

• P standing for Pluggability.

History

History refers to the maintenance of successive states of the system.

In NoSQL graph databases, changes can occur on both nodes and relationships, on the levels of their existence and of their properties. This can thus result in changes on both the level of the graph structure (by adding/deleting nodes and relations) and the level of values (by adding/deleting key-value information).

For example, Fig. 3 reports the following changes between two transactions, T1 and T2 representing the state of an organization:

• the age of the node has moved from 28 to 29;

• the node of entity number 32 has been deleted together with the two incoming relationships;

• the node of entity number 28 has been added together with a relationship from John who is acting as a member at the rank of Director in this entity; IJRIT

• a relationship between John and Bill as been added as Friend.

For efficiency reasons, both at the semantic and performance levels, it is more suitable to avoid only keeping successive timestamped snapshots. We thus suggest that timelines are maintained to follow every node and relation. On the previous example, it is indeed not the same to consider that the node of the entity number 32 has been deleted and entity of number 28 has been added or to consider that the node of entity number 32 has changed to number 28, as described in Fig. 4. IJRIT This question has already been studied in databases [START_REF] Abiteboul | Procedural and declarative database update languages[END_REF], but is still important in our context.

Such timelines are important. Managing unique identifiers in graph databases is a key challenge for this purpose. In Neo4j for instance, node identifiers are unique but the system reuses its internal identifiers when nodes and relationships are deleted, which means that we cannot yet easily rely on identifiers.

On top of such basic operations, high level changes must be considered. For instance, a system must provide a way to get the difference between two versions of a graph in time. Although it is not possible to list in an exhaustive manner all the high level operations, this type of history tracking relies on graph diff operations as studied in the field of graph theory and change detection.

To sum up, history must be maintained at the three levels of node, relationship and graph. The system should also provide a way to track context informations about every version (e.g., who, what, when, why).

This point is important as it is essential to answer to some legal queries, or to study the dynamic of networks.

Non-intrusivity

Although we aim at tracking successive states of the system, the system itself may not be historical by nature. For instance, when managing an organization, the important information for daily life is embedded in the current snapshot: IJRIT

• who is managing whom?

• who is heading what?

• what is the position of X?

• who is working with Y?

• etc.

We thus aim at keeping the developers, designers and end-users out of the process of managing history.

For this purpose, we consider that the system must not interfere:

• neither at the technical level,

• nor at the conceptual level.

At the technical layer, the system must work without the need for developers to modify code unless they want to get some history support functionality.

At the conceptual layer, the system must not have any impact on the graphs conceptual structure.

Temporal Independence

Non-intrusivity guarantees that the users do not have to take care of the management of history.

The user must also be able to decide when changes must be tracked or not. For this purpose, the system must be able to run with and without history management.

We introduce thus the so-called temporal independence criterion. The more representative illustration of such a criterion is when the system runs for a while without tracking changes and must at some time start managing history.

Pluggability

As discussed in [START_REF] Castelltort | Representing history in graph-oriented nosql databases: A versioning system[END_REF], the history can be either stored as a separate graph or as a subgraph, depending on the choices to maintain the current version in a smaller and faster system or to maintain the whole information (current and past versions) in a single equally-performant system.

Whatever the choice, the system should be distributed as a library or plugin, thus avoiding the management of history and avoiding to oblige developers to change existing source codes. This library will be responsible for managing all events leading to an action of historization.

As described in the non-intrusivity criterion, the existing system must not be changed. The library will thus rely on hooks in the existing system so as to trigger actions in its inner code. Such hooks are commonly implemented in the NoSQL graph databases, as for instance the ones from Neo4j.

The links between the criteria are discussed in the next section.

Discussion

The criteria proposed above have been introduced in an implemented architecture described in [START_REF] Castelltort | Representing history in graph-oriented nosql databases: A versioning system[END_REF]. There has been one initial version rev:0 and 2 successive states rev:1 and rev:2, all these 3 labels pointing on the whole graph version. The Rev node has only one outgoing relationship pointing out to the current version of the graph. In this proposition, timelines are respected. Graph versions can be directly queried by following one red path, while nodes can be queried by following some blue path, and relationships by following some green path.

Links with Other Criteria

The management of history is not new, even for graph data. However, no system has yet been implemented in the specific context of NoSQL graph databases, making our proposition original.

NoSQL databases are indeed quite different from regular relational database engines and concepts. Data are modelled and indexed in a different manner. ACID criteria have first been mentioned as being non mandatory in NoSQL systems, leading to the cocalled CAP theorem (Consistency, Availability, Partition Tolerence) [START_REF] Brewer | Towards robust distributed systems[END_REF].

However, some current NoSQL engines are not restricted to CAP criteria.In particular the NoSQL Neo4j engine offer ACID properties. IJRIT

As mentioned above, the HNTP criteria lead to a transparent system of historization. This transparency must thus not interfere with any other criterion such as those from the ACID and CAP concepts. They thus are compatible with ACID and CAP criteria.

Links between Criteria

Some of the HNTP criteria may appear as being linked or even redundant, which is not the case.

For instance, non-intrusivity and pluggability are not linked and may occur in a system in an independent manner (one without or with the other one).

However, history is mandatory and transparency should be guaranteed to the users at the condition that the three criteria N, T and P are fulfilled.

Queries

The H-History criterion guarantees that the information is kept to follow the graph successive versions from three points of view (node, relationship and graph).

On top of this, we argue that all types of queries can be run. Low-level queries will be easily answered by following basic operations on nodes or relationships. Such queries are for example:

• What are the successive Degrees of People X?

• Who were the friends of the friends of X last year?

High-level queries will be as well treated by looking down at the node and relationship level. Such queries may for instance aim at studying dynamic networks, to detect trends.

It should be noted that the fulfilment of the four HNTP criteria implies to manage history independently from the query types. It is indeed impossible to design a data structure devoted to historical queries because of the Non-intrusivity criterion.

Regarding NoSQL Neo4j graph databases, the impact on the three ways of querying the data are somehow comparable:

• either the languages (should it be declarative or functional, or even rely on programmatic functions through API) are extended ; • or the user is aware of the implementation of history tracking in order to explicitly traverse historical data.

We recommend that the languages are extended in order to offer better performances with underlying efficient implementations and to fulfil the non-intrusivity criterion.

Conclusion

In this paper, we discuss the criteria a system must fulfill in order to manage history in NoSQL graph databases. Graphs are pervasive and established in various and numerous areas. Such data have attracted IJRIT much attention in the last years, especially because of the Web 2.0 (XML, social and media networks etc.) and the arriving Web 3.0 concepts. We focus in this paper on the management of change.

In further work, we aim at study the extension of query languages for traversing graph NoSql databases, including extensions to fuzzy queries.

Fig. 5

 5 Fig.5shows how successive versions of nodes, relationships and graph are maintained.


Arnaud Castelltort

Anne Laurent

Representing History in Graph-Oriented NoSQL DataBases: A Versioning System

Graph databases are taking more and more importance, especially for social networking. For instance, organizations can implement graph databases to represent and query data such as Person1 is CEO of Organization1. NoSQL graph databases (e.g., Neo4j) have been designed to deal with such data. However, managing history is not yet possible in an easy manner while being critical in many applications. Tracking changes is indeed one of the main functionalities in databases (especially Relational BD) and should not be forsaken in NoSQL graph DB. For instance, queries like "list all the people who have been CEO of Organization1" or "list all the functions People1 has been taken in his career" are important. In this paper, we thus propose a novel representation of historical graph data and tools to implement it as a plug-in of existing NoSQL graph systems.

I. INTRODUCTION

Graph databases are becoming more and more important as their use is increasing for managing data within applications such as social networks. In this context, they indeed propose a scalable and easy-to-use environment [START_REF] Cattell | Scalable SQL and NoSQL data stores[END_REF], [START_REF] Han | Survey on nosql database[END_REF]. For instance, they allow to represent organizations with their people, structures and links between these entities, as described in Fig. 1. Graph databases are becoming popular as they provide a robust solution for facing big data and as they allow to focus more on relations betweens objects rather than on the objects themselves, as it is the case in social networking. Many work have been proposed in the literature of databases to deal with history [START_REF] Kupfer | Keeping track of changes in database schemas and related ontologies[END_REF], [START_REF] Chawathe | Representing and querying changes in semistructured data[END_REF], [START_REF] Chawathe | Meaningful change detection in structured data[END_REF]. However, very few of them have addressed historization for NoSQL databases. Some works have studied and implemented solutions for some of the products (e.g., versioning modules for Mon-goDB, CouchDB's "Simple Document Versioning"...). To Arnaud Castelltort and Anne Laurent are with the Univ. Montpellier 2, LIRMM, CNRS UMR5506, France (email: firstname.lastname@lirmm.fr).

the best of our knowlege, graph-oriented databases do not provide such modules. We thus propose a novel approach for dealing with this challenge. For this purpose, we provide in this paper the necessary definitions and methods.

The rest of the paper is organized as follows. Section II recalls the seminal definitions related to graph-oriented databases. Sections III and IV introduce our proposal for representing history in the context of graph-oriented databases, which is discussed in Section V. Section VI concludes and presents the future work.

II. PRELIMINARY DEFINITIONS

Graph oriented databases are based on directed graphs [START_REF] Angles | Survey of graph database models[END_REF], [START_REF] Reutter | A formalism for graph databases and its model of computation[END_REF], [START_REF] Robinson | Graph Databases[END_REF]. Formally, a graph is a representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges. A set of vertices and the edges that connect them is said to be a graph.

A. Defining Graphs

This paper considers the classical definitions given below. Definition 1 (Graph): A graph G is given by a pair (V, E) where V stands for a set of vertices and E stands for a set of edges with E ⊆ (V × V ).

Definition 2 (Directed Graph): A directed graph G is given by a pair (V, E) where V stands for a set of vertices and E stands for a set of edges with E ⊆ {V × V }. That is E is a subset of all ordered permutations of V element pairs.

B. Defining Graph Databases: A Topic-Oriented Point of View

The structure a graph takes in the real-world determines the efficiency of the operations that are applied to it. It is exactly those efficient graph operations that yield an unconventional problem-solving style.

In this section, we introduce our conceptual representation of the different elements of a graph database independently on the implementation library which will be chosen.

Definition 3 (Property): A property p is a (key, value) pair where the key is a string identifier and the value is a set of elements of a given type, this element being possibly reduced to one element, the null element being forbidden.

The type of the elements can be string, int, bool, etc. Null values can be modeled by the absence of a key.

Nodes form a graph when being linked with relationships. They are often used to represent entities and can contain properties as illustrated on Fig. 3. In our vision, a node is not only defined by its properties, but also its incoming and outgoing relationships. This allows to improve traversal between nodes [START_REF] Rodriguez | The graph traversal pattern[END_REF].

Definition 4 (Node): A node n is defined as a pair (id n , P n ):

• id n is an identifier, • P n is a set of properties. It should be noted that the id does not contain any semantical information and is not unique over time within a graph. It can indeed be recycled after node's deletion to be reused for a new node. Relationships between nodes are a key part of a graph database. A relationship connects two nodes, and is guaranteed to have valid start and end nodes. As relationships are always directed, they can be viewed as outgoing or incoming relative to a node, which is useful when traversing the graph.

Relationships are equally well traversed in any direction. This means that, you can ignore the direction where it is not useful in your application. There is no need to add duplicate relationships in the opposite direction (with regard to traversal or performance). Just like nodes, relationships have properties as illustrated on Fig 4 and defined below.

Definition 5 (Relationship): A relationship R is defined as a 5-tuple (id R , n iR , n oR , T R , P R ) where:

• id R is an identifier,

• n iR is the id of the incoming node,

• n oR is the id of the outgoing node, • T R is the type of R, • P R is a set of properties. It should be noted that start (incoming) n iR and endpoint (outgoing) n oR nodes can be the same (a node can have relationships to itself).

A node can easily be linked to its incoming and outgoing nodes by considering the relationthips connected to it. Graph databases implement these features very efficiently [START_REF] Rodriguez | The graph traversal pattern[END_REF].

III. GRAPH VERSIONING

This section presents our proposition to design and implement a versioning system on graph databases. We define the following criteria that must be met by the versioning solution:

• Non-intrusivity criterion -At the technical layer, the system must work without the need for developers to modify code unless they want to get some history support functionality. -At the conceptual layer, the system must not have any impact on the graph's structure.

• Pluggability criterion

The system should be distributed has a library or plugin.

• Temporal independance criterion The system must be pluggable at any moment (at project launching or after a while in production) like a "Plug and Play" device.

• History support criterion -The system must provide a way to get history of a node or a relationship. -The system must provide a way to get the difference between two versions of a graph in time.

-The system should provide a way to track context informations about every version (e.g., who, what, when, why) if asked.

Before introducing the system, we propose some terms and ideas.

A. Preparatory Statements

This section aims at presenting the use cases we have targeted and at defining the language and terms we are using.

1) Historical Points of View:

We first claim that history must be considered as being highly linked with some point of view. We do not consider history as a stand-alone concept, but rather consider history of objects.

For this purpose, we distinguish three types of history, namely:

• The history from the node point of view, that is the entity point of view, to see the changes that have occurred on the entity itself. (e.g., on a Person point of view, searching for changes on marital status over time or on jobs held); • The history from the relationship point of view, to see the changes to the relation including start or end node updates.(e.g., on the relationship "President" point of view, searching the last ten presidents); • The history from the Graph point of view, to see the change on the graph itself.(e.g., on a Human Resources Graph point of view, searching for the differences between two dates to establish turnover).

2) Versioning Point of View: Our proposal is based on the idea that versioned data have not to be stored in the same modelisation way than the operational data. Thus, we provide a separation between the operational graph data and the management of the sequence of versions over time. For this purpose, we consider the following concepts.

B. VersionGraph Structure

For understanding sake, we explain our proposal using a very simple graph as shown in Fig. 5. Here are two real world use cases:

• changing a job title (i.e. defining a new type for the relation) This property is a logical entites' tracer for tracking their history, so that the type of an element can change, be deleted or recreated, without the risk of losing its history. The developer does not need to implement this uuid by herself. A trigger/handler system on the database can do it for her.

The algorithm is simple, as described in Algorithm 1.

Algorithm 1: OnElementCreation(Element X) if !exists(X.rev-uuid) then X.rev-uuid = generateU U ID() V G.CreateV ersionN ode(X) end if V G.CreateRevisionN ode(X)
This algorithm creates a rev-uuid for every new element except if the new element is created with an rev-uuid.

This case can happen when binding a new element on an already existing history. For example, if we replace a (A) -

IV. ANATOMY OF VERSIONGRAPH

A. Formal Definitions

GraphRevision. For every new revision, the VersionGraph is only increased by the modified elements. Every transaction or action (if no transaction support is implemented in the graph database) creates a new version of the Data Graph which is materialized by a revision in the VersionGraph.

The new revision contains both the newly modified elements and the ones that have not been modified from the previous revision. As a result, every revision is a complete snapshot of the Data Graph taken at a given time.

There are two ways to modelize a GraphRevision: 1) as a node pointing to all the RevisionElements included in the GraphRevision, 2) as a label stored in every RevisionElement included in the GraphRevision ( labels being a new feature available in some graph databases). In order to remain in the most general level, our modelisation relies on the first case.

Definition 6 (GraphRevision): The GraphRevision node is defined as a node n = (id n , P n ) where:

• P n contains: The revision root node is the startpoint to traverse data graph by revision. Every revision can be seen as a subgraph that has the semantic information available in Data Graph at a time. TraceElement. Every element of a Data Graph is represented by a TraceElement in the VersionGraph.

Definition 7 (TraceElement): Given an element e of the DataGraph, a TraceElement is a node n e = (id n , P n ) where:

• P n contains meta-information such as tracking launch date, last modified date, number of revision nodes, last graph revision number to enable fast access to some statistical information and usefull data; • P n contains a property rev-uuid mapped with e.revuuid; • there exists a unique relation starting from n and ending to the last RevisionElement.

The set of properties of a node may change over time, this information is not set on the TraceElement but on RevisionElement. RevisionElement. There are differencies between the implementation of RevisionElement's nodes and relations.

Definition 8 (RevisionElementNode): Given a TraceEle-mentNode t = (id t , P t ) tracking a DataGraph node, a RevisionElementNode is a node n t = (id n , P n ) where:

• P n contains all the properties of the DataGraph element related to t; • P t also contains:

the date of creation of n; a version number, the value is RevisionElement.revisionNumber + 1; the set of all pairs (rev-uuid, relation type) from the relations ending to or starting from of the DataGraph element related to t;

• there exists at most one outgoing relationship from n that points to another RevisionElementNode; • there exists a unique ingoing relation on the version graph Revision. Definition 9 (RevisionElementRelation): Given a TraceElementNode t = (id t , P t ) tracking a DataGraph relation, a RelationElementRelation is a node n = (id n , P n ) where:

• P n contains all the properties of the DataGraph element related to t; • P n contains:

the date of creation of n; a version number, the value is RevisionElement.revisionNumber + 1; the rev-uuid of the incoming node of the Data-Graph element related to t; the rev-uuid of the outgoing node of the Data-Graph element related to t. It should be noted that the startNode and endNode are in the RevisionElement and not in TraceElement because they can change over time. Also, the root element of a chain of RevisionElements is always the TraceElement they are related to.

B. Deployment Architecture

The VersionGraph system proposed in this paper can be deployed in two main different ways:

1) as a full graph in a separate graph database, 2) as a subgraph of the graph database. First, Graph Database can have a huge size and can be hosted on high avaibility infrastructures with a high cost to support a huge traffic. VersionGraph will be bigger than DataGraph. If the use of Version data needs less traffic, it can be hosted on a lower cost infrastructure with higher disk capacity.

Second, VersionGraph holds all the versions of the Data Graph including the current Data Graph revision. Based on this, all the queries on historization can be computed independently on the main data system.

The main drawback is that the consistency between the two graphs has to be maintained. This means that for every transaction on the Data Graph database, the new graph revision on the VersionGraph must be created in the other database.

On the one hand, this can be managed in a synchronous way. However, performance issues may occur.

On the other hand, if managing this as a failover asynchronous way, the system complexity may increase, and consistency may not be guaranteed between DataGraph and VersionGraph at any time. 2) Version Graph as a Subgraph of DataGraph: In this case, only one database is used. This solution has the advantage to allow mixing common queries with version queries and to ensure consistency. However, all version queries will have an impact on the load of the overall system.

To simplify query conception, a link can be added between every node and the equivalent VersionElement and then the history can easely be traversed: X.version.previous returns the first RevisionElement of the node X Also, as presented previously, the storage space must be provisioned to support both DataGraph and VersionGraph. This should be at least more than two times DataGraph requirement size.

V. CRITERIA MATCHING Section III-B introduces the criteria that should be matched by a graph versioning system. In this section, we discuss our proposal regarding its complience with all these criteria.

A. Non Intrusivity criterion

The version graph proposal is independent of the Data-Graph structure, then it is not necessary to adapt the graph's structure to support historization. Futhermore, the system will work unobtrusively without any change to the existing projet code as it is using a system of trigger/handler to build the VersionGraph without the need for developers to change requests nor to update code.

B. Pluggable criterion

Depending on graph implementation system, this system will be packaged as a plugin or as a set of trigger orders to be stored in the graph database engine. Deploying the system as a self package plugin seems to be a far better approach whenever possible.

C. Temporal independance criterion

The version graph system proposal could be installed at any moment. When starting the version graph system the first time, it will scan all nodes and relations. For each element (node, relation) it will add a rev-uuid in DataGraph and will make a TraceElement and a first RevisionElement to make GraphRevision 0 in VersionGraph. Starting from this point, every transaction will lead to a new revision .

Our system can be plugged at anytime:

• at project launch, there will be no available element (if an empty database does not require a root Node). As a consequence, the first Revision in the VersionGraph will not have any element. • at any moment, the VersionGraph can be constructed and after it, the VG Revision 0 will have every element at the installation time of the version graph system.

D. Historization features criterion

As shown in Fig. 14, three kinds of traversal can be adressed by the version graph system. We will go deeper on this subject in a futher work.

VI. CONCLUSION AND FURTHER WORK

In this paper, we address data historization in the context of graph-oriented NoSQL databases. Although being crucial, changes tracking is not yet available in such databases. We thus propose a novel approach, by both studying what historization means in such a context, and by proposing representations and methods to manage history.

Fig. 1 .

 1 Fig. 1. Example of Graph Data: The Matrix Neo4j Database

Fig. 2 .

 2 Fig. 2. Graph of Graph Organization

Fig. 3 .

 3 Fig. 3. Node Properties

Fig. 4 .

 4 Fig. 4. Relationship Properties

•

  DataGraph: the current graph in use • Transaction: a set of operations which either all occur, or nothing occurs on the DataGraph. A guarantee of atomicity prevents updates to the graph occurring only partially, which can cause greater problems than rejecting the whole series outright • Revision: Every transaction makes a new version of the graph, termed revision • VersionGraph: A VersionGraph stores the history of different versions of a data graph. The VersionGraph model does not depend on the DataGraph architecture choice, as explained later in this paper.

Fig. 5 .

 5 Fig. 5. Simple Graph Model The graph from Fig. 5 is only made of 3 nodes (A, B, C) and three relations (R1, R2, R3).

1 )

 1 Sample Graph Model representation in Version Graph:To manage the history of the Data Graph 'DG, a Version-Graph 'VG is built as shown inFig 6.

Fig. 6 .

 6 Fig. 6. Version Graph Model

Fig. 7 .

 7 Fig. 7. Edit a node Property

Fig. 8 .

 8 Fig. 8. Data Graph : Deleting R2

Fig. 9 .

 9 Fig. 9. VersionGraph: Deleting R2

3 )

 3 Tracking a Relation: In relational databases, relationships' attributes are used in flat tables to represent incoming and outgoing links. Then, this information can easily be updated. By contrast, in graph databases, only properties can be modified on the relationship. There is no update order on relationship start/end node because a relationship cannot exist without both start and endpoint. Such an update is then handled by deleting the existing relationship and creating a new one. 4) Tracking a Relationship When Changing the Start or End Point: In the transaction 3, a new relation is created between C and B of type R2. We want this relation to be tracked as a new version of the initial relation R2 from A and B of the first revision.

Fig. 10 .

 10 Fig. 10. DataGraph: Adding a new R2 type relation with history tracking

Fig. 11 .

 11 Fig. 11. VersionGraph: Adding a new R2 type relation with history tracking

Fig. 12

 12 Fig. 12. Graph Properties

Algorithm 2 :

 2 Fig. 13 depicts the Data graph enhanced by the rev-uuid.

Fig. 13 .

 13 Fig. 13. Revision uuid

Fig. 15 .

 15 Fig. 15. Revision implementation as label or node

Fig. 14 .

 14 Fig. 14. Point of view in VersionGraph

1 )

 1 VersionGraph as a Separate Graph Database: Separating the operational and historical graph databases has several advantages.

Fig. 16 .

 16 Fig. 16. Version Graph as a separate graph database

Fig. 17 .

 17 Fig. 17. Version Graph as a subgraph of DataGraph

Further work include the implementation of our solution, which should be realized using a Neo4j graph database. Moreover, queries over historical graph databases will be studied. We are also studying the reduction of the number of revisions by a squashing system.


Internet of Things for Efficient Wildlife Conservation: Challenges and Opportunities

Charith Perera (PI), Omer Rana, Benoît Goossens, Pablo Orozco Ter Wengel Danau Girang Field Centre (DGFC) is located in Sabah Malaysia (marked in Figure 1). The only access to the field centre is through the river. Similarly, all the research activities are conducted by going through the river. It is worth noting that Sabah Malaysia is a high humidity region where electronic components could get damaged quite quickly due to environmental factors such as moisture. Further, in jungle terrains, insects could also get attracted to copper within electronic components. We need to keep in mind this context when we are addressing the challenges. We conducted a two full-day workshop to explore and identify research challenges that could potentially be addressed using the Internet of Things (IoT) technologies. During this workshop, we identified two major areas to focus on:

(1) Sensing Infrastructure, and (2) Data Science. Additionally, we also discussed citizen engagement research, where we could work with local schools and universities to share our technical expertise with the local community. In the long term, such activities will help local communities to develop technologies to solve their own problems.

Sensing Infrastructure Challenge 1: Trap Activation Detection

Catching animals and tagging them is a common task in wildlife conservation activities and bioscience research. Let examine the process of catching and tagging animals. First researchers need to develop different types of traps, as shown in Figure 2. Each trap is typically custom-designed to target a specific type of animal-based on their characteristics. The next step is to deploy these traps in areas where the targeted animal wander around. Typically, there is a significant distance between the deployment location and the field centre. Furthermore, at a given time, there could be more than 20 traps deployed within the sanctuary. Typically, the research area could be 20 miles from each side of the field centre. Therefore, at least two staff members of the DGFC need to travel in boats and visit each of these traps across the 40-mile strip. Such visitations take a significant amount of time and effort.

Further, these visitations need to be done daily, because if an animal has been trapped, either they need to be tagged or released.

These traps are not perfect and mostly have weight-based or bait base activation triggers. Therefore random animals could also get trapped in these traps (due to similar weight or attracted to similar baits). If this is the case, staff members only need to open the trap door and let the animal go otherwise; it would die within the trap. However, if the animal is the interested targeted animal, then the DGFC staff needs to send a message to the Sabah wildlife department, and the relevant officials need to be present in order to conduct the tagging. Due to this uncertainty, DGFC staff member needs to visit each trap every day to check them manually.

We believe that technology can be developed to monitor these traps remotely and inform the field centre staff to take the necessary actions without physically visiting the trap all the time. Such remote monitoring will reduce the workload of field centre staff and enhance their capabilities. There are two levels of technology that we can develop. First, if we can identify whether a particular trap door has been activated (i.e., closed), it will help the field centre staff only to visit the trap once activated.

However in an advanced approach, if we can identify the animal remotely without visiting the trap, it would help the field centre staff to send the message to the Sabah wildlife department and ask them to come to the trap so they can perform the tagging straightaway. Such approach will save DGFC staff time as they do not need to wait near the trap until the wildlife of officials arrives due to precoordination ability (i.e., remote monitoring helps to coordinate the trap visitation efficiently).

We believe that trap door activation can be detected by a few different ways. For example, trap door activation could be detected by using different types of sensors such as vibration, noise, light, motion, and camera and so on. Further, there are two different technologies that can be used to do the communication between the traps and the field centre. For example, we could use SMS or 3G technologies. It is important to note that 3G technology only works in very few limited spots within the sanctuary due to lack of signal penetration.

Furthermore, we could use low-cost edge computing technologies to detect and identify the animal trapped within a given trap. State of the art deep learning is sophisticated enough today to be able to use in such identification. However, it is difficult to predict how these models would behave in unconstrained environments such as Sabah, where many environmental factors could affect the ability of the model to predict accurately. The lighting conditions, raining, dust, insects and many other factors could affect the camera. Therefore, deep learning models which are trained to predict within specific environmental conditions may not be able to perform as expected.

Challenge 2: Poacher Tracking

Poaching is a significant challenge in Sabah Malaysia. Anti-poaching efforts can be divided into many different areas. Two of those areas are poacher tracking and poacher detection. The objective of poacher tracking is not necessarily to stop or catch the poachers. The objective is to track how poachers behaviour and try to understand the pouching ecosystem holistically. Most of the poachers do ordinary jobs during the daytime. At night they become poachers. Poachers not only catch or kill animals, but they also sell meat to local restaurants. Then these local restaurants sometimes offer meat to unsuspecting tourists. Poachers may also sell skin and other body parts of the animals to different buyers.

The only way to stop poaching is to understand the entire ecosystem and the stakeholders and take necessary measures to discourage them all from engaging in poaching and related activities. Therefore, we need to develop technologies to track poachers' movements. Some crucial questions that need to be answered are, what are the shops poachers visit the most, on what days what time they visit these places, do the poachers meet each other, and so on. Catching one or two pouches here and there will not change the situation. One arrested poacher may be replaced by new pouches as long as the demand and the infrastructure for poaching activities present in Sabah. It is going to be difficult to stop poaching without targeting the entire stakeholders. It is challenging to track humans in areas like Sabah, where CCTV like technology is not well deployed. Therefore the better way to track poachers is through tracking their vehicles. We believe one way to achieve this is to deploy small tracking nodes (i.e., small electronic devices) that can communicate location information to the officials. Such tracking nodes can be deployed in poachers' vehicles using informants. The major characteristics of such tracking nodes are: (i) be able to collect and store data while offline, (ii) long-lasting battery life, and (iii) smaller in size.

Network communication in Sabah is a challenge, especially in jungle terrain where urban technologies such as 3G and LoRaWAN, are challenging to employ. Therefore, we believe primitive technologies such as SMS are the best way to go forward. However, we also believe that a combination of different communication technologies could be more effective. Tracking nodes that can adapt based on the context and use the most efficient communication technology are the most ideal. The challenge is that the more sophisticated the tracker node becomes, the larger it will become. Larger size tracker nodes are challenging to be deployed in poacher vehicles through informants without getting noticed.

Another challenge is that in certain jungle areas, long-range communication technologies do not work at all. In such situations, short-range communication technologies such as Bluetooth Low Energy (BLE) could be used. However, technology such as Bluetooth could be affected by environmental factors as well as humidity. Further, BLE may also require static infrastructure. Therefore, BLE will require many numbers of nodes to be deployed in many different strategic locations to track poacher vehicles.

Challenge 3: Poacher Detection

The objective of detecting poachers is to catch/arrest them. However, sometimes, poacher detection technology can also be used to track poacher the moment in a limited way. In Malaysia Sabah, poachers use two primary modes of transportation for poaching activities: four-wheel drives and boats. Most of the time, poacher may combine the two transportation mechanisms and work as teams. The following Figure 3 shows the borderline between Palm oil plantation and the sanctuary. Usually, poachers would come by a four-wheel drive and stop the vehicle within the buffer between the oil plantation and the sanctuary. Then they cross the electric fence (deployed to discourage elephants, typically switched off until elephant warning triggers) and go into the sanctuary. Then they kill or capture the animals and then get into the boats and get out through the river. Sometimes group members may come back and pick up the vehicle during the night or the next day. Typically, plantation workers or any other officials in plantations are not interested in stopping poaching neither they have any authority to do so. As plantations are very large, it is unlikely that any workers would see pouches at all. To detect poachers, we need to develop two types of technologies targeting the two types of transportations modes (i.e., vehicles and boats). Another important aspect to keep in mind is that poaching happens at night, so whatever the technology we develop should be able to work with limited lighting conditions.

Vehicles Detection: There are two levels of detection that can be done in relation to the poacher vehicles. First, it is important to detect whether there is a vehicle or not. In the sanctuary, it is prohibited for vehicles to enter (or stay) after evening (7 pm). Therefore, if there a vehicle is detected within Sanctuary during after-hours, it is fair to assume that it is a poaching vehicle. Therefore necessary actions could be taken to inform the law enforcement and wildlife officers. Further, if it is possible to detect and read the license plate pf the vehicle, it could give more evidence. A license plate number helps to decide whether a given vehicle is a poaching vehicle or authorised vehicle. For example, we can have white-listed license plate used by authorised personal. So if such an authorised license plate is detected within sanctuary during after-hours, we can ignore them. There could be many different ways to detect vehicles. For example, we could use sensors such as cameras, noise, vibration, infrared to detect vehicles. The challenge is to find out what technique works best within this area of Sabah.

Figure 4: (A demonstration only) Poacher vehicle drives along the electric fence in the buffer area

Boat Detection: As we discussed earlier, another major transportation mode used by poachers are boats. Boats come through river and park on river banks. Then the poacher would go into the jungle terrain and capture or kill the animal and come back with the animal. The difficulty of detecting poacher boats is that the fishermen also use boats to travel for fishing during the evening and night hours. Therefore, just because we detect a boat in the River, even within us afterwards, it is challenging to conclude that the boat is a poaching boat. It is also difficult to use sound sensors because most of the poaching boats, as well as fishing boats, use similar engines. Therefore, it would be challenging to detect poacher boats by only observing movements in the river. However, fishing boats have certain behaviours when they move through the river. Poachers are likely to get down from the boat on river banks.

Another approach could be to combine the data we gather from vehicle detection sensors and combine that knowledge with boat tracking data. For example, if see a pattern of both boat and vehicle moving towards a similar direction, then we could imagine based on past data that group of poachers may be working together to catch or kill animals. As we discussed earlier, most of the long-range communication technologies we use in urban areas are not working within jungle terrain, because of the obstacles such as the thick canopy and high humidity. Lack of network connectivity is one of the major issues that directly impact all other challenges. For example, we discussed trap door activation before. Even we detect trap door activation, without network communication, it is not possible to send the message to the official's ontime. Therefore, most of the time, we have to rely on technologies such as SMS, 3G or satellite communication.

Satellite communication is costly. On the other hand, 3G communication only available in certain spots within the sanctuary. Therefore, the most practical solution seems to be SMS. However, we believe that technologies such as Lora and Xbee can be utilised to develop a cheaper network. Due to obstacles such as high humidity, both Lora and Xbee technologies do not provide the performance as they would in urban cities. Therefore, we expect that the coverage these technologies provide to be much less in jungle terrains that their official specifications.

We believe that it is useful to combine these two technologies (i.e., Lora and Xbee) to develop an efficient and effective network. Lora is designed for long-range communicate (10+ Km). However, the packet size that it can transfer is quite small (few KB). Such small packets are good enough to a message from a trap door to the field centre. However, it would be difficult to send an image over a Lora network. It is ideal to have Xbee as the backbone of the network. For example, we could deploy a series of Xbee gateway node along the river bank where data would be hope from one to another. Then, the communication between the river bank and the jungle terrain can be done using Lora as depicted in Figure 6. In doing so, we could utilise best of both worlds of Lora and Xbee. Such infrastructure will help researchers to monitor different aspects of the sanctuary and animals in a much more efficient and effective manner. Camera traps are widely used in wildlife research to monitor behaviours of animals. They are typically deployed remotely and expected to be triggered by animal movements. Cameras are configured to take photographs or video. Usually, researchers are not visiting these camera traps every day. Ideally, cameras will be deployed for 1-3 weeks, and the researchers will collect them. However, it is difficult to predict when the battery would die. Most of the camera traps use rechargeable batteries. Even though some batteries get fully recharged once deployed, they tend to dry out very quickly. Sometimes, for example, a researcher may deploy a camera trap, and within one day, the battery gets dried out. However, the researcher may not know that the battery has died. Once return in a week or two, they will get disappointed to know that none of the footage has been recorded. To avoid address this issue, we need to develop technology that can at least detect and notify the researchers when the batteries are dead, because predicting battery life ahead of time is extremely difficult due to harsh environmental condition (rain, humidity). We can develop technology (contact or non-contact) to measure the voltage of the batteries and notify researchers once the voltage drops below a certain amount.

Data Science Challenge 1: Automated Camera Trap Image Annotation

As mentioned earlier, camera traps are one of the most common ways that wildlife researchers collected data about animals and their behaviours. First, researchers may deploy cameras in the wild. Then they bring the camera back to the centre and move the photos or videos from the memory chip to a computer. Then, they need to review each photo and annotate them manually with various parameters such as whether there is animal or not in the photo, what type of animal and so on. Such a review process is a challenging task, and it also takes a significant amount of time to review thousands of images.

Artificial Intelligence (AI) technologies can automatically detect animals in a given photo. Further, some AI models can recognise animal types and their behaviours as well. There are many different deep learning classifiers developed and trained by many different institutions and researchers. However, none of those classifiers is perfect. Accuracy also depends on environmental parameters as well, which affected by the image quality. We believe that the best way to go forward is to develop a method to combine these classifiers together.

One of the primary reasons that researchers do not want to use AI is that they do not want to lose any important images due to inaccuracies of AI. Therefore, when developing the technology, we need to make sure that we give researchers the full power or ability to involve in the decision-making process. Therefore, we believe the best approach is to use different AI classifiers to analyse each camera image and then present that information to the wildlife researchers to make the final decision on whether to go ahead with a certain type of annotation or not. Eventually, the wildlife researchers will learn to trust the AI. In the meantime, wildlife researchers will also get the opportunity to correct the mistake done by the AI, and then the AI will be able to learn from the researchers and improve its decisionmaking model.

The best approach would be to present the majorities decision of the AI Classifiers' as the default decision (i.e., propose annotations) to the researcher. For example, if 3 out of 4 classifiers detect an elephant in a given image, the default annotation data will be presented as an elephant to the researchers. At that time, the researcher gets the opportunity to either accept or manually alter the notation. Auch AI system could save a significant amount of time for wildlife researchers.

Another important aspect to consider is 'sensitivity of wildlife data'. As you could imagine certain images, especially with the location already tagged by the camera, could be used by bad actors to find out where are the certain type of endangered animals are living within the sanctuary. Therefore, sometimes researchers could be reluctant to use cloud-based AI systems. To address this issue, some computer science researchers have already developed classifiers that can perform data annotation without sending data to the cloud. However, with enormous computational capabilities, accuracy could be better in cloud-based AI systems. At the end its a trade-off that needs to be considered when developing such an annotation system.

Challenge 2: Semantic Data Integration for Wildlife.DATA

In most of the wildlife projects, each researcher tends to collect their own dataset and analyse and produce results. This is no different in DGFC as well. Over the past decade, they have collected many different datasets through different project by different researchers. As researcher come and go, most of these datasets are underutilised and mostly inaccessible to new researcher researchers. At DGFC, there are a few common types of projects based on the types of data they collect. One of the common data types is camera traps data. Another data type is animal collar data. Other than that some projects collect date about plants and genetic/DNA. By far the majority are the first two types of data (i.e., camera traps and animal collar data).

We believe that semantic data integration techniques can be used to combine these independently collected siloed data in a meaningful and logical manner that can be queried and retrieved easily. For example, one researcher may use camera traps to collect information about animal 'X'. However, organically those cameras may also capture animals 'Y' and 'Z'. Without semantic integration, it is very difficult to query and find out all the instances where animals Y' and 'Z' has been captured. Further, semantic data modelling and integration allows interested parties to make more sophisticated, useful, and complex queries (e.g., what are the best areas to deploy camera traps to detect a certain type of animal?). If we had all the data modelled using semantic technologies, this kind of query could be easily answered. Such queries may have spatial or temporal properties as well (e.g., what are the areas animal 'X' was detected at night?, Give me all the images where a certain type of animal has been detected during mornings from 4 to 7 am). Such granular data querying can only be provided by semantic data integration. Therefore, we believe integrated semantic platform will provide wildlife researchers significant capabilities, and make data more accessible for wider community.

Figure 1 :

 1 Figure 1: A map the region of the Kinabatangan Wildlife Sanctuary

Figure 2 :

 2 Figure 2: Differnt traps that targets differnt animals

Figure 3 :

 3 Figure 3: Buffer between palm oil plantation and wildlife sanctuary divided by an electric fences

Figure 5 :

 5 Figure 5: River where poachers use to get away after catching or killing animals

Figure 6 :

 6 Figure 6: Potential Pilot IoT Network

Figure 7 :

 7 Figure 7: At Cardiff University: From left to right: Jack Burkett (Cardiff University-COMSC), Omer Rana (Cardiff University-COMSC), Richard Wenner (The Things Network), Sergio Guerrero Sanchez (DGFC), Elisa Panjang (DGFC), Tommy Rowel (DGFC), Charith Perera (Cardiff University-COMSC) [Not in the Photo: Pablo Orozco Ter Wengel (Cardiff University-BIOSI), Penny Gardner (DGFC), Sharadha Kariyawasam (VortexIoT), Emad Aliwa (Cardiff University-COMSC)]

Supported by: iotgarage.net