Keywords:

quantication oue dans une requête est très limité par rapport au coût de l'évaluation globale.

Conclusion & Perspectives

Cette thèse est la première proposant une extension oue du langage SPARQL visant à améliorer son expressivité et à permettre i) d'interroger des bases de données RDF oues et ii) d'exprimer des préférences complexes sur la valeur des données et sur la structure du graphe. Les résultats présentés dans ce manuscrit sont prometteurs et montrent que le coût supplémentaire dû à l'introduction de conditions de recherche oues reste limité/acceptable.

De nombreuses perspectives peuvent être envisagées. Une première perspective concerne l'extension des langages FURQL et FUDGE avec des préférences plus sophistiquées dont certaines font appel à des notions provenant du domaine de l'analyse des réseaux sociaux (centralité ou prestige d'un noeud) ou de la théorie des graphes (par exemple, clique, etc).

Nous envisageons ensuite d'étudier d'autres types de requêtes quantiées plus complexes, par exemple trouver les auteurs ayant un article publié dans la plupart des revues de base de données renommées (ou plus généralement, trouver les x tels que x est relié (par un chemin) à Q n÷uds d'un type donné T satisfaisant la condition C). Les logiciels SURF et SUGAR peuvent également être améliorés an de les rendre plus conviviaux, ce qui pose la question de l'élicitation de requêtes oues complexes. Il vaut également la peine d'étudier la manière dont notre cadre pourrait être appliqué à la gestion de dimensions de qualité des données (par exemple, précision, cohérence, etc.) qui sont en général d'une nature graduelle.

List of Tables

Appendix A Sample of Queries Bibliography Résumé en français La publication de données ouvertes (éventuellement liées) sur le web est un phénomène en pleine expansion. L'étude des modèles et langages permettant l'exploitation de ces données s'est donc grandement intensiée ces dernières années.

Récemment, le modèle RDF (Resource Description Framework) s'est imposé comme le modèle de données standard, proposé par le W3C, pour représenter des données du web sémantique [W3C, 2014]. RDF est un cas particulier de graphe étiqueté orienté, dans lequel chaque arc étiqueté (représentant un prédicat) relie un sujet à un objet.

SPARQL [START_REF] Prud | SPARQL query language for RDF[END_REF] est le langage de requête standard recommandé par le W3C pour l'interrogation de données RDF. Il s'agit d'un langage fondé sur la mise en correspondance de patrons de graphe.

Les travaux que nous présentons visent à introduire plus de exibilité dans le langage (SPARQL ici) en orant la possibilité d'intégrer des préférences utilisateur aux requêtes.

Les motivations pour intégrer les préférences des utilisateurs dans les requêtes de base de données sont multiples. Tout d'abord, il semble souhaitable d'orir à l'utilisateur la possibilité d'exprimer des requêtes dont la forme se rapproche, autant que possible, de la formulation de la requête en langage naturel. Ensuite, l'introduction de préférences utilisateur dans une requête permet d'obtenir un classement des réponses, par niveau décroissant de satisfaction, ce qui est trés utile en cas d'obtention d'un grand nombre de réponses. Et enn, là où une requête booléenne classique peut ne retourner aucune réponse, une version à préférence (qui peut être vue comme une version relaxée et donc moins restrictive), peut permettre de produire des réponses proches des objets idéals visés. [START_REF] Bruno | Top-k selection queries over relational databases: Mapping strategies and performance evaluation[END_REF], Chomicki, 2002, Torlone and Ciaccia, 2002, Borzsony et al., 2001, Kieÿling, 2002, Tahani, 1977, Bosc and Pivert, 1995, Pivert and Bosc, 2012]. La littérature sur les requêtes à preférences dans le contexte de bases de données RDF n'est pas aussi abondante puisque cette question n'a commencé à attirer l'attention que récemment.

La plupart des approches existantes sont des adaptations directes des propositions faites dans le contexte des bases de données relationnelles. En particulier, elles se limitent à l'expression de préférences sur les valeurs présentes dans les n÷uds.

Dans un contexte de graphe RDF, la nécessité d'exprimer des conditions sur la structure des données, puis d'extraire les relations entre les ressources dans le graphe RDF, a motivé des travaux visant à étendre SPARQL et à le rendre plus expressif. Dans [START_REF] Kochut | SPARQLer: Extended SPARQL for semantic association discovery[END_REF], Anyanwu et al., 2007, Alkhateeb et al., 2009] et [START_REF] Pérez | nSPARQL: A navigational language for RDF[END_REF],

les auteurs étendent principalement SPARQL en permettant d'interroger RDF à l'aide de patrons de graphe en utilisant des expressions régulières. Mais dans ces approches, le graphe RDF et les conditions de recherche restent non-ous (booléens).

Le modèle RDF de base ne permet en eet de représenter nativement que des données de nature booléenne. Les concepts du monde réel à manipuler sont cependant souvent de nature graduelle. Il est donc nécessaire de disposer d'un langage plus exible qui prenne en compte des graphes RDF dans lesquels les données sont intrinsèquement décrites de façon pondérée.

Les poids peuvent représenter des notions graduelles telles qu'une intensité ou un coût. Par exemple, une personne peut être l'amie d'une autre avec un degré fonction de l'intensité de la relation d'amitié.

An de représenter ces informations, plusieurs auteurs ont proposé des extensions oues du modèle de données RDF. Cependant, les extensions oues de SPARQL qui peuvent être trouvées dans la littérature restent très limitées en termes d'expression de préférences.

Notre objectif dans cette thèse est de dénir un langage de requête beaucoup plus expressif pour i) traiter des bases de données RDF oues et non oues et ii) exprimer des préférences complexes sur les valeurs des noeuds et sur la structure du graphe. Un exemple d'une telle requête est: trouver les acteurs a tels que la plupart des lms récents où a joué l'acteur a, sont bien notés et ont été recommandés par un ami proche de a. Nos contributions principales sont décrites dans la suite.

Une extension oue de SPARQL avec des capacités de navigation oue Notre objectif dans la première contribution est d'étendre le langage SPARQL de façon à lui permettre d'exprimer des préférences utilisateur pour exprimer des requêtes exibles, portant sur des données RDF véhiculant ou non des notions graduelles.

Tout d'abord, nous proposons une extension de la notion de patron de graphe, fondée sur la théorie des ensembles ous, que l'on nomme patron ou de graphe. Cette extension repose sur celle de patron de graphe SPARQL introduite dans [START_REF] Pérez | Semantics and complexity of SPARQL[END_REF] et [START_REF] Arenas | Querying semantic web data with SPARQL[END_REF]. Dans ces travaux, les auteurs dénissent un patron de graphe SPARQL dans un formalisme algébrique plus traditionnel que le formalisme introduit dans la norme ocielle. Un patron de graphe est récursivement déni comme étant soit un graphe contenant des variables, soit un graphe complexe obtenu par l'application d'opérations sur des patrons de graphe.

Ensuite, on nous fondant sur cette notion de patron ou de graphe, nous proposons le langage FURQL qui est plus expressif que toutes les propositions existantes de la littérature, et qui permet: 1. d ( [START_REF] Mazzieri | A fuzzy semantics for semantic web languages[END_REF], Udrea et al., 2006, Mazzieri and Dragoni, 2008, Lv et al., 2008, Straccia, 2009, Udrea et al., 2010, Zimmermann et al., 2012]), dont le principe commun consiste à ajouter un degré dans [0, 1] à chaque triplet RDF, formalisé ou bien par l'encapsulation d'un degré ou dans chaque triplet ou bien par l'ajout au modèle d'une fonction associant un degré de satisfaction à chaque triplet (ces deux représentations sont sémantiquement équivalentes et présentent la même expressivité).

Un degré attaché à un triplet s, p, o exprime à quel point l'objet o satisfait la propriété p sur le sujet s. Préférences oues Le langage FURQL est basé sur des patrons ous de graphe qui permettent d'exprimer des préférences oues sur les données d'un graphe ou F-RDF via des conditions oues (par exemple, l'année de publication d'un lm est récente ) et sur sa structure via des expressions régulières oues (par exemple, le chemin entre deux amis doit être court ).

Syntaxiquement, le langage FURQL permet d'utiliser des patrons ous de graphe dans la clause where et des conditions oues dans la clause filter. La syntaxe d'une ex-pression oue de graphe est proche de celle de chemin, comme déni dans SPARQL 1.1 [Harris and Seaborne, 2013], permettant d'exhiber des n÷uds reliés par des chemins exprimés sous forme d'une expression régulière. On permet ici l'expression d'une propriété oue portant sur les n÷uds reliés. Une propriété d'un chemin concerne des notions classiques de la théorie des graphes ous [Rosenfeid, 2014] : la distance et la force de la connexion entre deux n÷uds, où la distance entre deux noeuds est la longueur du plus court chemin entre ces deux noeuds et la distance d'un chemin est dénie comme étant le poids de l'arc le plus faible du chemin.

Ce travail a été publié dans les actes de la 25ème Conférence internationale IEEE sur les systèmes ous (Fuzz-IEEE 16), Vancouver, Canada, 2016.

Requêtes quantiées structurelles oues dans FURQL La deuxième contribution traite de requêtes quantiées oues adressées à une base de données RDF oue. Les requêtes quantiées oues ont été étudiées de façon approfondie dans un contexte de bases de données relationnelles pour leur capacité à exprimer diérents types de besoins d'information imprécis, voir notamment [START_REF] Kacprzyk | FQUERY III +:a "human-consistent" database querying system based on fuzzy logic with linguistic quantiers[END_REF], Bosc et al., 1995], où elles servent à exprimer des conditions sur les valeurs des attributs des objets stockés.

Cependant, dans le cadre spécique de RDF/SPARQL, les approches actuelles de la littérature traitant des requêtes quantiées considèrent des quanticateurs non-ous uniquement [START_REF] Bry | SPARQLog: SPARQL with rules and quantication[END_REF], Fan et al., 2016] sur des données RDF non-oues.

Nous étudions une forme particulière de requête quantiée oue structurelle et montrons comment elle peut être exprimée dans le langage FURQL déni précédemment. Plus précisement, nous considérons des propositions quantiées oues du type QB X are A sur des bases de données RDF oues, où Q est le quanticateur qui est représenté par un ensemble ou et est soit relatif (par exemple, la plupart) soit absolu (par exemple, au moins trois), B est une condition oue, X est l'ensemble de noeuds dans le graphe RDF, et A désigne une condition oue. Un exemple d'une telle proposition quantiée oue est : la plupart des albums récents sont très bien notés. Dans cet exemple, Q correspond au quanticateur ou relatif la plupart, B est la condition oue être récent, X correspond à l'ensemble des albums présents dans le graphe RDF et A correspond à la condition oue être très bien noté.

Conceptuellement, l'interprétation d'une telle proposition quantiée oue dans une requête FURQL peut être basée sur l'une des approches de la littérature proposées dans [Zadeh, 1983, Yager, 1984, Yager, 1988]. Son évaluation comporte trois étapes:

1. la compilation de la requête quantiée oue R en une requête non-oue R , 2. l'interprétation de la requête SPARQL R , 3. le calcul du résultat de R (qui est un ensemble ou) basé sur le résultat de R .

Ce travail a été publié dans les actes de la 26ème Conférence internationale IEEE sur les systèmes ous (Fuzz-IEEE'17), Naples, Italie, 2017.

Mise en ÷uvre et expérimentation

Dans cette thèse, nous abordons également l'implantation du langage FURQL. Nous avons à cet eet considéré deux aspects:

1. le stockage de graphes ous (modèle de données étendu que nous considérons) et 2. l'évaluation de requêtes FURQL.

Le premier point peut être résolu par l'utilisation du mécanisme de réication qui permet d'attacher un degré ou à un triplet, solution proposée dans [Straccia, 2009].

Concernant l'évaluation de requêtes FURQL, nous avons développé une couche logicielle permettant la prise en compte de requêtes FURQL, que l'on associe à un moteur SPARQL standard. Cette couche logicielle, appelé SURF, est composée principalement des deux modules suivants:

• Dans une étape de prétraitement, un module de compilateur de requête FURQL produit les fonctions dépendantes de la requête qui permettent de calculer les degrés de satisfaction pour chaque réponse retournée, une requête SPARQL classique qui est ensuite envoyée au moteur de requête SPARQL pour récupérer les informations nécessaires pour calculer les degrés de satisfaction.

La compilation utilise le principe de dérivation introduit dans [START_REF] Pivert | Fuzzy Preference Queries to Relational Databases[END_REF] dans un contexte de bases de données relationnelles qui consiste à traduire une requête oue en une requête non oue.

• Dans une étape de post-traitement, un module de traitement des données oues qui calcule le degré de satisfaction pour chaque réponse renvoyée, classe les réponses et les ltre qualitativement si une alpha-coupe a été spéciée dans la requête oue initiale.

Une preuve de concept de l'approche proposée, le prototype SURF, est disponible et téléchargeable à l'adresse https://www-shaman.irisa.fr/furql/.

Pour évaluer les performances du prototype SURF que nous avons développé, nous avons eectué deux séries d'expériences sur diérentes tailles de bases de données RDF oues. Les premières expériences visent à mesurer le coût supplémentaire induit par l'introduction du ou dans SPARQL, et les résultats obtenus montrent l'ecacité de notre proposition. Les deuxièmes expériences, qui concernent des requêtes quantiées oues, montrent que le coût supplémentaire induit par la présence d'un quanticateur ou dans les requêtes reste très limité, même dans le cas de requêtes complexes.

Requêtes quantiées structurelles oues dans FUDGE

A la n de cette thèse, nous nous situons dans un cadre plus général: celui de bases de données graphe [START_REF] Angles | Survey of graph database models[END_REF]. Jusqu'à présent, une seule approche de la littérature, décrite dans [START_REF] Castelltort | Fuzzy queries over NoSQL graph databases: Perspectives for extending the Cypher language[END_REF], considère des requêtes quantiées oues dans un tel environnement, et seulement d'une manière assez limitée. Une limitation de cette approche tient au fait que seul le quanticateur est ou (alors qu'en général, dans une proposition quantiée oue de la forme QB X are A, les prédicats A et B peuvent également l'être).

Nous proposons quant à nous d'étudier des requêtes quantiées oues impliquant des prédicats ous (en plus du quanticateur) sur des bases de données graphe oues. Nous considerons le même type de requête quantiée oue structurelle que celui considéré dans FURQL mais dans un cadre plus général. Cette contribution est basée sur notre travail décrit dans [Pivert et al., 2016e], dans lequel nous avons montré comment il est possible d'intégrer ces requêtes quantiées oues dans un langage nommé FUDGE, précédemment déni dans [Pivert et al., 2014a]. FUDGE est une extension oue de Cypher [START_REF] Cypher | Cypher[END_REF] qui est un langage déclaratif pour l'interrogation des bases de données graphe classiques.

Une stratégie d'évaluation fondée sur un mécanisme de compilation qui dérive des requêtes classiques pour accéder aux données est également décrite. Elle s'appuie sur une surcouche logicielle au système Neo4j, baptisée SUGAR, dont une première version, décrite dans [Pivert et al., 2015[START_REF] Pivert | SUGAR: A graph database fuzzy querying system[END_REF], permet d'évaluer ecacement les requêtes FUDGE ne comportant pas de propositions quantiées. A cet eet, nous avons mis à jour ce logiciel, qui est une couche logicielle qui implémente le langage FUDGE sur le SGBD Neo4j, pour lui permettre d'évaluer des requêtes FUDGE contenant des conditions quantiées oues.

Comme preuve de concept de l'approche proposée, le prototype SUGAR est disponible et téléchargeable à l'adresse www-shaman.irisa.fr/fudge-prototype.

An de conrmer l'ecacité de l'approche proposée, nous avons eectué quelques expérimentations avec le prototype SUGAR en utilisant diérentes tailles de bases de données graphe oues. Les résultats obtenus sont prometteurs et montrent que le coût du traitement de la

Introduction

The relational model, introduced in 1970 by Edgar F. Codd [Codd, 1970], has been the most popular model for database management for many decades in academic, nancial and commercial pursuits. In this framework, data can be stored and accessed thanks to a database management system like Oracle, Microsoft SQL Server, MySQL, etc.

However, in the recent decades, the traditional relational model faced new challenges, mainly related to the development of Internet. Data to be searched are more and more accessible on the Web (i.e., open environment) and never stop to increase in volume and complexity.

As a solution, an alternative model, called NoSQL (Not only Structured Query Language), came to existence and has attracted a lot of attention since 2007. It aims to process eciently and store huge, distributed, and unstructured data such as documents, e-mail, multimedia and social media [Leavitt, 2010, Robinson et al., 2015].

Among NoSQL database systems, we may nd the famous Google's BigTable [START_REF] Chang | Bigtable: A distributed storage system for structured data[END_REF]], Facebook's Cassandra [START_REF] Lakshman | Cassandra: structured storage system on a P2P network[END_REF]], Amazon's Dynamo [START_REF] Decandia | Dynamo: amazon's highly available key-value store[END_REF]], LinkedIn's Project Voldemort, Oracle's BerkeleyDB [Berkeley, 2010] and mostly Graph Databases Systems (e.g., Neo4j

1 , Allegrograph 2 ,etc.), which are designed to store data in the form of a graph.

In the last decade, there has been increased attention in graphs to represent social networks, web site link structures, and others. Recently, database research has witnessed much interest in the W3C's Resource Description Framework (RDF) [W3C, 2014], which is a particular case of directed labeled graph, in which each labeled edge (called predicate) connects a subject to an object. It is considered to be the most appropriate knowledge representation language for representing, describing and storing information about resources available on the Web. This graph data model makes it possible to represent heterogenous Web resources in a common and unied way, taking into consideration the semantic side of 1 http://www.neo4j.org/ the information and the interconnectedness between entities. The SPARQL Protocol and RDF Query Language (SPARQL) [START_REF] Prud | SPARQL query language for RDF[END_REF] is the ocial W3C recommendation as an RDF query language. It plays the same role for the RDF data model as SQL does for the relational data model and provides basic functionalities (such as, union and optional queries, value ltering and ordering results, etc.) in order to query RDF data through graph patterns, i.e., RDF graphs containing variables data.

RDF data are usually composed of large heterogeneous data including various levels of quality e.g., over relevancy, trustworthiness, preciseness or timeliness of data (see [START_REF] Zaveri | Quality assessment for linked data: A survey[END_REF]). It is then necessary to oer convenient query languages that improve the usability of such data. A solution is to integrate user preferences into queries, which allows users to use their own vocabulary in order to express their preferences and retrieve data in a more exible way. This idea may be illustrated by an example of a real life scenario of movie online booking stated as follows: I want to nd a recent movie with a high rating.

In order to process such a query, fuzzy predicates, such as recent and high which model user preferences, have to be taken into account during database querying. These terms are vague and their satisfaction is a question of degree rather than an all or nothing notion.

Motivations for integrating user preferences into database queries are manifold [START_REF] Hadjali | Database preference queriesa possibilistic logic approach with symbolic priorities[END_REF].

First, it appears to be desirable to oer more expressive query languages that can be more faithful to what a user intends to say. Second, the introduction of preferences in queries provides a basis for rank-ordering the retrieved items, which is especially valuable in case of large sets of items satisfying a query. Third, a classical query may also have an empty set of answers, while a relaxed (and thus less restrictive) version of the query might be matched by some items.

Introducing user preferences in queries has been a research topic for already quite a long time in the context of the relational database model. In the literature, one may nd many exible approaches suited to the relational data model: top-k queries [START_REF] Bruno | Top-k selection queries over relational databases: Mapping strategies and performance evaluation[END_REF],

the winnow [Chomicki, 2002] and Best [START_REF] Torlone | Finding the best when it's a matter of preference[END_REF] operators, skyline queries [START_REF] Borzsony | The skyline operator[END_REF], Preference SQL [Kieÿling, 2002], as well as approaches based on fuzzy set theory [Tahani, 1977, Bosc and Pivert, 1995, Pivert and Bosc, 2012]. The literature about preference SPARQL queries to RDF databases is not as abundant since this issue has started to attract attention only recently. Most of these approaches are straightforward adaptations of proposals made in the relational database context. In particular, they are limited to the expression of preferences over the values present in the nodes.

In an RDF graph context the need to query about the structure of data and then extract relationships between resources in the RDF graph, has motivated research aimed to extend SPARQL and make it more expressive. In [START_REF] Kochut | SPARQLer: Extended SPARQL for semantic association discovery[END_REF], Anyanwu et al., 2007, Alkhateeb et al., 2009] and [START_REF] Pérez | nSPARQL: A navigational language for RDF[END_REF], the authors mainly extend SPARQL by allowing to query crisp RDF through graph patterns using regular expressions but in these approaches, both the graph and the search conditions remain crisp (Boolean).

However, in the real world, many notions are not of a Boolean nature, but are rather gradual (as illustrated by the example above), so there is a need for a exible SPARQL that takes into account RDF graphs where data is described by intrinsic weighted values, attached to edges or nodes. This weight may denote any gradual notion like a cost, a truth value, an intensity or a membership degree. For instance, in the real world, relationship between entities may be gradual (e.g., close friend, highly recommends, etc.) and an associated degree may express its intensity. A statement involving a gradual relationship is for instance an artist recommends a movie with a degree 0.8 (roughly, this movie is highly recommended by this artist).

In order to represent such information, several authors proposed fuzzy extensions of the RDF data model. However, the fuzzy extensions of SPARQL that can be found in the literature appear rather limited in terms of expressiveness of preferences.

Our aim in this thesis is to dene a much more expressive query language that i) deals with both crisp and fuzzy RDF graph databases and ii) supports the expression of complex preferences on the values of the nodes and on the structure of the graph. An example of such a query is most of the recent movies that are recommended by an actor, are highly rated and have been featured by a close friend of this actor.

Contributions

In this thesis, our main contributions are as follows.

1. We rst propose a fuzzy extension of the SPARQL query language that improves its expressiveness and usability. This extension, called FURQL, allows (1) to query a fuzzy RDF data model involving fuzzy relationships between entities (e.g., close friends), and

(2) to express fuzzy preferences on data (e.g., the release year of a movie is recent ) and on the structure of the data graph (e.g., the path between two friends is required to be short ). A prototype, called SURF, has been implemented and some experiments have been performed that show that introducing fuzziness in SPARQL does not come with a high price.

2. We then focus on the notion of fuzzy quantied statements for their ability to express dierent types of imprecise and exible information needs in a (fuzzy) RDF database context. We show how a particular type of fuzzy quantied structural query can be expressed in the FURQL language that we previously proposed and study its evaluation.

SURF has been extended to eciently process fuzzy quantied queries. It has been shown

through some experimental results that introducing fuzzy quantied statements into a SPARQL query entails a very small increase of the overall processing time.

3.

In the same way as we did with FURQL, we deal with fuzzy quantied queries in a more general (fuzzy) graph database context (RDF being just a special case). We study the same type of fuzzy quantied structural query and show how it can be expressed in an extension of the Neo4j Cypher query language, namely FUDGE, previously proposed in [Pivert et al., 2014a]. A processing strategy based on a compilation mechanism that derives regular (nonfuzzy) queries for accessing the relevant data is also described. Then, some experimental results are reported that show that the extra cost induced by the fuzzy quantied nature of the queries remains very limited.

Structure of the thesis

The remainder of the thesis is organized as follows:

• Chapter 1 introduces background concepts and notations that are necessary to understand the rest of this thesis. We start with the RDF data model and SPARQL, which is the standard query language for RDF data, and briey touch upon fuzzy set theory. Readers familiar with RDF, SPARQL and fuzzy set theory may want to skip this chapter.

• Chapter 2 discusses the state-of-the-art research work related to this thesis. We give a classied overview of approaches from the literature that have been proposed to make SPARQL querying of RDF data more exible. Then, we summarize the main features of these approaches and point out their limits.

• Chapter 3 is devoted to the presentation of our rst contribution which consists of a fuzzy extension of the SPARQL query language. First, we dene the notion of a fuzzy RDF database. Second, we provide a formal syntax and semantics of FURQL, an extension of the SPARQL query language. To do so, we extend the concept of a SPARQL graph pattern dened over a crisp RDF data model, into the concept of a fuzzy graph pattern that allows: (1) to query a fuzzy RDF data model, and (2) to express fuzzy preferences on data (through fuzzy conditions) and on the structure of the data graph (through fuzzy regular expressions).

• Chapter 4 is directly related to our second contribution that addresses the issue of integrating the notion of fuzzy quantied statements in the FURQL language introduced in Chapter 3 for querying fuzzy RDF databases. We rst recall important notions about fuzzy quantiers, and present dierent approaches from the literature for interpreting fuzzy quantied statements. Then, we introduce the syntactic format for expressing a specic type of fuzzy quantied structural query in FURQL and we show how they can be evaluated in an ecient way.

• Chapter 5 provides a detailed architectural implementation of the SURF prototype and reports experimental results related to approaches described in the previous chapters.

These results are promising and show the feasibility of the presented approaches.

• Chapter 6 concerns fuzzy quantied queries in a more general (fuzzy) graph database context. We start by recalling important notions about graph databases, fuzzy graph theory, fuzzy graph databases, and the FUDGE query language which is a fuzzy extension of the Neo4j Cypher query language. We then discuss related work about fuzzy quantied statements in a graph database context and point out their limits. In this chapter, we consider again a particular type of fuzzy quantied structural query addressed to a fuzzy graph database. We dene the syntax and semantics of an extension of the query language Cypher that makes it possible to express and interpret such queries in the FUDGE language. A query processing strategy based on the derivation of nonquantied fuzzy queries is also proposed and some experiments are performed in order to study its performances.

• Finally, we conclude the thesis by summarizing our main contributions. Then, we discuss our upcoming perspectives for future research in order to improve and extend the proposed approach.

Publications & Softwares

Parts of this thesis have been published as i) regular papers at the IEEE International Conference on Fuzzy Systems [Pivert et al., 2016c] [Pivert et al., 2017], at the International Conference on Scalable Uncertainty Management [Pivert et al., 2016e], and the ACM Symposium on Applied Computing [Pivert et al., 2016g], ii) as posters and demos at the IEEE International Conference on Research Challenges in Information Science [Pivert et al., 2016a[START_REF] Pivert | SUGAR: A graph database fuzzy querying system[END_REF]. [Pivert et al., 2016a] [ Pivert et al., 2016c] [ [START_REF] Pivert | Fuzzy quantied queries to fuzzy RDF databases[END_REF] Moreover, some works were published in French conferences: [START_REF] Pivert | FURQL : une extension oue du langage SPARQL[END_REF] The SURF prototype and the SUGAR prototype are available and downloadable respectively on the following web sites:

Introduction

Int his chapter, we introduce some background notions that will be used throughout the thesis. Section 1.1 presents the RDF graph data model, section 1.2 presents the SPARQL language used for querying this model and section 1.3 presents fuzzy set theory. Let us consider an album as a resource of the Web. Characteristics may be attached to the album, like its title, its artist, its date or its tracks. In order to express such a characteristic, the RDF data model uses a statement of the form of an RDF triple. Denition 1 provides a more formal denition. Denition 2 (RDF graph). An RDF graph is a nite set of triples of (U ∪B)×U ×(U ∪L∪B).

An RDF graph is said to be ground if it does not contain blank nodes.

An RDF graph can be modeled by a directed labeled graph where for each triple s, p, o , the subject s and the object o are nodes, and the predicate p corresponds to an edge from the subject node to the object one. RDF is then a graph-structural data model that makes it possible to exploit the basic notions of graph theory (such as, node, edge, path, neighborhood, connectivity, distance, in-degree, out-degree, etc.). Moreover, RDF provides a schema denition language called RDF Schema (RDFS), which allows to specify semantic deductive constraints on the subjects, properties and objects of an RDF graph. It permits to declare objects and subjects as instances of given classes, and inclusion statements between classes and properties. It is also possible to relate the domain and range of a property to classes. RDFS denes a set of reserved words from URI with its own predened semantics/vocabularies (i.e., RDFS vocabulary). Among RDFS vocabularies, we can mention the following list:

• (rdf:type): represents the membership to a class;

• (rdfs:subClassOf ): represents the subclass relationship between classes;

• (rdfs:subPropertyOf ): represents the subclass relationship between properties;

• (rdfs:domain): represents the domain of properties;

• (rdfs:range): represents the range of properties;

• (rdfs:Class): represents the meta-classes of classes;

• (rdf:Property): represents the meta-classes of properties;

• etc. RDF also declares entailment rules that make it possible to derive new triples from the explicit triples appearing in an RDF graph. Such implicit triples are part of the RDF graph even if they do not explicitly appear in it. They can be explicitly added to the graph. When all implicit triples are made explicit in the graph, then, the graph is said to be saturated. In this thesis, we only consider saturated RDF graph. A database which stores RDF graphs, containing statements of the form (subject-predicateobject), is called a triple store (or simply an RDF database ).

There have been a signicant number of RDF databases over the last years mainly divided into two categories [START_REF] Faye | A survey of RDF storage approaches[END_REF]:

• Native RDF stores implement their own database engine without reusing the storage and retrieval functionalities of other database management systems. Some examples of native RDF stores are AllegroGraph (commercial) 6 , Apache Jena TDB (open-source) 7 , etc.

• Non-native RDF Stores use the storage and retrieval functionalities provided by other database management systems. Among the non-native RDF stores, we nd the Apache

Jena SDB (open-source) using conventional relational databases 8 , etc. 1.2 Example 4 [Basic Graph Pattern] The albums featuring the artist Beyonce, with their names are described by the following graph pattern.

?artist dc:creator ?album . ?artist dc:title "Beyonce" . ?album dc:title ?name . According to the graph of Figure 1.1, two subgraphs that are isomorphic to this graph pattern may be found and they are given in Figure 1.3. A classical SPARQL query has the general form given in Listing 1.4, where the clause prefix is for abbreviating URIs (which will be omitted in the following examples), the clause select is for specifying which variables should be returned, the clause from denes the datasets to be queried, and the clause where contains the triple of the researched pattern. ..,distinct ...,limit ...,offset ...,projection ... #Modifiers Listing 1.4: Skeleton of a sparql query SPARQL also provides solution modiers, which make it possible to modify the result set by applying classical operators like order by for ordering the result set in ascending (asc (.) default ordering) or descending (desc(.)) order, distinct for removing duplicate answers, limit to limit the number of answers to a xed number (chosen by a user), projection to choose certain variables and eliminate others from the solutions, or offset to dene the position of the rst returned answers.

Finally, the output of a SELECT SPARQL query is a set of mappings of variables which match the patterns in the where clause.

Example 5 • Optional graph pattern: uses the clause optional and allows for a partial matching of the query. The query tries to match a graph pattern and does not discard a candidate answer when some part of the optional patterns is not satised. • Filter graph pattern: using the clause filter followed by an expression to select answers according to some criteria. This expression may contain classical operators (e.g., =, + , * , -, / , < , > , ≥ , ≤) and functions (e.g., isU RI(?x), isLiteral(?x), isBlank(?x), regex(?x, "A. * )).

Example 8 • SELECT query: is equivalent to an SQL SELECT, used to return a set of variables from the query pattern using the select clause. For instance, all the aforementioned examples of SPARQL queries are of the SELECT form;

• CONSTRUCT query: returns a single RDF graph by creating new triples that satisfy a specic template from the query pattern.

Example 9 [CONSTRUCT query] Let us assume that, if a person X knows a person Y and if this latter (X ) knows a person Z, so, we can say that the rst person X knows the person Z or any person known by Y . Thus, we can create this relationship thanks to the following CONSTRUCT query. construct { ?x foaf:knows ?z . } where { ?x foaf:knows ?y . ?y foaf:knows ?z . } Listing 1.10: An example of a CONSTRUCT query

• ASK query: is used to return a Boolean result: true if there exists at least one result that matches the query pattern and false otherwise.

Example 10 [ASK query] The following query illustrates the use of the ASK query: Is Beyonce the name of the resource uri:beyonce ? ask { uri:beyonce dc:title "Beyonce" . } Listing 1.11: An example of an ASK query This query returns true since the resource uri:beyonce is indeed the artist Beyonce.

• DESCRIBE query: is used to return a single RDF graph with information about the selected resources.

Example 11 [DESCRIBE query] An example of a DESCRIBE query is given in Lsiting 1.12. describe uri:beyonce Listing 1.12: An example of a DESCRIBE query This query returns information about the ressource <uri:beyonce>, such as, its name, its age, its rating, its type, etc.

Recently, SPARQL 1.1 [Harris and Seaborne, 2013] is a new version of SPARQL supporting new features, such as, property paths, update functionalities, subqueries, negation, value assignments, aggregates functions, etc.

• Property paths: they are known as regular expressions tackled in [START_REF] Kochut | SPARQLer: Extended SPARQL for semantic association discovery[END_REF], Anyanwu et al., 2007, Pérez et al., 2008, Alkhateeb et al., 2009, Pérez et al., 2010 • Assignments: The value of a complex expression can be added to a solution mapping by binding a new variable to the value of this expression. The variable can then be used in the query and also can be returned in the result. The assignment is of the form:

(expression as ?var).

Example 16 [Query with assignment] The following query aims to return the albums released less than 6 years before 2017.

Fuzzy Set Theory

In the classical set theory, there are two possible situations for an element: to belong or to not belong to a subset.

In 1965, Lot Zadeh [Zadeh, 1965] proposed to extend classical set theory by introducing the concept of gradual membership in order to model classes whose borders are not clear-cut.

A fuzzy set is associated with a membership function which takes its values in the range of real numbers [0,1], that is to say that graduations are allowed and an element may belong more or less to a fuzzy subset.

The theory of fuzzy sets has advanced applications in articial intelligence, computer science, decision theory, expert systems, robotics, etc. They also play an important role in expressing fuzzy user preferences queries to relational databases [Dubois andPrade, 1997, Pivert andBosc, 2012].

In the following, we rst give a formal denition and some characteristics of the notion a fuzzy set, and then the main operations over fuzzy sets are detailed. 1.3.1 Denition Let X be a classical set of objects called the Universe and x be any element of X. If A is a classical subset of X, the membership degree of every element can take only extreme values 0 or 1. This corresponds to the classical denition of a characteristic function :

µ A (x) = 1 i x ∈ A, 0 otherwise.
When A is a fuzzy subset of X [Zadeh, 1965] it is denoted by:

A = {(x, µ A (x)), x ∈ X} with µ A :X → [0,1],
where µ A (x) is a degree of membership (simply denoted degree in the following) that quanties the membership grade of x in A. The closer the value of µ A (x) to 1, the more x belongs to A.

Therefore, we can have the three situations:

µ A (x)=0 , 0 < µ A (x) < 1 , µ A (x)=1.
where µ A (x)=0 means that x does not belong to A at all, 0 < µ A (x) < 1 if x belongs partially to A and µ A (x)=1 means that x belongs entirely to A.

In practice, the membership function of A is of a trapezoidal shape (see Figure 1.4) and is expressed by the quadruplet (A -a, A, B, B + b).

A = {µ A (x 1 )/x 1 , ..., µ A (x n )/x n },
It is worth mentioning that in practice the elements for which the degree equals 0 are omitted.

Remark 1. A fuzzy subset of X is called normal if there exists at least one element x ∈ X such as µ A (x) = 1. Otherwise it is called subnormal. 1.3.2 Characteristics of a Fuzzy Set

Several notions can be used to describe a fuzzy set. Among them we can cite. 1.3.2.1 Support,height and core The support of a fuzzy subset A in the universal set X, denoted by supp(A), is a crisp set that contains all the elements of X that have a strictly positive degree in A (i.e., which belong somewhat to A). More formally:

supp(A) = {x | x ∈ X, µ A (x) > 0}.
The core of a fuzzy subset A, denoted by core (A), is the crisp subset of X containing all the elements with a degree equal to 1 (i.e. that completely belong to A with degree equal to 1). More formally:

core(A) = {x | x ∈ X, µ A (x) = 1}.
Remark 2. Note that in the case of a crisp set, the support and the height collapse, since if

x is somewhat in A it belongs (totally) to A.

Example 19 Let us consider two fuzzy subsets A and B of the set X, with X= {x 1 , x 2 , x 3 , x 4 , x 5 }, A= {1/x 1 , 0.3/x 2 , 0.2/x 3 , 0.8/x 4 , 0/x 5 } and B= {0.6/x 1 , 0.9/x 2 , 0.1/x 3 , 0.3/x 4 , 0.2/x 5 }.

The supports of the two subsets A and B are:

supp(A) = {x 1 , x 2 , x 3 , x 4 }, supp(B) = {x 1 , x 2 , x 3 , x 4 , x 5 }.
The core of these two subsets is as follows:

core(A)= {x 1 }, core(B)= ∅.
The height of a fuzzy subset A of X denoted by hgt(A) is the largest degree attained by any element of X that belongs to A. More formally:

hgt(A) = sup x∈X µ A (x).
A is said to be normalized i ∃ x ∈ X, µ A (x) = 1 which means that hgt(A) = 1. 1.3.2.2 α-cut The ordinary set of such elements x ∈ X having a membership degree larger or equal to a threshold α ∈]0, 1] is the α-cut (A α ) of the fuzzy subset A dened as:

A α = {x | x ∈ X, µ A (x) ≥ α}.
Example 20 Let us consider X={x 1 , x 2 , x 3 } and a fuzzy subset A={0.3/x 1 + 0.5/x 2 + 1/x 3 }, the α-cuts of this subset are as follows :

A 0.5 = {x 2 , x 3 }, A 0.1 = {x 1 , x 2 , x 3 }, A 1 = {x 3 }
The membership function of a fuzzy subset A can be expressed in terms of characteristic functions of its α-cuts according to the following formula:

µ A (x) = sup α∈]0,1] min(α, µ Aα (x)) , where µ Aα (x) = 1 i x ∈ A α , 0 otherwise.
The strict (or strong) α-cut of A, denoted by A ᾱ, contains all the elements in X that have a membership value in A strictly greater than α:

A ᾱ = {x|x ∈ X, µ A (x) > α}.
The following properties hold:

• A0 = supp(A), • A1 = core(A), • α 1 > α 2 ⇒ A α 1 ⊆ A α 2 .
It can easily be checked that:

(A ∪ B) α = A α ∪ B α and (A ∩ B) α = A α ∩ B α .

Operations on Fuzzy Sets

Classical operations on crisp sets have been extended to fuzzy sets. These extensions are equivalent to classical operations of set theory when dealing with membership functions belonging to values 0 or 1. The most commonly used operations are presented hereafter and the interesting reader may refer to [Dubois, 1980]. 1.3.3.1 Complementation The complement of a fuzzy set A, denoted by Ā, is dened as:

∀x ∈ X, µ Ā(x) = 1 -µ A (x).
Example 21 Let us consider the fuzzy subset A = {1/ x 1 + 0.3/x 2 + 0.2/x 3 + 0

.8/x 4 + 0/x 5 }. Its complement is Ā = {0/x 1 + 0.7/x 2 + 0.8/x 3 + 0.2/x 4 + 1/x 5 }.
This operation is involutive, i.e., Ā = A (µ Ā(x) = µ A (x)). 1.3.3.2 Inclusion Let us consider two fuzzy sets A and B dened on X. If for any element x of X, x belongs less to A than B or has the same membership, then A is said to be included in

B (A ⊆ B). Formally A ⊆ B if and only if: ∀x ∈ X, µ A (x) ≤ µ B (x).
When the inequality is strict, the inclusion is said to be strict and is denoted by A ⊂ B. Obviously, A=B i A ⊆ B and B ⊆ A. 1.3.3.3

Intersection and union of fuzzy sets

The intersection of two fuzzy subsets A and B in the universe of discourse X, denoted by A ∩ B, is a fuzzy set given by:

µ A∩B (x) = (µ A (x), µ B (x)),
where is a triangular norm (abbreviated t-norm ) and usually we take the minimum.

The union of two fuzzy subsets A and B in the universe X (denoted by A ∪ B) is a fuzzy subset given by:

µ A∪B (x) = ⊥(µ A (x), µ B (x)),
where ⊥ is a triangular co-norm (abbreviated t-conorm ) and usually we take the maximun.

The t-norms and t-conorms operators follow the properties showed in Table 1

A ∩ B = {0.6/x 1 , 0.3/x 2 , 0.1/x 3 , 0.3/x 4 , 0/x 5 }.
The union of the two fuzzy subsets, taking ⊥ = max, is as follows: x 1 ,0.9/x 2 ,0.2/x 3 ,0.8/x 4 ,0.2/x 5 }

A ∪ B = {1/
1 ∧ x = x 0 ∨ x = x Commutativity x ∧ y = y ∧ x x ∨ y = y ∨ x Associativity x ∧ (y ∧ z) = (x ∧ y) ∧ z x ∨ (y ∨ z) = (x ∨ y) ∨ z Monotonicity if v ≤ w and x ≤ y then v ∧ x ≤ w ∧ y v ∨ x ≤ w ∨ y
Remark 3. A t-norm is associated with a t-conorm (e.g., min/max) and they satisfy De Morgan's Laws.

Later, compensatory operators, such as the averaging operators, have appeared useful for aggregating fuzzy sets, especially in the context of decision making [Zimmermann, 2011].

Averaging operators for intersection (resp., union) are considered to be more optimistic (resp., pessimistic) than t-norms (resp., t-conorms ).

Let us also mention many other operators that may be used for expressing dierent kinds of trade-os, such as the weighted conjunction and disjunction [START_REF] Dubois | Weighted minimum and maximum operations in fuzzy set theory[END_REF], fuzzy quantiers [START_REF] Fodor | Fuzzy-set theoretic operators and quantiers[END_REF] (that are going to be explained in Chapter 4), or the non-commutative connectives described in [START_REF] Bosc | On four noncommutative fuzzy connectives and their axiomatization[END_REF]. 1.3.3.4 Dierence between fuzzy sets

The dierence between two fuzzy sets A and B is dened as:

∀x ∈ X, µ A-B (X) = (µ A (x), µ B (x)) = (µ A (x), 1 -µ B (x)),
which leads to:

• µ A-B (x) = min(µ A (x), 1 -µ B (x)) with (x, y) = min(x, y), • µ A-B (x) = max(µ A (x) -µ B (x), 0) if (x, y) = max(x + y -1, 0) is chosen.
Example 23 Consider the following fuzzy sets A= {1/a, 0.3/b, 0.7/c, 0.2/e } and B= {0.3/a, 1/c, 1/d, 0.6/e}.

Using the minimum for the conjunction, one obtains { 0.7/a, 0.3/b, 0.2/e} for the dierence A -B, while A -B= { 0.7/a, 0.3/b} with the other choice. 1.3.3.5 Cartesian product of fuzzy sets

The Cartesian product of the two fuzzy sets A and B, dened as:

µ A×B (xy) = (µ A (x), µ B (x)),
where is a triangular norm.

Introduction

Int he last years, with the rapid growth in size and complexity of RDF graphs, querying RDF data in a exible, expressive and intelligent way has become a challenging problem. In the following, we present the contributions from the literature that make SPARQL querying of RDF data more exible. Three categories of approaches may be associated with the following objectives: i) introducing user preferences into queries (which is directly related to this thesis),

ii) relaxing user queries and iii) computing an approximate matching of two RDF graphs.

These approaches are discussed further in the following sections.

A part of this chapter related to introducing user preferences inside SPARQL queries was published in the form of a survey in the proceedings of the 31st ACM Symposium on Applied

Computing (SAC'16).

Preference Queries on RDF Data

Introducing user preferences into queries has been a research topic for already quite a long time in the context of the relational database model. Motivations for integrating preferences are manifold [START_REF] Hadjali | Database preference queriesa possibilistic logic approach with symbolic priorities[END_REF]. First, it has appeared to be desirable to oer more expressive query languages that can be more faithful to what a user intends to say. Second, the introduction of preferences in queries provides a basis for rank-ordering the retrieved items, which is especially valuable in case of large sets of items satisfying a query. Third, a classical query may also have an empty set of answers, while a relaxed (and thus less restrictive) version of the query might be matched by some items.

The literature about preference queries to RDF databases is not as abundant as in the relational context since this issue has started to attract attention only recently. In this section, we present an overview of approaches that have been proposed to extend SPARQL by integrating user preferences in queries, followed by a classication of these approaches into two categories according to their qualitative or quantitative nature. We rst present quantitative approaches (Subsection 2. 1.1), then qualitative ones (Subsection 2.1.2).

Quantitative Approaches

The quantitative approaches share the following principle: each involved preference is dened via an atomic scoring function allowing a score (aka., satisfaction degree) to be associated with each answer, making it possible to get a total ordering of the answers (i.e., tuple t 1 is preferred to tuple t 2 if the score of t 1 is higher than the score of t 2 ).

Among the works which belong to the quantitative approaches we may nd those that are based on fuzzy set theory [Zadeh, 1965] and aim to a exible extension of the query language (SPARQL) [START_REF] Cheng | f-SPARQL: a exible extension of SPARQL[END_REF], Wang et al., 2012, Ma et al., 2016]. We can nd, also, those based on top-k querying of RDF data that aim to extend the SPARQL language with top-k queries [START_REF] Bozzon | Towards and ecient SPARQL top-k query execution in virtual RDF stores[END_REF], Bozzon et al., 2012, Magliacane et al., 2012, Wang et al., 2015].

Fuzzy set-based approach

The standard version of the SPARQL query language supports only a few classical ways of retrieval, all based on Boolean logic.

In order to meet user needs more eectively, [START_REF] Cheng | f-SPARQL: a exible extension of SPARQL[END_REF] proposes a syntactical fuzzy extension of SPARQL, called f-SPARQL (fuzzy SPARQL), which supports the expression of fuzzy conditions including (possibly compound) fuzzy terms, e.g., recent or young, and fuzzy operators, e.g., close to or at least, interpreted in a gradual manner.

µ atleastY (x) =      0, if u ≤ w; u-w Y -w , if w < u < Y ; 1, if u ≥ Y.
(?X θ FT ) | (?X θ Y)] [with α],
where FT denotes a fuzzy term, θ denotes a classical operator (e.g., >, <, =, ≥, ≤, ! =), θ denotes a fuzzy operator (such as close to (around), at least, and at most ), and Y is a string, an integer or an other types allowed in RDF. The optional parameter [with α] species the smallest acceptable membership degree in the interval [0, 1]. Each f-SPARQL query is prexed by #FQ#.

Example 25 The fuzzy query retrieve the name of the recent albums with

Beyonce is formulated by the f-SPARQL listing 2.1.

#FQ# select ?name where { ?artist dc:title "Beyonce". ?artist dc:creator ?album . ?album dc:title ?name. ?album dc:date ?date. filter (?date = recent).} Let us now assume that the database of the running example embeds a rating value for each album, through a property named dc:rate connecting an album (URI resource) to a rating value (a label). When a user wants to express preferences on several attributes (e.g., date, rating, ...), he/she may assign an importance to every partial preference. If no importance is specied, it is implicitly assumed that the partial degrees are aggregated by means of the triangular norm minimum that is commonly used in fuzzy logic to interpret the conjunction.

In [START_REF] Cheng | f-SPARQL: a exible extension of SPARQL[END_REF], the authors propose to use a weighted mean in order to combine the partial scores coming from dierent atomic preference criteria:

score(A) = n i=1 µ(A i ) × w(F i ) (2.2)
where F = (F 1 , ..., F n ) is the set of filter conditions, A i is the property concerned by F i

in the candidate answer A, µ(A i ) denotes the membership degree of the answer for F i , and w(F i ) denotes the weight assigned to F i , assuming that n i=1 w(F i ) = 1.

Example 26 Consider the query retrieve the name of the recent (importance 0. It is also possible to apply a threshold α i to an atomic fuzzy condition F i (this threshold is associated with the underlying attribute in the select clause). Then, an answer is qualied only if its membership degree relatively to F i is at least equal to α i . Surprisingly, it does not seem that f-SPARQL makes it possible to specify a threshold on the global satisfaction degree.

As in SQLF introduced in [Bosc and Pivert, 1995], two types of queries exist in f-SPARQL depending on the type of calibration:

• a qualitative calibration in the case of exible queries (#fq#) (see Listing 2.2);

• a quantitative calibration in the case of top-k exible queries (#top-k fq# with k (see Listing 2.3), and then, only the top-k answers are returned.

The query type has to be declared before the select clause: #fq# (exible query) in the rst case, and #top-k fq# with k (top-k exible query) when a quantitative threshold is used.

Example 27 Let us consider again the query from Example 26 and assume that a user only wants to get the 10 best answers. The authors of [START_REF] Cheng | f-SPARQL: a exible extension of SPARQL[END_REF] exhibit a set of translation rules to convert f-SPARQL queries into Boolean ones so as to be able to benet from the existing implementations of standard SPARQL. The same principle was initially proposed in [START_REF] Bosc | SQLf query functionality on top of a regular relational database management system[END_REF] in the context of relational databases (under the name derivation principle ) to process SQLf (fuzzy) queries. It aims to derive a crisp (SQL) query from an SQLf query involving a (global)

qualitative threshold α in order to return only answers with satisfaction degree greater or equal to the α-cut. Dierent types of translation rules were used in [START_REF] Cheng | f-SPARQL: a exible extension of SPARQL[END_REF] depending on the the types of fuzzy terms (including simple atomic terms, e.g., recent, modied fuzzy terms, e.g., very recent, and compound fuzzy terms, e.g., popular and very recent ) and fuzzy operators.

Some of the authors of [START_REF] Cheng | f-SPARQL: a exible extension of SPARQL[END_REF] proposed two variants of f-SPARQL. The First one, called fp-SPARQL (fuzzy and preference SPARQL) [START_REF] Wang | fp-Sparql: an RDF fuzzy retrieval mechanism supporting user preference[END_REF], involves an alternative way of (i) interpreting modied fuzzy terms (i.e., an atomic fuzzy term modied by an adverb such as extremely, rather, etc), and (ii) interpreting compound fuzzy conditions where atomic predicates are assigned a priority.

The second query language, called SPARQLf-p [START_REF] Ma | SPARQL queries on RDF with fuzzy constraints and preferences[END_REF], makes it possible to express i) more complex conditions including fuzzy relations (e.g., physical health is a fuzzy relation between height and weight) besides fuzzy terms and fuzzy operators and, ii) multidimensional user preferences.

From another point of view, the authors of [START_REF] Buche | Flexible querying of fuzzy RDF annotations using fuzzy conceptual graphs[END_REF], Buche et al., 2009, Buche et al., 2013] dened a exible querying system using fuzzy RDF annotations based on the notion of similarity and imprecision. This approach is beyond the scope of our work since it does not explicitly propose an extension of the SPARQL query language.

Top-k-based approach

Top-k -query approaches have been proposed for already many years in a relational database context (cf., the survey of [START_REF] Ilyas | A survey of topk query processing techniques in relational database systems[END_REF]). They have been useful in several application areas such as system monitoring, information retrieval, multimedia databases, sensor networks, etc. Top-k queries [START_REF] Bruno | Top-k selection queries over relational databases: Mapping strategies and performance evaluation[END_REF] are a popular class of queries that return only the k most relevant (best) tuples according to user's preferences. The attribute values of each tuple are associated with a value or score using a simple linear function. Top-k -queries can be viewed as a special case of fuzzy queries limited to conditions of the form:

attribute constant

The distance between an attribute value and the ideal value is computed by mean of a dierence (absolute value), after a normalization step (which yields domain values between 0 and 1). The overall distance is calculated by aggregating the elementary distances using a function which can be the minimum, the sum, or the Euclidean distance. The steps in the computation are the following:

1. using k, and taking into account both the chosen aggregation function and statistics about the considered relation, a threshold α over the global distance is deduced, 2. a Boolean query computing the desired α-cut or a superset of this α-cut is determined, 3. this query is processed and the score attached to every element of the result is calculated, 4. if at least k tuples with a score greater than or equal to α have been obtained, the k best are returned to the user; otherwise the procedure is run again (from step 2) using a lower threshold α.

For eciently processing Top-k -queries in the context of relational databases, several algorithms have been proposed (e.g., Threshold Algorithm (TA) and No Random Access Algorithm (NRA) [START_REF] Fagin | Optimal aggregation algorithms for middleware[END_REF], the Best Position Algorithm [START_REF] Akbarinia | Best position algorithms for top-k queries[END_REF],

LPTA [START_REF] Das | Answering top-k queries using views[END_REF], LPTA+ [START_REF] Xie | Ecient top-k query answering using cached views[END_REF] and IV-Index [START_REF] Xie | Ecient top-k query answering using cached views[END_REF]).

In the Semantic Web community, top-k -queries have raised a growing interest in the last few years [START_REF] Bozzon | Extending SPARQL algebra to support ecient evaluation of top-k SPARQL queries[END_REF], Magliacane et al., 2012, Dividino et al., 2012, Wang et al., 2015] for alleviating information overload problems. A major challenge is to make the processing of such queries ecient in a SPARQL-like setting.

Classical top-k -SPARQL queries can be expressed in SPARQL 1.1 by solution modiers, such as, order by and limit clauses, that respectively order the result set, and limit the number of results.

Example 28 The top-k -SPARQL query of Listing 2.4 aims to nd the best ve oers of albums ordered by a function of user ratings and oer date where g 1 and g 2 are scoring functions.

select ?album ?offer (g 1 (?rating) + g 2 (?date) AS ?score) where { ?album rdf:type mo:Album. ?album dc:rating ?rating. ?album dc:date ?date. ?album dc:hasOffers ?offer. } order by desc(?score) limit 5

Listing 2.4: Standard top-k -SPARQL-query

Naive query processing then relies on a materialize-then-sort procedure which entails an evaluation of all the candidate answers (i.e., those satisfying the condition in the where clause), followed by a computation of the ranking function for each of them, even if only a small number (typically, k = 5) of answers is requested. As a consequence, this processing strategy produces poor performances especially in the case of a large number of answers matching the selected query. A smart processing should stop as soon as the top-k results are returned.

In this respect, recent works have proposed solutions to optimize the evaluation of these queries.

For instance, the authors of [START_REF] Bozzon | Towards and ecient SPARQL top-k query execution in virtual RDF stores[END_REF], Bozzon et al., 2012, Magliacane et al., 2012] introduced a SPARQL-RANK algebra which is an extension of the SPARQL algebra [START_REF] Pérez | Semantics and complexity of SPARQL[END_REF]] and an incremental rank-aware execution model for top-k -SPARQL queries. This algebra enables splitting the scoring function that may be interleaved with other binary operators. The general objective is to derive an optimized query execution plan and reduce as much as possible the evaluation to a restricted number of answers.

[ [START_REF] Bozzon | Towards and ecient SPARQL top-k query execution in virtual RDF stores[END_REF] rst applied this algebra to the processing of top-k SPARQL queries addressed to virtual RDF datasets through query rewriting using the rank-aware relational algebra presented in [START_REF] Li | RankSQL: query algebra and optimization for relational top-k queries[END_REF]. Then, [START_REF] Bozzon | Extending SPARQL algebra to support ecient evaluation of top-k SPARQL queries[END_REF] proposed a detailed version of the SPARQL-RANK algebra, which can be applied to both RDBMS and native RDF datasets. They introduced a rank-aware operator denoted by ρ for evaluating a ranking criterion and redened unary and binary operators (such as, selection (σ), join ( ), union (∪), dierence (\) and left joint ( )) for processing the ranked set of mappings in this context. New algebraic equivalence laws involving this operator have also been proposed.

Among these equivalence laws we may nd, pushing ρ over binary operators, splitting the criteria of a scoring function into a set of rank operators and using commutativity of ρ with itself.

In [START_REF] Magliacane | Ecient execution of top-k SPARQL queries[END_REF], an incremental execution model for the SPARQL-RANK algebra is proposed and a rank-aware SPARQL query engine denoted by ARQ-RANK based on this algebra is implemented. This engine eciently improves the performance of top-k queries. Later, in [START_REF] Zahmatkesh | Towards a top-k SPARQL query benchmark generator[END_REF], the authors presented top-k DBPSB, an extension of DBPSB (DBpedia SPARQL benchmark) that makes it possible to automatically generate top-k queries from the queries of DBPSB and its datasets.

According to [START_REF] Wang | Top-k queries on RDF graphs[END_REF], the SPARQL-RANK algebra proposed by [START_REF] Bozzon | Towards and ecient SPARQL top-k query execution in virtual RDF stores[END_REF], Bozzon et al., 2012, Magliacane et al., 2012] suers from frequent unnecessary input and output in the rank-join operation and this is seen as a drawback in the case of a large dataset. To deal with this issue, they proposed in [START_REF] Wang | Top-k queries on RDF graphs[END_REF] a graph-exploration-based method for eciently processing top-k queries in crisp RDF graphs. They introduced a novel tree index called an MS-tree. Based on this MS-tree, candidate entities are constructed (ranked and ltered) in an appropriate way and the process immediately stops as soon as possible (i.e., as soon as the top-k answers are generated). In case of complex scoring functions, a cost-model-based optimization method is used in order to improve the query processing performance.

An evaluation of the approach with both synthetic and real-world datasets using SPARQL-RANK as a competitor is presented in the paper. The experimental results conrm that the model proposed in [START_REF] Wang | Top-k queries on RDF graphs[END_REF] signicantly outperforms SPARQL-RANK approach in case of large datasets to be cached in memory.

From an RDF data model view, in [START_REF] Dividino | Ranking RDF with provenance via preference aggregation[END_REF] the authors introduce an approach for top-k querying RDF data annotated with provenance information. In this context, annotations may concern the origin, history, truthfulness, or validity of an RDF statement.

An annotated RDF statement is considered as a tuple S= α : θ 1 ,. The statement #1 says that the artist TAL plays in the Le Grand Rex and this information has been published on 03.02.17, has 0.9 as a certainty degree, and was picked up from the Web site www.legrandrex.com.

The presence of multiple independent annotation dimensions in the query can induce dierent rankings of answers. In this regard, [START_REF] Dividino | Ranking RDF with provenance via preference aggregation[END_REF] discusses the problem of preference aggregation (or judgement aggregation) and proposes a framework to aggregate all the annotation dimensions into a single joint ranking ordering using dierent aggregation methods. Finally, the authors of [START_REF] Dividino | Ranking RDF with provenance via preference aggregation[END_REF] perform top-k querying using these ranking methods in oine (i.e., available results) and online (i.e., the aggregation of streaming data) settings.

Qualitative Approaches: Skyline-based Approaches

In the relational database domain, qualitative approaches to preference queries have attracted a large interest, in particular skyline queries [START_REF] Borzsony | The skyline operator[END_REF], which aim to lter an n-dimensional dataset S according to a set of user preference relations and return only the tuples of S that are not dominated in the sense of Pareto order. Note that these approaches only yield a partial order, contrary to the quantitative ones.

Let us consider two tuples t = (u 1 , . . . , u n ) and t = (u 1 , . . . , u n ) from S (reduced to the attributes on which a preference is expressed). The tuple t dominates (in the sense of Pareto order) the tuple t , denoted by t t , i t is at least good as t in all dimensions and strictly better than t in at least one dimension. This may be represented by: t t ⇔ ∀i ∈ {1, . . . , n}, t.u i i t .u i and ∃j ∈ {1, . . . , n} such that t.u j j t .u j (2.3) Example 30 Let us assume that a user is looking for an album to listen to, and prefers an album which is recent and high rated. For every preference: recent (resp. high rated), the higher the date (resp. rating) is, the more preferred the tuple is. Consider three albums A 1 (date 2015, rating 5.8), A 2 (date 2013, rating 4) and A 3 (date 2014, rating 8). Album A 1 is more recent and has a higher rating than A 2 . So, A 1 dominates A 2 . Nevertheless, A 1 does not dominate A 3 since A 1 is more recent than A 3 but has a worse rating than A 3 . Hence, the skyline result is {A 1 , A 3 }.

In the literature, few works [START_REF] Siberski | Querying the semantic web with preferences[END_REF], Gueroussova et al., 2013] have dealt with the expression and evaluation of skyline queries in a SPARQL-like language.

In [START_REF] Siberski | Querying the semantic web with preferences[END_REF], Siberski et al. extend SPARQL with a preferring clause in order to support the expression of multidimensional user preferences. This extension is based on the principle underlying skyline queries, i.e., it aims to nd the nondominated objects.

The main syntax of this extension is as follows: select ... where ... { filter (A or B) } preferring P and P' ... and P* Listing 2.5: Extension of SPARQL using Skyline Two types of preferences may be distinguished: Boolean preferences where the answers that meet the condition are favored over those which do not, and scoring preferences (introduced by the keywords highest or lowest, where the elements with a higher value are favored over those with a lower value and vice versa).

Example 31 Let us consider that a user has the following preferences: (P 1 ) prefer the artists rated excellent over the very good ones (Boolean preference), (P 2 ) prefer the artist's concert taking place between 9pm and 1am (Boolean preference) and (P 3 ) prefer the artist's concert taking place the latest (scoring preference) pro- vided that they are taking place between 9pm and 1am.

In the absence of a skyline functionality, one would use the classical SPARQL query of Listing 2.6 that returns those artists satisfying the Boolean conditions, ordered according to the starting time of their concert. As we can see, a classical skyline query can be expressed in SPARQL with the clauses filter, order by and desc. However, the classical skyline query of Listing 2.6 also returns dominated artists, but only at the bottom of the list of answers.

In the extended SPARQL version of [START_REF] Siberski | Querying the semantic web with preferences[END_REF], lines 5 to 7 of Listing 2.6 are replaced by: 5 preferring 6 ?rating = ft:excellent 7 and 8 (?startingTime >= 9pm && ?endingTime <= 1am) 9 cascade highest(?startingTime) Listing 2.7: Skyline extension of SPARQL [START_REF] Siberski | Querying the semantic web with preferences[END_REF] Lines 1 to 4 represent the graph patterns and hard constraints.

Line 6 corresponds to preference P 1 , line 8 corresponds to P 2 , and line 9 corresponds to P 3 . The cascade clause in line 9 species that P 3 is evaluated if and only if two answers are equivalent with respect to P 2 .

The authors of [START_REF] Siberski | Querying the semantic web with preferences[END_REF] gave the semantics and the implementation of the new constructs aimed to compute a skyline query with SPARQL and extended the SPARQL implementation ARQ in order to process these types of queries. Nevertheless, no optimization aspects are discussed in the paper.

The approach proposed in [START_REF] Gueroussova | SPARQL with qualitative and quantitative preferences[END_REF] is based on [START_REF] Siberski | Querying the semantic web with preferences[END_REF]] and i) introduces user preferences in the filter clause, ii) replaces the cascade clause by a prior to clause in the spirit of Preference SQL [START_REF] Kieÿling | The preference SQL system-an overview[END_REF], iii) introduces new comparators for specifying atomic preferences: between, around, more than, and less than. The authors of [START_REF] Gueroussova | SPARQL with qualitative and quantitative preferences[END_REF] show that PrefSPARQL preference queries can be expressed in SPARQL 1.0 and SPARQL 1.1 using an optional clause or features available in SPARQL 1.1 such as not exists. Nevertheless, they do not deal with implementation issues and query processing/optimization aspects.

In [START_REF] Rosati | Preference queries with ceteris paribus semantics for linked data[END_REF], the authors are interested also in qualitative preferences but the preferences are represented by means of a CP-net. A CP-net (network of conditional preferences) has been earlier suggested by [START_REF] Boutilier | CP-nets: A tool for representing and reasoning with conditional ceteris paribus preference statements[END_REF] for modeling relational database preference queries. It is a powerful graphical representation of statements that express conditional ceteris paribus (everything else being equal) preferences.

Example 34 Let us consider the following ceteris paribus preferences on clothes: i) P 1 : black (b) jackets are preferred to white (w) jackets, ii) P 2 : black (b) pants are preferred to white (w) pants, iii) P 3 : if the jackets and the pants are of the same color, red (r) shirts are preferred to white (w) ones; otherwise, white shirts are preferred. These preferences are modeled by means of the CP-net depicted in The authors of [START_REF] Rosati | Preference queries with ceteris paribus semantics for linked data[END_REF] propose an RDF vocabulary to represent qualitative preference triples formulated under the ceteris paribus semantics. Inspired by [START_REF] Gueroussova | SPARQL with qualitative and quantitative preferences[END_REF], the authors of [START_REF] Rosati | Preference queries with ceteris paribus semantics for linked data[END_REF] present an algorithm to encode a CP-net into a standard SPARQL 1.1 query able to retrieve a ranked set of answers satisfying the user preferences. To the best of our knowledge, this work is the rst attempt to translate the semantics of a CP-net into a SPARQL query.

Let us also mention that there exist some works (cf., [START_REF] Chen | Eciently evaluating skyline queries on RDF databases[END_REF]) that propose methods for the optimization of skyline queries in an RDF data context.

Query Relaxation

Nowadays, the size and the complexity of databases (including relational, semantic, etc.)

increase over time at a sustained pace. In such circumstances, users when querying these databases do not have enough knowledge about their content and structure. So, they fail sometimes to formulate meaningful queries to get the expected result or even to avoid empty responses.

In order to cope with these issues, some of the semantic Web systems include a query relaxation process for triple-pattern queries (i.e., adressed to data represented in the RDF format) sharing the same principle as the cooperative querying systems [START_REF] Gaasterland | Relaxation as a platform for cooperative answering[END_REF] [ Godfrey, 1997] [Chu et al., 1996] [Kleinberg, 1999] that operate on relational databases.

These systems aim to automate the relaxation process of user queries when the selection criteria in the query do not make it possible to obtain answers that meet the user's needs.

In a SPARQL/RDF setting, several works have been carried out [START_REF] Hurtado | A relaxed approach to RDF querying[END_REF], Hurtado et al., 2008, Huang et al., 2008, Poulovassilis and Wood, 2010, Calì et al., 2014, Frosini et al., 2017] that propose a relaxation framework for RDF data through RDFS entailment using information provided by a given ontology (see Figure 2.4) and being characterized by RDFS inferences rules (see Table 2.2). These rules enable a generalization of the SPARQL query in order to release its conditions in case of an empty result.

Group A (Subproperty)

(a,sp,b)(b,sp,c) (a,sp,c) (1)
(a,sp,b)(x,a,y) (x,b,y) Group B (Subclass) (3) (a,sc,b)(b,sc,c) (a,sc,c) (2)
(a,sc,b)(x,type,a) (x,type,b) (4)
Group C (T yping)

(a,dom,c)(x,a,y) (x,type,c)

(a,range,d)(x,a,y) (y,type,d) x is an instance of a, then, x is an instance of b. [START_REF] Hurtado | A relaxed approach to RDF querying[END_REF], Hurtado et al., 2008] is interested in the relaxation of a conjunctive fragment of queries over RDF data (e.g., See [START_REF] Gutierrez | Foundations of semantic web databases[END_REF], Haase et al., 2004]).

This type of queries has the following expression H ← B, where B is a graph pattern (i.e., a set of triples including URIs, literals, blanks nodes, and variables) and H = H 1 , ..., H n is a list of variables. It rstly aims to nd matchings from the graph pattern (i.e., the body of the query B ) to the data and, secondly, applies these matchings to the head of the query (H ) in order to get the nal answers.

The authors propose to extend these conjunctive queries by introducing (one or several) relax clauses in the place of the optional clauses. This extension is detailed in the following example.

Example 37 In order to avoid empty answers for some cases, a relaxation of some conditions using a specic ontology (see Figure 2.4) is needed. This ontology is represented in the form of an RDF graph based on an RDFS vocabulary that models documents along with properties that model dierent ways people contribute to them (e.g., as authors, editors, etc.).

Thanks to this ontology, the following query may be generalized and relaxed in the following way: ?Z, ?Y ← {(?X, name , ?Z), relax {(?X, proceedingsEditorOf , ?Y)}}.

The relax clause aims to return rstly editors of conference proceedings. Then, one can automatically rewrite the triple (?X, proceedingsEditorOf , ?Y) into (?X, editorOf, ?Y) or (?X, contributorOf, ?Y) since proceedingsEditorOf is a subproperty of editorOf and editorOf is a subproperty of contributorOf according to the ontology and rules from Table 2.2. So, the relaxed query allows to obtain people who are editors of a publication or in a more general way contributors to a document.

The query relaxation strategy involves two types of relaxations:

• simple type without using an ontology, which includes dropping triple patterns using the optional clause, replacing constants with variables in a triple pattern, etc.

• more complex type using an ontology and inference rules, which includes:

Type relaxation for example, following rule (4) from Predicate to range relaxation for example, using rule ( 6) from Table 2.2, the triple pattern (JohnRobert, editorOf, ?Y ) can be relaxed into (?Y, type, Publication) since we have (editorOf, range, Publication) ∈ cl(O).

For the purpose of incrementally computing the relaxed answers to the query, an algorithm is presented, which eciently orders the answers according to how closely they meet the query conditions.

In, [START_REF] Huang | Computing relaxed answers on RDF databases[END_REF] the authors points out that the approaches proposed in [START_REF] Hurtado | A relaxed approach to RDF querying[END_REF], Hurtado et al., 2008] may still be insucient. They propose a new similarity measure that requires computing the semantic similarity between the relaxed query and the original one. This measure makes it possible to reduce the number of answers as much as possible (or to the desired cardinality) and, then, ensure the quality of answers during the relaxation process.

More recently, [START_REF] Reddy | Ecient approximate SPARQL querying of web of linked data[END_REF] proposed an extension of the work [START_REF] Huang | Computing relaxed answers on RDF databases[END_REF] to the web of linked data, where they dene an optimized query processing algorithm in which the relaxed queries are generated and answered on-the-y during query execution (at run time). This work diers from the approach of [START_REF] Huang | Computing relaxed answers on RDF databases[END_REF],

which is dedicated only to centralized RDF repositories and aims to generate multiple relaxed queries and execute them sequentially one by one.

Another related work is that by [START_REF] Dolog | Robust query processing for personalized information access on the semantic web[END_REF], Dolog et al., 2009], where the authors present user centered process for automatically relaxing over-constrained RDF queries. This relaxation is carried out by rewriting rules for making patterns optional, replacing value, replacing patterns or predicate and deleting patterns or predicate. Background knowledge about the domain of interest and the preferences of the user are taken into account during the query relaxation to rene and guide this process.

From a dierent perspective, [START_REF] Poulovassilis | Combining approximation and relaxation in semantic web path queries[END_REF], introduce a framework wherein relaxations and approximations of regular path queries are combined in order to get a more exible querying of RDF data when the user lacks knowledge of their structure. [START_REF] Frosini | Flexible query processing for SPARQL[END_REF], Calì et al., 2014], rely on the work of [START_REF] Poulovassilis | Combining approximation and relaxation in semantic web path queries[END_REF] and propose a formal syntax and semantics of SP ARQL AR which is an extension of the query language SPARQL 1.1 (i.e., SPARQL with property path queries) with query approximation and query relaxation operators. A relaxation operator relies on RDF inference rules and follows the principle presented in [START_REF] Hurtado | Query relaxation in RDF[END_REF] and the approximation operator aims to transform a regular expression pattern P into a new expression pattern P using a set of edit operations (e.g., deletion, insertion and substitution).

In [START_REF] Hogan | Towards fuzzy query-relaxation for RDF[END_REF], the authors base their relaxation framework on an industrial use-case from the European Aeronautic Defence and Space Company (EADS) that involve human observations which are presented in the form of natural language and may be imprecise Some contributions also address the problem of providing a guide for the user to relax his/her query. [START_REF] Elbassuoni | Query relaxation for entity-relationship search[END_REF] propose a novel approach for query relaxation based on statistical language models (LMs) for structured RDF data in an automated way. This approach generates a set of relaxation candidates which can be derived from the RDF data and also from external sources like ontologies and textual documents.

From another angle, [START_REF] Fokou | Cooperative techniques for SPARQL query relaxation in RDF databases[END_REF], Fokou et al., 2017, Fokou et al., 2017] are inspired by some prior works in relational databases [Godfrey, 1997, Pivert and[START_REF] Pivert | [END_REF] and recommendation systems [Jannach, 2009] and they deal with the problem of explaining the failure of RDF queries in order to help the user to relax his/her query. In [START_REF] Fokou | Endowing semantic query languages with advanced relaxation capabilities[END_REF], the authors initially proposed an extension of SWDB (Semantic Web Database) query languages with new operators that allow to control the relaxation process. These operators describe the relaxation by specifying the part of the query to relax and the technique of relaxation to be used. Then, in [START_REF] Fokou | Cooperative techniques for SPARQL query relaxation in RDF databases[END_REF]] [Fokou et al., 2017] the authors addressed the problem of computing the Minimal Failing Subqueries (MFS) and the Maximal Succeeding Subqueries (XSSs) (i.e., which return non-empty answers) that are used to nd the parts of an RDF query that are responsible of the failure on the one hand, and the relaxed queries that are guaranteed to return a nonempty result on the other hand.

Approximate Matching

In the literature, the concept of graph isomorphism has been studied for a long time, cf., [Read andCorneil, 1977] [Fortin, 1996] [START_REF] Zhu | An approach for semantic search by matching RDF graphs[END_REF], De Virgilio et al., 2013, De Virgilio et al., 2015, Zheng et al., 2016].

[ [START_REF] Zhu | An approach for semantic search by matching RDF graphs[END_REF] introduces an approach for semantic search. The idea is to match RDF graphs in order to verify whether each candidate resource RDF graph matches the query RDF graph. The resource RDF graph is built up from a specic domain Web information and the query RDF graph corresponds to a user query. To do this, a new semantic similarity measure between two RDF graphs, based on an ontology has been dened. This measure takes into account the similarities between edges and also nodes.

The approach proposed in [START_REF] Zhu | An approach for semantic search by matching RDF graphs[END_REF] only takes the similarity of nodes and edges into account in an RDF graph but ignores the structure formed by the nodes and the edges.

To deal with this issue, [De Virgilio et al., 2013, De Virgilio et al., 2015] propose an approach dealing with approximate query answering in the context of large RDF data sets. This approach aims to measure the similarity between a portion of a (large) graph representing an RDF dataset and a sub-graph representing a query by applying substitutions and transformations to the paths of the latter. This operation is based on a scoring function that simulates the relevance of answers by taking into account two aspects: i) quality that measures how much the paths retrieved align with the paths in the query and ii) conformity that measures how much the combination of paths retrieved is similar to the combination of the paths in the query.

A more recent work is [START_REF] Zheng | Semantic SPARQL similarity search over RDF knowledge graphs[END_REF], where the authors focus on the problem of Semantic SPARQL Similarity Search over RDF knowledge graphs. They propose a metric, semantic graph edit distance in order to measure the similarity between RDF graphs. This metric consider the graph structural, concept-level and semantic similarities in a uniform manner.

Conclusion

In this chapter, we reviewed several approaches from the literature that aim to query RDF data in a more expressive and exible way, either by introducing fuzzy user preferences, relaxing some preferences or applying approximate matching. We present a summary of these approaches in Table 2. 3.

.3: Main features of the preference query approaches

A rst observation concerns the limited expressiveness of the approaches. Indeed, all of them are straightforward adaptations of proposals made in the relational database context: they make it possible to express preferences on the values of the nodes, but not on the structure of the RDF graph (structural preferences may concern the strength of a path, the centrality of nodes, etc).

Some of the relaxation approaches (e.g., [START_REF] Poulovassilis | Combining approximation and relaxation in semantic web path queries[END_REF], [START_REF] Calì | Flexible querying for SPARQL[END_REF] and [START_REF] Frosini | Flexible query processing for SPARQL[END_REF]), and approximation approaches (e.g., [De Virgilio et al., 2013], [De Virgilio et al., 2015] and [START_REF] Zheng | Semantic SPARQL similarity search over RDF knowledge graphs[END_REF]) have considered this issue but only in a crisp way.

A second important remark is that all of the approaches presented above only deal with crisp RDF data. However, we believe that there is a real need for a exible SPARQL that takes into account RDF graphs where data is described by intrinsic weighted values, attached to edges or nodes. This weight may denote any gradual notion like a cost, a truth value, an intensity or a membership degree.

The RDF data model should thus be enriched in order to represent gradual information, and new query languages should be dened. A rst step in this direction is the approach proposed in [START_REF] Cedeño | R2DF framework for ranked path queries over weighted RDF graphs[END_REF] where the authors propose an extension of the RDF model embedding weighted edges and an extension of SPARQL to support this feature, allowing new path predicates to express nodes reachability and the ability to express ranked queries. This approach takes the weights into account in order to rank the answers, but does not propose any means to express preferences in user queries.

To the best of our knowledge, none of the existing approaches aims to dene a general purpose exible version of SPARQL to weighted RDF databases, which is the rst contribution of this thesis.

Introduction

Aswes In the literature, several types of approaches have been devoted to extending the SPARQL language among which: i) those that extend the research patterns with paths involving regular expressions, ii) those that consider fuzzy conditions. However, to the best of our knowledge, no approach cover both aspects at the same time.

In this chapter, we intend to tackle this issue and we propose the FURQL query language which is a fuzzy extension of SPARQL that improves its expressiveness and usability. This In the following, in Section 3.1, we rst present the notion of the fuzzy RDF data model and then, in Section 3.2, we provide the syntax and the semantics of the FURQL query language.

Fuzzy RDF (F-RDF) Graph

The classical crisp RDF model is only capable of representing Boolean notions whereas real-world concepts are often of a vague or gradual nature. This is why several authors have proposed fuzzy extensions of the RDF model. Throughout the thesis, we consider the data model based on Denition 4 which synthesizes the existing fuzzy RDF models of literature ( [START_REF] Mazzieri | A fuzzy semantics for semantic web languages[END_REF], [START_REF] Udrea | Annotated RDF[END_REF], [START_REF] Mazzieri | A fuzzy semantics for the resource description framework[END_REF], [START_REF] Lv | Fuzzy RDF: A data model to represent fuzzy metadata[END_REF], [Straccia, 2009], [START_REF] Udrea | Annotated RDF[END_REF], [START_REF] Zimmermann | A general framework for representing, reasoning and querying with annotated semantic web data[END_REF]), whose common principle consists in adding a fuzzy degree to edges, modeled either by a value embedded in each triple or by a function associating a satisfaction degree with each triple, expressing the extent to which the fuzzy concept attached to the edge is satised.

Example 38 [Fuzzy RDF triple] The corresponding fuzzy RDF triple ( Beyonce, recommends, Euphoria , 0.8) states that Beyonce, recommends, Euphoria is satised to the degree 0.8, which could be interpreted as Beyonce strongly recommends Euphoria.

Denition 4 (Fuzzy RDF (F-RDF) graph ). A F-RDF graph is a tuple

(T , ζ) such that (i) T is a nite set of triples of (U ∪ B) × U × (U ∪ L ∪ B), (ii) ζ is a membership function on triples ζ : T → [0, 1].
According to the classical semantics associated with fuzzy graphs, ζ(t) qualies the intensity of the relationship involved in the statement t. Intuitively, ζ attaches fuzzy degrees to the edges of the graph. Having a value of 0 for ζ is equivalent to not belonging to the graph. Having a value of 1 for ζ is equivalent to fully satisfying the associated concept. In the graph G M B of Figure 3.1, such edges appear as classical ones, i.e., with no degree attached.

The fuzzy degrees associated with edges are given or calculated. A simple case is when, each degree is based on a simple statistical notion, e.g., the intensity of friendship between two artists may be computed as the number of their common friends over the total number of friends with respect to each artist. Remark 5. In the same way as the RDF graph, an F-RDF graph is said to be ground if it contains no blank nodes. Such a graph may be ground at the beginning or made ground e.g. by a skolemization procedure. In the following, we only consider ground fuzzy RDF graphs.

JulioI

Example 39 [Fuzzy RDF graph] Figure 3.1 is an example of a fuzzy RDF graph inspired by MusicBrainz 1 . This graph, denoted by G M B in the following, mainly contains artists and albums as nodes. For readability reasons, each URI node contains the value of its name instead of the URI itself. Literal values may be attached to an URI, like the age of an artist, the release date or the global rating of an album. The graph contains fuzzy relationships (e.g., friend, likes, recommends, memberOf ) as well as crisp ones (e.g., creator, date, . . . ). We limit our example to some entities including artists and albums and omit URI prexes to avoid overcrowding the gure.

In order to create this graph, we started from a MusicBrainz nonfuzzy subgraph for which every relationship between nodes was Boolean and, then, we made it fuzzy by adding satisfaction degrees denoting the intensity of some relationships.

Here for instance,

• the degree associated with an edge of the form Art1friend → Art2 is the proportion of common friends (i.e., Boolean relationship) between Art1 and Art2 over the total number of friends of Art1 ;

• the degree associated with an edge of the form Art -memberOf → Group is the number of years the artist stayed in this group over the number of years this group has been existing;

• the degree associated with an edge of the form Art1likes → Art2 is the number of albums by Art2 that Art1 has liked over the total number of albums by Art2;

• the degree associated with an edge of the form Artrecommends → Alb is the number of stars given by Art to Alb over the maximum number of stars.

In the following, we rely on classical notions from fuzzy graph theory [Rosenfeid, 2014], which are the path, the distance and the strength (ST) of the connection between two nodes respectively given in Denitions 5,6 and 7. Denition 5 (Path between two nodes). Let G be an F-RDF data graph.

Classically, a path p in G corresponds to a possibly empty sequence of triples

(t 1 , • • • , t k , • • • , t n ) such that {t i | 1 ≤ i ≤ n} ⊆ G and for all 1 ≤ k ≤ n -1, the object of t k is the subject of t k+1 .
Given two nodes x and y, P aths(x, y) denotes the set of cycle-free paths 2 in G connecting x to y, i.e., the set of paths of the form (t length(p)

1 , • • • , t k , • • • , t n ) such that x is the subject of t
(3.1)
where length(p) is the length of a path p in a fuzzy graph [Rosenfeid, 2014], dened by .2) The distance between two nodes is the length of the shortest path between these two nodes.

length(p) = t∈p 1 ζ(t) . ( 3
Remark 6. In a crisp RDF graph (when ζ(t) ∈ {0, 1}), which is a special case of a fuzzy RDF graph, the distance between two nodes x and y given in Denition 6 is still valid and it expresses the number of edges between these nodes (which corresponds to the classical denition).

Denition 7 (Strength between two nodes). The strength between two nodes x and y is dened by ST (x, y) = max p∈P aths(x,y)

ST _path(p) (3.3) where ST _path(p) is the strength of the path connecting x and y in a fuzzy graph [Rosenfeid, 2014], dened by

ST _path(p) = min({ζ(t)|t ∈ p} (3.4)
The strength of a path is dened to be the weight of the weakest edge of the path.

Example = min(0.8, 0.3, 0.5, 1) = 0.3.

Thus, the strength between the pair of nodes (Beyonce, Euphoria) is ST(Beyonce, Euphoria)= 0.8.

Here, the distance and the strength correspond to the same path, but it is of course not necessarily the case in general.

Let us also mention that except for introducing the degree of truth within an RDF triple in case of imprecise information, several other extensions of RDF were proposed in the literature in order to deal with:

• time ( [START_REF] Gutierrez | Introducing time into RDF[END_REF], [START_REF] Pugliese | Scaling RDF with time[END_REF], [START_REF] Tappolet | Applied temporal RDF: Ecient temporal querying of RDF data with SPARQL[END_REF]) to represent the validity periods of time of the information brought by the triple dened by an interval (containing the start and the end point of validity of this information),

• trust [Hartig, 2009], used in case of uncertainty about the trustworthiness of the RDF triples. It is represented by a trust value which is either unknown or a value in the interval [-1, 1], where -1 encodes a full disbelief in the triple, 1 a total belief in the triple and 0 signies the lack of belief as well as the lack of disbelief; and,

• provenance [START_REF] Dividino | Querying for provenance, trust, uncertainty and other meta knowledge in RDF[END_REF]: may contain information attached to an RDF triple (such as, origins/source (Where is this information from?), authorship (Who provided the information?), time (When was this information provided?), and others).

Moreover, [START_REF] Udrea | Annotated RDF[END_REF] and [START_REF] Zimmermann | A general framework for representing, reasoning and querying with annotated semantic web data[END_REF] provided a single theoretical framework to handle the aforementioned extensions along with an extension of the RDF query language to deal with such a framework.

FUzzy RDF Query Language (FURQL)

In this section, we introduce the FURQL query language, and we formally study its expressiveness. FURQL is based on the notion of fuzzy graph pattern, which is a fuzzy extension of the SPARQL graph pattern notion introduced in [START_REF] Pérez | Semantics and complexity of SPARQL[END_REF] and [START_REF] Arenas | Querying semantic web data with SPARQL[END_REF] which present it in a more traditional algebraic formalism than the ocial syntax does [W3C, 2014]. In the following, we redened the associated syntax and semantics in order to introduce fuzzy preferences expressed over the F-RDF data model of Denition 4.

Syntax of FURQL

FURQL (Fuzzy RDF Query Language) consists in extending SPARQL graph patterns into fuzzy graph patterns. Before formally introducing the syntax of FURQL, we rst need to dene the notion of a fuzzy graph pattern.

A fuzzy graph pattern allows to express fuzzy preferences on the entities of an F-RDF graph (through fuzzy conditions) and on the structure of the graph (through fuzzy regular expressions). It considers the following binary operators: and (SPARQL concatenation), union (SPARQL union), opt (SPARQL optional) and filter (SPARQL filter). We fully parenthesize expressions making explicit the precedence and association of operators.

In the following, we assume the existence of an innite set V of variables such that V ∩ (U ∪ L) = ∅. By convention, we prex the elements of V by a question mark symbol.

Let us rst dene the notion of a fuzzy regular expression.

Denition 8 (Fuzzy regular expression). The set F of fuzzy regular expression patterns, dened over the set U of URIs, is recursively dened by:

• is a fuzzy regular expression of F;

• u ∈ U and '_' are fuzzy regular expressions of F;

• if A ∈ F and B ∈ F then A|B, A.B, A * , A cond are fuzzy regular expressions of F.

Above, denotes the empty pattern, the character '_' denotes any element of U, A|B denotes alternative expressions, A.B denotes the concatenation of expressions, A * stands for the classical repetition of an expression (the Kleene closure), A cond denotes paths satisfying the pattern A with a condition cond where cond is a Boolean combination of atomic formulas of the form: sprop is F term where sprop is a structural property of the path dened by the expression and F term denotes a predened or user-dened fuzzy term like short (see Figure 3.3). In the following, we limit the path structural properties to ST (see Denition 7) and distance (see Denition 6). Examples of conditions of this form are distance IS short and ST IS strong. We denote by A + the classical shortcut for A.

• A fuzzy triple from (U ∪ V) × (U ∪ F ∪ V) × (U ∪ L ∪ V
) is a fuzzy graph pattern.

• If P 1 and P 2 are fuzzy graph patterns then (P 1 and P 2 ), (P 1 union P 2 ) and

(P 1 opt P 2 ) are fuzzy graph patterns. Fuzzy connectives include of course fuzzy conjunction ∧ (resp. disjunction ∨), usually interpreted by the triangular norm minimum (resp. maximum), but also many other operators that may be used for expressing dierent kinds of trade-os, such as the weighted conjunction and disjunction [START_REF] Dubois | Weighted minimum and maximum operations in fuzzy set theory[END_REF], mean operators, fuzzy quantiers [START_REF] Fodor | Fuzzy-set theoretic operators and quantiers[END_REF], or the non-commutative connectives described in [START_REF] Bosc | On four noncommutative fuzzy connectives and their axiomatization[END_REF].

Given a pattern P (which can be a fuzzy triple pattern in particular), var(P ) denotes the set of variables occurring in P .

Example 42 [Fuzzy graph pattern] Let us consider P rec_low the fuzzy graph pattern dened by (?Art1, (f riend + ) distance is short .creator, ?Alb) AND (?Art1, recommends, ?Alb) AND ((?Alb, rating, ?r) FILTER (?r IS low)), of which Syntactically, FURQL naturally extends SPARQL, by allowing the occurrence of fuzzy graph patterns (which may contain fuzzy regular expressions) in the where clause and the occurrence of fuzzy conditions in the filter clause. A fuzzy regular expression is close to a property path, as dened in SPARQL 1.1 [Harris and Seaborne, 2013], but involves a fuzzy structural property (e.g. distance and strength over fuzzy graphs).

The general syntactic form of a FURQL query is given in Listing 3. 1. a list of define clauses that makes it possible to dene the fuzzy terms. If a fuzzy term fterm has a trapezoidal function dened by the quadruple (A-a, A, B and B+b)

meaning that its support is [A-a, B+b] and its core [A, B] , then the clause has the form define fterm as (A-a,A,B,B+b). If fterm is a decreasing function, like the term low of Figure 3.5, then, the clause has the form definedesc fterm as (δ,γ) (there is the corresponding defineasc clause for increasing functions). 1 definedesc low as (2, 8) 2 defineasc short as (3, 5) 3 select ?art1 where { 4 { ?art1 (friend+ | distance is short) ?art2 . 5

?art2 creator ?alb .

6

?alb rating ?r .

7

?art1 recommends ?alb . } 8 filter (?r is low) 9 } cut 0.4

Listing 3.2: A FURQL query containing P rec_low

In this example, the definedesc clause of line 1 denes the fuzzy term low of The pattern from lines 3 to 8 is the fuzzy pattern of Example 42. Line 9 species an α-cut of the fuzzy pattern with a satisfaction degree greater or equal to 0.4.

Semantics of FURQL

To dene the semantics of FURQL, we need to dene the semantics of fuzzy graph patterns.

Intuitively, given an F-RDF data graph G, the semantics of a fuzzy graph pattern P denes a set of mappings, where each mapping (from var(P ) to URIs and literals of G) maps the pattern to an isomorphic subgraph of G. For introducing such a concept, the notion of satisfaction of a fuzzy regular expression must rst be dened.

Denition 10 (Fuzzy regular expression matching of a path). Let G = (T , ζ) be an F-RDF graph and exp be a fuzzy regular expression. Let p = ( s 1 , p • exp is of the form .

If p is empty then sat exp (p) = 1 else sat exp (p) = 0.

• exp is of the form u ∈ U (resp. _).

If p 1 is u (resp. any u ∈ U) then sat exp (p) = ζ( s 1 , p 1 , o 1 ) else 0.
• exp is of the form f 1 .f 2 .

Let P be the set of all pairs of paths (p 1 , p 2 ) s.t. p is of the form p 1 p 2 . One has sat exp (p) = max P (min(sat f 1 (p 1 ), sat f 2 (p 2 ))).

• exp is of the form f 1 ∪ f 2 .

One has sat exp (p) = max(sat f 1 (p), sat f 2 (p)).

• exp is of the form f * .

If p is the empty path then µ exp (p) = 1. Otherwise, we denote by P the set of all tuples of paths (p

1 , • • • , p n ) (n > 0) s.t. p is of the form p 1 • • •p n . One has sat exp (p) = max P (min i∈[1..n] (sat exp (p i ))).
• exp is of the form f Cond where Cond is a fuzzy condition. sat exp (p) = min(sat f (p), µ Cond (p)) where µ Cond (p) denotes the degree of satisfaction of cond by p.

Again, not satisfying is equivalent to getting a degree of 0.

Denition 11 (Satisfaction of a fuzzy regular expression by a pair of nodes). Let G = (T , ζ)

be an F-RDF graph and exp be a fuzzy regular expression. Let (x, y) be a pair of nodes of G. The statement the pair (x, y) satises exp with a satisfaction degree of sat exp (x, y) is dened by sat exp (x, y) = max p∈P aths(x,y) sat exp (p).

Note that only cycle-free paths need to be considered in order to compute the satisfaction degree.

Example Expression f 1 = (friend + ).creator is a fuzzy regular expression. A pair of nodes (x, y) satises f 1 if x has a friend-linked artist (an artist connected to x with a path made of friend edges), that created the album y. All of the pairs of nodes (EnriqueI, Justied), (Shakira, Buttery), (Beyonce, Euphoria), (Rihanna, Euphoria), (MariahC, Euphoria) and (Shakira, Euphoria), illustrated in Figure 3 = min(0.5, 1) = 0.5.

Expression f 2 = (friend + ) distance is short .creator is a fuzzy regular expression. A pair of nodes (x, z) satises f 2 if x has a close friend artist y that created an album z, close meaning that x is connected to y by a short path made of friend edges (the term short is dened in Figure 3.3 on page 68). It is worth noticing that expression f 1 is a sub-expression of expression f 2 , so we are going to make use of the satisfaction degree of f 1 , denoted by sat f 1 , in order to calculate the satisfaction degree of f 2 , denoted by sat f 2 .

According to the paths depicted in Figure 3.6:

• the length of pair (EnriqueI, Justied) = 1/0.4 + 1 = 3.5, µ short (3.5) = 0.75 and sat f 1 (EnriqueI, Justied) = 0.4, then, sat f 2 (EnriqueI, Justied) = min(0.75, 0.4) = 0.4,

• the length of pair (Shakira, Buttery)= 1/0.7 + 1 = 2.4, µ short (2.4) = 1 and sat f 1 (Shakira, Buttery) = 0.7, then, sat f 2 (Shakira, Buttery) = min(1, 0.7) = 0.7,

• the length of pair (Beyonce, Euphoria) = 1/0.6 + 1/0.2 + 1 = 7.7, µ short (7.7) = 0 and sat f 1 (Beyonce, Euphoria) = 0.3, then, sat f 2 (Beyonce, Euphoria) = min(0, 0.3) = 0,

• the length of pair (Rihanna, Euphoria) = 1/0.2 + 1 = 6, µ short (6) = 0 and sat f 1 (Rihanna, Euphoria)=0.2, then, sat f 2 (Rihanna, Euphoria) = min(0, 0.2) = 0,

• the length of pair (MariahC, Euphoria)= 1/0.3 + 1/0.5 + 1= 6.33, µ short (6.33) = 0 and sat f 1 (MariahC, Euphoria) = 0.3, then, sat f 2 (MariahC, Euphoria) = min(0, 0.3) = 0, and • the length of pair (Shakira, Euphoria) = 1/0.5 + 1 = 3, µ short (3) = 1 and sat f 1 (Shakira, Euphoria) = 0.5, then, sat f 2 (Shakira, Euphoria) = min(1, 0.5) = 0.5.

Then, the pairs of nodes (EnriqueI, Justied), (Shakira, Buttery) and (Shakira, Euphoria) are the only ones that match the fuzzy regular expression f 2 and their satisfaction degrees are sat f 2 (EnriqueI, Justied) = 0.4, sat f 2 (Shakira, Buttery) = 0.7 and sat f 2 (Shakira, Euphoria) = 0.5 respectively.

Expression f 3 = (f riend+) ST >0. 65 .creator is a fuzzy regular expression. A pair of nodes (x, y) satises f 3 if x has a friend artist (an artist connected to x with a path made of friend edges which has a strength higher than 0.65), who created the album y. It is worth noticing that expression f 1 is a sub-expression of expression f 3 , so we are going to make use of the satisfaction degree of f 1 (denoted by sat f 1 ) in order to calculate the satisfaction degree of f 3 (sat f 3 ). The pair of nodes (Shakira, Buttery), shown in Figure 3.6, is the only one that matches the fuzzy regular expression f 3 with a non zero satisfaction degree: sat f 3 (Shakira, Buttery) = 0.7, where the strength between the pair of nodes (Shakira, Buttery)= min (0.7,1)= 0.7 and sat f 1 (Shakira, Buttery) = 0.7, then, sat f 3 (Shakira, Buttery) = min (0.7, 0.7) =0.7.

Let us now come to the denition of a mapping. A mapping is a pair (m, d) where m : V → (U × L) and d ∈ [0, 1]. Intuitively, m maps the variables of a fuzzy graph pattern into a subgraph (answer) of the F-RDF data graph and d denotes the satisfaction degree associated with the mapping (the more satisfactory the subgraph, the higher the satisfaction degree). The expression m(t), where t is a triple pattern, denotes the triple obtained by replacing each variable x of t by m(x). The domain of a mapping m denoted by dom(m) is the subset of V for which m is dened. Two mappings m 1 and m 2 are compatible i for all ?v ∈ dom(m 1 ) ∩ dom(m 2 ), one has m 1 (?v) = m 2 (?v). Intuitively, m 1 and m 2 are compatible if m 1 can be extended with m 2 to obtain a new mapping m 1 ⊕m 2 and vice versa.

Let M 1 and M 2 be two fuzzy sets of mappings. We dene the join, union, dierence and left outer-join of M 1 with M 2 as:

Join

M 1 M 2 ={(m 1 ⊕ m 2 , min(d 1 , d 2 )) | (m 1 , d 1 ) ∈ M 1 and (m 2 , d 2 ) ∈ M 2 and m 1 , m 2 are compatible}.
The operation M 1 M 2 denotes the set of new mappings that result from extending mappings in M 1 with their compatible mappings in M 2 .

Union

M 1 ∪ M 2 ={(m, d) | (m, d) ∈ M 1 and m ∈ support(M 2 )} ∪ {(m, d) | (m, d) ∈ M 2 and m ∈ support(M 1 )} ∪ {(m, max(d 1 , d 2 )) | (m, d 1 ) ∈ M 1 and (m, d 2 ) ∈ M 2 }
Here, ∪ corresponds to the classical set-theoretic union and support denotes the support of a fuzzy set of mappings and corresponds to the set of all elements of the universe of discourse whose their grade of membership is greater than zero.

Dierence

M 1 \M 2 ={(m 1 , d 1 ) | (m 1 , d 1 ) ∈ M 1 and ∀(m 2 , d 2 ) ∈ M 2 , m 1 and m 2 are not compatible}.
M 1 \M 2 returns the set of mappings in M 1 that cannot be extended with any mapping in M 2 .

Leftouterjoin

M 1 M 2 = (M 1 M 2 ) ∪ (M 1 \M 2 ).
A mapping m is in M 1 M 2 if it is the extension of a mapping of M 1 with a compatible mapping of M 2 , or if it is in M 1 and cannot be extended with any mapping of M 2 .

Denition 12 (Mapping satisfying a fuzzy condition). Let m be a mapping and C be a fuzzy condition. Then m satises the fuzzy condition C with a satisfaction degree dened as follows, according to the form of C:

• C is of the form bound(?x): if ?x ∈ dom(m) then m satises the condition C with a degree of 1, else 0.

• C is of the form ?x θ c (where θ is a (possibly fuzzy) comparator and c is a constant): if ?x ∈ dom(m) then m satises the condition C with a degree of µ θ (m(?x), c), else 0.

• C is of the form ?x θ ?y: if ?x ∈ dom(m) and ?y ∈ dom(m), then m satises the condition C with a degree of µ θ (m(?x), m(?y)), else 0.

• C is of the form ?x is F term: if ?x ∈ dom(m) then m satises the condition C to the degree µ F term (m(?x)) (which can be 0).

• C is of the form ¬C 1 or C 1 C 2 where is a fuzzy connective: we use the usual interpretation of the fuzzy operator involved (complement to 1 for the negation, minimum for the conjunction, maximum for the disjunction, etc [START_REF] Fodor | Fuzzy-set theoretic operators and quantiers[END_REF]).

Denition 13 (Evaluation (interpretation) of a fuzzy graph pattern). The evaluation of a fuzzy graph pattern P over an F-RDF graph, denoted by P G is recursively dened by:

• if P is of the form of a (crisp) triple graph pattern t ∈ (U ∪ V) × (U ∪ V) × (U × L × V)
then P G = {(m, 1) | dom(m) = var(t) and m(t) ∈ G},

• if P is of the form of a fuzzy triple graph pattern t ∈ (U ∪ V) × F × (U × L × V)
denoted by ?x, exp, ?y (where variables occur as subject and object) then P G = {(m, d) | dom(m) = {?x, ?y} and (m(?x), m(?y)) satises exp with a satisfaction degree d = sat exp (x, y)}. The case where the subject (resp. the object) of t is a constant of U (resp. U ∪ L) is trivially induced from this denition.

• if P is of the form (P 1 and P 2 ) then

P G = P 1 G P 2 G ,
• if P is of the form (P

1 opt P 2 ) then P G = P 1 G P 2 G ,
• if P is of the form (P 1 union P 2 ) then

P G = P 1 G ∪ P 2 G , • if P is of the form (P 1 filter C) then P G = {(m, d) | m ∈ P G and m satises C
to the degree of d}.

Intuitively, expressions (P 1 and P 2 ), (P 1 union P 2 ), (P 1 opt P 2 ), and (P 1 filter C) refer to conjunction graph patterns, union graph patterns, optional graph patterns, and lter graph patterns respectively. Optional graph patterns allow for a partial match of the query (i.e., the query tries to match a graph pattern and does not omit a solution when some part of the optional pattern is not satised).

Remark 7. Note that a crisp graph pattern is a special case of a fuzzy graph pattern where no fuzzy term or condition occurs (and thus, according to the previous denition, an answer necessarily has a satisfaction degree of 1).

Example 45 [Evaluation of a fuzzy graph pattern] Let us recall the fuzzy graph pattern P rec_low from Example 42 dened by (?Art1, (f riend + ) distance is short .creator, ?Alb) AND (?Art1, recommends, ?Alb) AND ((?Alb, rating, ?r) FILTER (?r is low)), for which Figure 6.3 is a graphical representation. It can be represented as follows:

P rec_low G M B = { ({?Art1 → EnriqueI , ?Alb → Justied, ?r → 6}, 0.33), ({?Art1 → Shakira , ?Alb → Buttery, ?r → 4}, 0.66)}.

Note that the mapping {?art1 → Shakira, ?alb → Euphoria, ?r → 9} is excluded from the result of the evaluation of the pattern P rec_low since µ low_rating (9) = 0.

Conclusion

In this chapter, we have introduced a new query language named FURQL which is a fuzzy extension of SPARQL that goes beyond the previous proposals in terms of expressiveness inasmuch as it makes it possible i) to deal with crisp and fuzzy RDF data, and ii) to express fuzzy structural conditions beside more classical fuzzy conditions on the values of the nodes present in the graph.

We rst presented the notion of a fuzzy RDF graph that makes it possible to model relationships between entities and then, we formalized a formal syntax and semantics of FURQL based on the notion of fuzzy graph pattern, which extends Boolean graph patterns introduced by several authors in a crisp querying context. Associated implementation issues and experiments will be presented in Chapter 5. In the following chapter, we propose to extend the FURQL query language to be able to express more sophisticated fuzzy conditions, namely fuzzy quantied statements.

Introduction

Fuzzyquant ied queries have been long recognized for their ability to express dierent types of imprecise and exible information needs in a relational database context. However, in the specic RDF/SPARQL setting, the current approaches from the literature that deal with quantied queries consider crisp quantiers only [START_REF] Bry | SPARQLog: SPARQL with rules and quantication[END_REF], Fan et al., 2016] over crisp RDF data.

In the present chapter, we integrate fuzzy quantied statements in FURQL queries addressed to a fuzzy RDF database. We show how these statements can be dened and implemented in FURQL, which is a fuzzy extension of the SPARQL query language that we previously presented in Chapter 3. This work has been published in the proceedings of the 26th IEEE International Conference on Fuzzy Systems (Fuzz-IEEE'17), Naples, Italy, 2017.

In the following, in Section 4.1 we rst present a refresher on fuzzy quantied statements in a relational database context, then, in Section 4.2 we introduce the syntactic format for expressing fuzzy quantied statements in the FURQL language and we describe their interpretation using dierent approaches from the literature. 4.1 Refresher on Fuzzy Quantied Statements In this section, we recall important notions about fuzzy quantiers, then, we present three approaches that have been proposed in the literature for interpreting fuzzy quantied statements. 4.1.1 Fuzzy Quantiers Fuzzy logic extends the notion of quantier from Boolean logic (e.g., ∃ and ∀) and makes it possible to model quantiers from the natural language such as most of, at least half, few, around a dozen, etc.

In [Zadeh, 1983], the author distinguishes between absolute and relative fuzzy quantiers.

Absolute quantiers refer to a number while relative ones refer to a proportion. Quantiers may also be increasing, as at least half , or decreasing, as at most three.

An absolute quantier Q is represented by a function µ Q from an integer range to [0, 1] whereas a relative quantier is a mapping µ Q from [0, 1] to [0, 1]. In both cases, the value µ Q (j) is dened as the truth value of the statement Q X are A when exactly j elements from X fully satisfy A (whereas it is assumed that A is fully unsatised for the other elements).

According to [Yager, 1988], fuzzy quantiers can be increasing (proportional) which means that if the criteria are all entirely satised, then the statement Q X are A is entirely true, and if the criteria are all entirely unsatised, then the statement Q X are A is entirely false. Moreover, the transition between those two extremes is continuous and monotonous.

Therefore, when Q is increasing (e.g., most, at least a half ), function µ Q is increasing.

Similarly, decreasing quantiers (e.g., at most two, at most a half ) are dened by decreasing functions.

The characteristics of monotonous fuzzy quantiers are given in Table 4.1.

Increasing quantier

Decreasing quantier Calculating the truth degree of the statement Q X are A raises the problem of determining the cardinality of the set of elements from X which satisfy A. If A is a Boolean predicate, this cardinality is a precise integer (k), and then, the truth value of Q X are A is µ Q (k). If A is a fuzzy predicate, this cardinality cannot be established precisely and then, computing the quantication corresponds to establishing the value of function µ Q for an imprecise argument.

µ Q (0) = 0 µ Q (0) = 1 ∃k such that µ Q (k) = 1 ∃k such that µ Q (k) = 0 ∀a, b, if a > b then µ Q (a) ≥ µ Q (b) ∀a, b, if a > b then µ Q (a) ≤ µ Q (b)
Fuzzy quantied queries have been thoroughly studied in a relational database context, see e.g. [START_REF] Kacprzyk | FQUERY III +:a "human-consistent" database querying system based on fuzzy logic with linguistic quantiers[END_REF], Bosc et al., 1995] where they serve to express conditions about data values. The authors distinguished between two types of uses of fuzzy quantiers:

• horizontal quantication (the quantier is used as a connective for combining atomic conditions in a where clause; this use was originally suggested in [START_REF] Kacprzyk | FQUERY III +:a "human-consistent" database querying system based on fuzzy logic with linguistic quantiers[END_REF]);

• vertical quantication (the quantier appears in a having clause in order to express a condition on the cardinality of a fuzzy subset of a group, as in nd the departments where most of the employees are well-paid ). This is the type of use we make in our approach.

Interpretation of Fuzzy Quantied Statements

We now present dierent proposals from the literature for interpreting quantied statements of the type Q B X are A (which generalizes the case Q X are A by considering that the set to which the quantier applies is itself fuzzy) where X is a (crisp) referential and A and B are fuzzy predicates. 4. 1.2.1 Zadeh's interpretation Let X be the usual (crisp) set {x 1 , x 2 , . . ., x n } and n the cardinality of X. Zadeh [Zadeh, 1983] denes the cardinality of the set of elements of X which satisfy A, denoted by Σcount(A), as:

Σcount(A) = n i=1 µ A (x i ) (4.1)
The truth degree of the statement Q X are A is then given by

µ(Q X are A) =        µ Q (Σcount(A)) (absolute), µ Q Σcount(A) n (relative) (4.2)
One may notice, however, that a large number of elements with a small degree µ A (x) has a same eect as a small number of elements with a high degree µ A (x), due to the denition of Σcount.

Example 46 Let us consider the following sets:

X 1 = {0.9/x 1 , 0.9/x 2 , 0.9/x 3 , 0.8/x 4 , 0.8/x 5 , 0.7/x 6 , 0.6/x 7 }, X 2 = {1/x 1 , 1/x 2 , 0.3/x 3 , 0.2/x 4 , 0.1/x 5 , 0/x 6 , 0/x 7 }, X 3 = {1/x 1 , 1/x 2 , 1/x 3 , 1/x 4 , 1/x 5 , 0.8/x 6 , 0.3/x 7 }.

and the quantier at least ve represented in Figure 4. As for quantied statements of the form Q B X are A (with Q relative), their interpretation is as follows:

µ(Q B X are A) = µ Q Σcount(A ∩ B) Σcount(B) = µ Q x∈X (µ A (x), µ B (x)) x∈X µ B (x) (4.3)
where denotes a triangular norm (for instance the minimum).

Example 47 Let us evaluate the quantied statement Q B X are

A where B={0.6/x 1 , 0.3/x 2 , 1/x 3 , 0.1/x 5 }, A={0.8/x 1 , 0.4/x 2 , 0.9/x 3 , 1/x 4 , 1/x 5 } and Q(x) = x 2 . Then, µ(Q B X are A) = µ Q ( 0.6+0.3+0.9+0+0.1 0.6+0.3+1+0+0.1 ) = µ Q ( 1.9 2 ) = µ Q (0.95) = 0.90.

Yager's Competitive Type Aggregation

The interpretation by decomposition described in [Yager, 1984] was originally limited to increasing quantiers.

It was later generalized to all kinds of fuzzy quantiers in [Bosc et al., 1995], but hereafter, we consider the basic case where Q is increasing.

The proposition Q X are A is true if an ordinary subset C of X satises the conditions c 1 and c 2 given hereafter:

c 1 : there are Q elements in C, c 2 : each element x of C satises A.
The truth value of the proposition: Q X are A is then dened as:

µ(Q X are A) = sup C ⊆ X min(µ c 1 (C), µ c 2 (C)) (4.4) with µ c 1 (C) =        µ Q (|C|) if Q is absolute, µ Q |C| n if Q is relative (4.5)
and .6) It has been shown in [Yager, 1984] that:

µ c 2 (C) = inf x ∈ C µ A (x). ( 4
µ(Q X are A) = sup 1 ≤ i ≤ n min(µ Q (i), µ A (x i )). (4.7)
where the elements of X are ordered in such a way that µ A (x 1 ) ≥ . . . ≥ µ A (x n ). Formula (4.7) corresponds to a Sugeno integral [Sugeno, 1974].

For quantied statements of the form QBX are A, the principle is similar. The statement is true if there exists a crisp subset C of X that satises the conditions c 1 and c 2 hereafter:

c 1 : Q B X are in C, c 2 : each element x of C satises the implication (x is B) ⇒ (x is A).
The truth value of the proposition: Q B X are A is then dened as:

µ(Q B X are A) = sup C ⊆ X min(µ c 1 (C), µ c 2 (C)) (4.8) with µ c 1 (C) =            µ Q x∈C µ B (x) if Q is absolute, µ Q   x∈C µ B (x) x∈X µ B (x)   if Q is relative (4.9) and µ c 2 (C) = inf x ∈ C µ B (x) → µ A (x) (4.10)
where → is a fuzzy implication (see e.g. [START_REF] Fodor | Fuzzy-set theoretic operators and quantiers[END_REF]).

Notice that µ(Q B X are A) is undened when ∀x ∈ X, µ B (x) = 0 since this would result in a division by zero in Formula 4.9.

Interpretation based on the OWA operator

In [Yager, 1988], Yager considers the case of an increasing monotonous quantier and proposes an ordered weighted averaging operator (OWA) to evaluate quantications of the type Q X are A. It is shown in [Bosc et al., 1995] i) how it can be extended in order to evaluate decreasing quantications and ii) that this interpretation boils down to using a Choquet fuzzy integral.

The OWA operator is dened in [Yager, 1988] as:

OWA(x 1 , . . . , x n ; w 1 , . . . , w n ) = n i=1 w i × x k i (4.11)
where x k i is the i th largest value among the x k 's and n i=1 w i = 1.

Let n be the crisp cardinality of X. The truth value of the statement Q X are A is computed by an OWA of the n values µ A (x i ). The weights w i involved in the calculation of the OWA are given by

w i =        µ Q (i) -µ Q (i -1) if Q is absolute, µ Q i n -µ Q i -1 n if Q is relative. (4.12)
The aggregated value which is calculated is:

OWA(µ A (x 1 ), µ A (x 2 ), . . . , µ A (x n ); w 1 , . . . , w n ) = n i=1 w i × c i (4.13)
where c i is the i th largest value among the µ A (x k )'s.

Example 48 Let us consider the sets X 1 , X 2 , and X 3 , and the quantier at least ve from Example 46. We have:

w 1 = 0, w 2 = 0, w 3 = 1/3, w 4 = 1/3, w 5 = 1/3, w 6 = 0, w 7 = 0.
We evaluate the statement at least ve elements of X 1 are A and we get the degree 0.83 (= 0.9 × 1/3 + 0.8 × 1/3 + 0.8 × 1/3). The same way, we get the degrees 0.2 for X 2 and 1 for X 3 .

This interpretation corresponds to using a Choquet integral [Choquet, 1954], see also [START_REF] Murofushi | [END_REF]Sugeno, 1989, Grabisch et al., 1992].

As for statements of the form Q B X are A, Yager suggests to compute the truth degree of statements of the form Q B X are A by an OWA aggregation of the implication values

µ B (x) → KD µ A (x)
where → KD denotes Kleene-Dienes implication (a

→ KD b = max(1 -a, b)). Let X = {x 1 , . . . , x n } be such that µ B (x 1 ) ≤ µ B (x 2 ) ≤ . . . ≤ µ B (x n ) and n i=1 µ B (x i ) = d.
The weights of the OWA operator are dened by: The implication values are denoted by c i and ordered decreasingly:

w i = µ Q (S i ) -µ Q (S i-1 ),
c 1 ≥ c 2 ≥ . . . ≥ c n .
Finally: We rst order the elements of X such that µ B (x k 1 ) ≤ ... ≤ µ B (x kn ), e 1 = 0, e 2 = 0.1, e 3 = 0.3, e 4 = 0.6, e 5 = 1 and d = 2. Thus, we get S 1 = 0, S 2 = 0.05, S 3 = 0.2, S 4 = 0.5, S 5 = 1.

µ(Q B X are A) = n i=1 w i × c i .
µ Q (S 1 ) = 0, µ Q (S 2 ) = 0.025, µ Q (S 3 ) = 0.04, µ Q (S 4 ) = 0.25, µ Q (S 5 ) = 1.
Therefore, the weights of the OWA operator are:

w 1 = µ Q (S 1 ) -µ Q (S 0 ) = 0, w 2 = µ Q (S 2 ) -µ Q (S 1 ) = 0.025, w 3 = µ Q (S 3 ) -µ Q (S 2 ) = 0.04 -0.0025 = 0.0375, w 4 = µ Q (S 4 ) -µ Q (S 3 ) = 0.25 -0.04 = 0.21, w 5 = µ Q (S 5 ) -µ Q (S 4 ) = 1 -0.25 = 0.75.
For each x i we calculate the implication value c i = max((1 -µ B (x i )), µ A (x i )) and these values are ordered decreasingly such that c 1 ≥ . . . ≥ c n .

c 1 = max(0.4, 0.8) = 0.8, c 2 = max(0.7, 0.4) = 0.7, c 3 = max(0, 0.9) = 0.9, c 4 = max(1, 1) = 1, c 5 = max(0.9, 1) = 1.

We reorder the implication values and we get c 1 = 1(c 4 ), c 2 = 1(c 5 ), c 3 = 0.9(c 3 ), c 4 = 0.8(c 1 ), c 5 = 0.7(c 2 ).

Finally, the satisfaction degree using the OWA aggregation is: µ = (1) * 0 + 0.0025 * (1) + (0.375) * 0.9 + 0.21 * (0.8) + 0.75 * (0.7) = 0.73.

FURQL with Fuzzy Quantied Statements

In this section, we rst present some recent proposals from the literature for incorporating quantied statements into SPARQL queries, and then, we propose to integrate fuzzy quantied statements in the FURQL language.

Related Work: Quantied Statements in SPARQL

In an RDF database context, quantied statements have only recently attracted the attention of database community. In [START_REF] Bry | SPARQLog: SPARQL with rules and quantication[END_REF], Bry et al. propose an extension of SPARQL (called SPARQLog) with rst-order logic (FO) rules and existential and universal quantication over node variables. This query language makes it possible to express statements such as: for each lecture there is a course that practices this lecture and is attended by all students attending the lecture . This statement can be expressed in SPARQLog as follows:

all ?lec ex ?crs all ?stu construct { ?crs uni:practices ?lec . ?stu uni:attends ?crs . } where { ?lec rdf:type uni:lecture . ?stu uni:attends ?lec . }

More recently, in [START_REF] Fan | Adding counting quantiers to graph patterns[END_REF], Fan et al. introduced quantied graph patterns, an extension of the classical SPARQL graph patterns using simple counting quantiers on edges.

Quantied graph patterns make it possible to express numeric and ratio aggregates, and negation besides existential and universal quantication. The authors also showed that quantied matching in the absence of negation does not signicantly increase the cost of query processing.

However, to the best of our knowledge, there does not exist any work in the literature that deals with fuzzy quantied statements in the SPARQL query language, which is the main goal of the present chapter.

Fuzzy Quantied Statements in FURQL

In this subsection, we show how fuzzy quantied statements may be expressed in FURQL queries. We rst propose a syntactic format for these queries, and then we show how they can be evaluated in an ecient way.

Syntax of a Fuzzy Quantied Query in FURQL

In the following, we consider fuzzy quantied statements of the type Q B X are A over fuzzy RDF graph databases, where the quantier Q is represented by a fuzzy set and denotes either a relative quantier (e.g., most ) or an absolute one (e.g., at least three ), B is the fuzzy condition to be connected to a node x, X is the set of nodes in the RDF graph, and A denotes a (possibly compound) fuzzy condition.

Example 50 [Fuzzy quantied statement] An example of a fuzzy quantied statements of the type Q B X are A is: most of the recent albums are highly rated.

In this example, Q corresponds to the relative quantier most, B is the fuzzy condition to be recent, X corresponds to the set of albums present in the RDF graph, and A corresponds to the fuzzy conditions to be highly rated. Since the FURQL query language supports the expression of fuzzy preferences involving fuzzy structural properties (like for example, the distance and strength between two nodes over fuzzy graphs), fuzzy quantied structural queries can be expressed in the FURQL language and an example of such query is given hereafter.

Example 52 [Fuzzy Quantied Structural Query in FURQL] We now consider a slightly more complex version of the above example by adding a fuzzy structural condition on the strength of the authors' recommendation: retrieve every artist (?art1) such that most of the recent albums (?alb) that he/she strongly recommends are highly rated and have been created by a young friend (?art2) of his/hers. The syntactic form of this query, denoted by R mostAlbums_ST , is given in Listing 4.3.

1 defineqrelativeasc most as (0.3,0.8) defineasc recent as (2010,2015) 2 defineasc high as (2,5) The interpretation of a fuzzy quantied statement in a FURQL query can be based on one of the formulas (4.3), ( 4.8), or (4.17). Its evaluation involves three stages :

1. the compiling of the fuzzy quantied query R into a crisp query denoted by R atBoolean , 2. the interpretation of the crisp SPARQL query R atBoolean , 3. the calculation of the result of R (which is a fuzzy set) based on the result of R atBoolean .

Compiling

The compiling stage translates the fuzzy quantied query R into a crisp query denoted by R atBoolean . This compilation involves two translation steps.

First, R is transcripted into an intermediate query R at that allows to interpret the fuzzy quantied statement embedded in R. The query R f lat , whose general form 1 is given in List- ing 4.4, is obtained by removing the group by and having clauses from the initial query and adding the optional clause for the A part. This query aims to retrieve the elements of the B part of the initial query, matching the variables ?res and ?x, and possibly the elements of the A part of the initial query, matching the variable ?x, for which we will then need to calculate the nal satisfaction degree.

select ?res ?X IB IA where { B(?res,?X) optional { A(?X) } } Listing 4.4: Derived query R at of R mostAlbums

For each pair (?res, ?x), we retrieve all the information needed for the calculation of µ B and µ A , i.e., the combination of fuzzy degrees associated with relationships and node attribute values involved in B(?res,?x) and in A(?X), respectively denoted by I B and I A . Listing 4.5 of Example 53 below presents the derived query associated with the query R mostAlbums .

The evaluation of R at is based on the derivation principle introduced by [START_REF] Pivert | Fuzzy Preference Queries to Relational Databases[END_REF] in the context of relational databases: R f lat is in fact derived into another query denoted by R atBoolean . The derivation translates the fuzzy query into a crisp one by transforming its fuzzy conditions into Boolean ones that select the support of the fuzzy statements. For instance, following this principle, the fuzzy condition ?year IS recent dened as defineasc recent as (2013,2016) becomes the crisp condition ?year > 2013 in order to remove the answers that necessary do not belong to the support of the answer. In the general case of a membership function having a trapezoidal form dened by a quadruple (a, b, c, d), the derivation introduces two crisp conditions ( ?var > a and ?var < d). Listing 4.6 of Example 53 below is an illustration of the derivation of the query R f lat .

Crisp interpretation

The previous compiling stage translates the fuzzy quantied query R embedding A fuzzy quantied statement and fuzzy conditions into a crisp query R atBoolean , whose interpretation is the classical Boolean one.

For the sake of simplicity, we consider in the following that the result of R at , denoted by r at , is made of the quadruples (?res i , ?x i , µ Bi , µ Ai ) matching the query.

Final result calculation

The last stage of the evaluation calculates the satisfaction degrees µ B and µ A according to I B and I A . If the optional part does not match a given answer, then µ A = 0. The answers of the initial fuzzy quantied query R (involving the fuzzy quantier Q) are answers of the query R at derived from R, and the nal satisfaction degree associated with each element e can be calculated according to the three dierent interpretations mentioned earlier in Subsection 4. 1.2. Hereafter, we illustrate this using [Zadeh, 1983] and [Yager, 1988]'s approaches (which are the most commonly used for interpreting fuzzy quantied statements ).

• Following Zadeh's Sigma-count-based approach (cf. Subsection 4. 1.2.1) we have:

µ(e) = µ Q {(?res i ,?x i ,µ Bi ,µ Ai )∈ R at |?res i =e} min(µ Ai , µ Bi ) {(?res i ,?x i ,µ Bi ,µ Ai )∈ R at |res i =e} µ Bi (4.18)
In the case of a fuzzy absolute quantied query, the nal satisfaction degree associated with each element e is simply Example 53 [Evaluation of a Fuzzy Quantied Query] Let us consider the fuzzy quantied query R mostAlbums of Listing 4.2. We evaluate this query according to the fuzzy RDF data graph G MB of Figure 4. 5. In order to interpret R mostAlbums , we rst derive the following query R at from R mostAlbums , that retrieves the artists (?art1) who recommended at least one recent album (corresponds to B(?art1,?alb) in lines 2 and 3), possibly (optional) highly rated and created by a young friend (corresponds to A(?alb) in lines 5 to 7). where µ p denotes the membership degree of the predicate p and ζ(t) denotes the membership value associated with the triple t (cf., Denition 4 on page 62).

µ(e) = µ Q   {(?res i ,?x i ,µ Bi ,µ Ai )∈ R at |?res i =e} µ Ai   .
For the sake of readability, the query of Listing 4.6 is a simplied version of the real derived query (cf. Listing A.1 in Appendix A).

According to the fuzzy RDF data graph G MB of Figure 4.5, R at concerns three artists {JustinT, Shakira, Beyonce}. EnriqueI, Drake, Mariah and Rihanna do not belong to the result set of R at because EnriqueI, Drake and Mariah have not recommended any album made by any of their friends and Rihanna did not recommend any somewhat recent album.

Then, the set of answers of the query R f lat , denoted by R f lat , is as follows:

R f lat = { (?art1→ JustinT, ?alb→ One dance, µ B → 0.4, µ A → 0.3), (?art1→ JustinT, ?alb → Home, µ B → 0.1, µ A → 0.6), (?art1→ Shakira, ?alb → Euphoria, µ B → 0.1 , µ A → 0.07), (?art1→ Shakira, ?alb → Butterfly, µ B → 0.2, µ A → 0), (?art1→ Shakira, ?alb → Justified, µ B → 0.3, µ A → 0.4), (?art1→ Beyonce, ?alb → Home, µ B → 0.4, µ A → 0.3)}.

Finally, assuming for the sake of simplicity that µ most (x) = x, the nal result of the query R mostAlbums evaluated on G MB using Formula 4.18 is: R mostAlbums = { ({?art1 → JustinT }, 0.80), ({?art1 → Beyonce }, 0.75), ({?art1 → Shakira }, 0.62)}.

• Using Yager's OWA-based approach, for each element e returned by R at we calculate

µ(e) = {(?res i ,?x i ,µ Bi ,µ Ai )∈ R at |?res i =e} w i × c i . (4.19) Let us consider condition B = {µ B 1 /x 1 , ..., µ Bn /x n } such that µ B 1 ≤ ... ≤ µ Bn , condition A = {µ A 1 /x 1 , ..., µ An /x n } and d = n i=1 µ B i .
The weights of the OWA operator are dened by

w i = µ Q (S x i ) -µ Q (S x i-1 ) with S x i = i j=1 µ B j d
The implication values are denoted by c x i = max(1 -µ B i , µ A i ) and ordered decreasingly such that c 1 ≥ . Then, with µ most (x) = x, we get µ Q (S Euphoria ) = 0.17, µ Q (S Buttery ) = 0.5 and µ Q (S Justied ) = 1.

Therefore, the weights of the OWA operator are:

W 1 = µ Q (S Euphoria ) -µ Q (S 0 ) = 0.17, W 2 = µ Q (S Buttery ) -µ Q (S Euphoria ) = 0.
33, and

W 3 = µ Q (S Justied ) -µ Q (S Buttery ) = 0.5.
The implication values are:

c Euphoria = max(1 -0.1, 0.07) = 0.9, c Buttery = max(1 -0.2, 0) = 0.8, and c Justied = max(1 -0.3, 0.36) = 0.7.

Thus, c 1 = 0.9, c 2 = 0.8 and c 3 = 0.7. Finally, we get:

µ(Shakira) = 0.17 × 0.9 + 0.33 × 0.8 + 0.5 × 0.7 = 0.15 + 0.26 + 0.35 = 0.77.

Finally, assuming for the sake of simplicity that µ most (x) = x, the nal result of the query R mostAlbums evaluated on G MB using Formula 4.19 is:

R mostAlbums = { ({?art1 → Shakira }, 0.77), ({?art1 → JustinT }, 0.66), ({?art1 → Beyonce }, 0.6) }.

Conclusion

In this chapter, we have investigated the issue of integrating fuzzy quantied structural queries of the type Q B X are A into the FURQL query language (a fuzzy extension of the SPARQL that we proposed in Chapter 3) aimed to query fuzzy RDF databases. We have dened the syntax and semantics of an extension of FURQL, that makes it possible to deal with such queries. A query processing strategy based on the derivation of nonquantied fuzzy queries has also been proposed using dierent interpretations from the literature previously discussed in Section 4. 1. The following chapter discusses implementation issues and presents some experiments.

Introduction

Chapters3and4cont ain the main contributions of the thesis which consist of the definition of the FURQL query language, which is a fuzzy extension of SPARQL with fuzzy preferences (including fuzzy quantied statements ) addressed to fuzzy RDF databases as well as crisp ones.

In the present chapter, in Section 5.1, we describe a prototype implementation of FURQL built on top of a classical SPARQL engine and, then in Section 5.2, we present a performance evaluation of the prototype system using dierent sizes of fuzzy RDF databases. The main objective behind these experiments is to show that the extra cost due to the introduction of fuzziness remains limited/acceptable.

rdf:subject, rdf:predicate, rdf:object and uri:degree that model respectively the type, the subject, the predicate, the object and the degree of the new statement. In order to create a fuzzy RDF database, we start from a nonfuzzy RDF subgraph database for which every relationship between nodes is Boolean and then, we make it fuzzy by adding satisfaction degrees denoting the intensity of some relationships using the reication mechanism (as illustrated in Example 55).

Shakira MariahC friend

Blank node

Evaluation of FURQL Queries

Concerning the evaluation of FURQL queries, two architectures may be thought of:

• A rst solution consists in implementing a specic query evaluation engine inside the data management system. Figure 5.2 is an illustration of this architecture. The advantage of this solution is that optimization techniques implemented directly in the query engine should make the system very ecient for query processing. An important downside is that the implementation eort is substantial, but the strongest objection for this solution is that the evaluation of a FURQL query in a distributed architecture would imply having available a FURQL query evaluator at each SPARQL endpoint, which is not realistic at the time being.

• An alternative more realistic architecture consists in adding a software add-on layer over a standard and possibly distant classical SPARQL engine (endpoint) which is the evaluation strategy that we adopted for processing FURQL queries. This software, called SURF 1 (Sparql with fUzzy quantieRs for rdF data), is imple- mented within the Jena Semantic Web Java Framework 2 for creating and manipulating 1. In a pre-processing step, the Query compiler module, produces the query-dependent functions that allow to compute the satisfaction degrees for each returned answer, a (crisp) SPARQL query which is then sent to the SPARQL query engine for retrieving the information needed to calculate the satisfaction degrees.

The compilation uses the derivation principle introduced in [START_REF] Bosc | SQLf query functionality on top of a regular relational database management system[END_REF] in a relational database context that consists in translating a fuzzy query into a Boolean one. 2. In a post-processing step, the Score calculator module calculates the satisfaction degree for each returned answer, ranks the answers, and qualitatively lters them if an α-cut has been specied in the initial fuzzy query. SURF makes it possible to query FURQL queries (including quantied ones) as well as regular SPARQL queries. The dierent evaluation scenarios are presented hereafter. 1. For a FURQL query (that does not involve any quantied statement), the principle is simple, we rst evaluate the corresponding (crisp) SPARQL query returned by the Query compiler module (obtained using the derivation rules). For each tuple x from the result of the crisp SPARQL query, we calculate its satisfaction degree using the Score calculator module. Finally, a set of answers ranked in decreasing order of their satisfaction degree is returned. At the current time, Zadeh's approach [Zadeh, 1983] and Yager's OWA-based approach [Yager, 1988] have been implemented, and the choice of the interpretation to be used is made through the conguration tool of the system. Finally, we get a set of answers ranked in decreasing order of their satisfaction degree. The SURF GUI was created using Vaadin 3 , a web framework for Java under NetBeans IDE 8.2. It is mainly composed of two frames:

• an input text area for entering and running a FURQL query, and

• a table for visualizing the results of a query.

Example 56 Figure 5.4 presents a screenshot of the SURF GUI, which contains the nal result of the evaluation of a FURQL query.

Experimentations

In order to demonstrate the performances of our approach in the case of fuzzy graph pattern queries, we ran two experiments in order to calculate the execution time of each step of the evaluation for FURQL queries with and without quantied statements and then to assess the cost of adding fuzzy preferences for each type of queries.

In the following, we rst present the setup we used for the evaluation and then, we describe in detail each experiment.

Experimental Setup

All of the experiments were carried out on a personal computer running Windows 7 (64 bits) with 8GB of RAM.

For these experiments, we used four dierent sizes of fuzzy RDF datasets containing crisp and fuzzy triples, as described in Table 5. 1. Our In the following, we rst present experiments on nonquantied FURQL queries (Section 5.2.2) and then on quantied ones (Section 5.2.3).

Experiments for nonquantied FURQL Queries

For this experiment, we considered dierent kinds of nonquantied FURQL queries (summarized in Table 5.2), based on the typology presented in [START_REF] Umbrich | Link traversal querying for a diverse web of data[END_REF]. Three types have been used. For each kind of queries, we consider two fuzzy subtypes: 1) a subtype for which a condition concerns a value, and 2) a subtype for which a condition concerns the intensity of the relationships. Such subtype is called Structural in the following.

• Edge queries: that consist in retrieving an entity e by means of a pattern where e may appear either i) in the subject (denoted by edge-s ), ii) in the object (denoted by edge-o), or iii) both (denoted by edge-so). We consider in the following four edge queries of the form edge-so given in Figure 5. 5.

Query Q 1.2 is a fuzzy edge query containing a fuzzy condition that aims to nd the recent albums recommended by an artist; Its corresponding crisp query, denoted by

Q 1.1 , Q 1.3 Q 1.2 Q 1.4
Star query

Q 2.1 , Q 2.3 Q 2.2 Q 2.4
Simple path query

Q 3.1 , Q 3.3 Q 3.2 Q 4.4
(resp., Figure 5.8.(b)) presents the execution time in milliseconds of the processing of the edge queries (resp., star queries) from Table 5.2. Figure 5.8.(c) presents the execution time in milliseconds of the processing of the path queries from Table 5.2.

The execution time is the elapsed time between submitting the query to the system and obtaining the query answers, it is measured in milliseconds using the system command time.

A rst (and predictable) observation is that, for each crisp and fuzzy query presented in Table 5.2, the processing time of the overall process is proportional to the size of the dataset, the number of the results and the complexity of the query.

It is straightforward to see that for all the crisp queries the query compiler and the score calculator modules do not play any role in the processing of the queries. Thus, the corresponding execution times in Figure 5.8 are equal to 0. In the case of fuzzy queries, these modules, which are directly related to the introduction of exibility into the query language, are strongly dominated in time by the crisp SPARQL evaluator (which includes the time for executing the query and getting the result set). As we can see in Figure 5.8, the time of the evaluation of the initial query by the SPARQL evaluator engine represents at least 89% of the overall process.

Moreover, the FURQL compiling module takes so little time compared to the other two steps that it cannot even be seen in Figure 5.8. This time remains almost constant, and is then independent on the size of the dataset. As to the score calculation module, the time used for calculating the nal satisfaction degrees is slightly higher than the last step and is dependent on the size of the result set and the nature of the query.

Comparing the pairwise queries (Q i.1 with Q i.2 and Q i.3 with Q i.4 ), we see that the processing time of the fuzzy query is slightly higher than that of its crisp version. The increase is 10% on average.

Finally, the results obtained tend to show that introducing fuzziness into a SPARQL query entails a rather small increase of the overall processing time. According to our experimentations, it represents around 11% of the overall time needed for evaluating a FURQL query in the worst case. Q4 crisp complex complex crisp between two or four triple patterns. Each Q crisp contains three crisp conditions. These queries are detailed in Appendix A.

In order to evaluate these queries, we used Yager's OWA-based interpretation. The results, depicted in Figure 6.8, present the execution time in milliseconds of the processing of the fuzzy quantied queries involving crisp conditions from Table 5.3 over the RDF datasets from Table 5.1 on page 103.

Fuzzy quantied query involving fuzzy conditions

We processed again four fuzzy quantied queries with fuzzy conditions (of the type Q B X are A) by changing each time the nature of the patterns corresponding to conditions B and A from simple to complex ones. Table 5.4 presents these queries.

A complex pattern diers from a simple one by the number and the nature (including structural properties) of its statements. During these experiments, a complex pattern is composed of nine triple patterns at most, while a simple pattern contains between two and four triple patterns. For each complex pattern a fuzzy structural property (e.g., involving the notions of strength or distance) is involved. Each Q fuzzy contains three fuzzy conditions.

These queries are detailed in Appendix A. The results of these experiments, using Yager's OWA-based interpretation, are depicted in Figure 5.10 that presents the execution time in milliseconds of the processing of the fuzzy quantied queries from Table 5.4 over the RDF datasets from Table 5.1 on page 103.

Results interpretation

A rst and obvious observation from Figure 5.9 and Figure 5.10 is that, for all the fuzzy quantied queries, the processing time taken by the overall process is proportional to the size of the dataset and the complexity of the pattern in the query.

One can see that, the processing time taken by the compiling and the score calculation module, which are directly related to the introduction of exibility into the query language, are very strongly dominated by the time taken by the SPARQL evaluator (which includes the time for executing the query and getting the result set). As it is shown in Figure 5.9 and Figure 5.10, the time of the evaluation of the initial query by the SPARQL evaluator engine represents 99% on average of the overall process.

Indeed, the FURQL compiling step takes so little time compared to the score calculation and the SPARQL evaluator modules that it cannot even be seen in Figure 5.9 and Figure 5.10. This time remains almost constant, and is independent on the size of the dataset while slightly increasing in the presence of complex patterns or fuzzy conditions.

Moreover, the time needed for calculating the nal satisfaction degree in the score calculator module is relatively dependent on the size of the result set and the nature of the patterns.

Again, these experimental results, even though preliminary, appear promising. They tend to show that introducing fuzzy quantied statements into a SPARQL query does not come with a high price (i.e., entails a very small increase of the overall processing time).

Finally, this conclusion can be extended to the case of Zadeh's interpretation [Zadeh, 1983],

inasmuch as it is even more straightforward, in terms of computation, than Yager's OWAbased approach [Yager, 1988]. Thus, the processing time of the score calculating step can only be smaller than in the case of Yager's OWA-based interpretation.

Conclusion

In this chapter, in Section 5.1, we discussed implementation issues related to the FURQL language and we presented an architecture which consists of a software add-on layer (called SURF) over the classical SPARQL engine. Then, in Section 5.2, we performed two set of experiments over dierent sizes of datasets in order to study the performances of our proposed approach. The rst experiments aimed to measure the additional cost induced by the introduction of fuzziness into SPARQL, and the results obtained show the eciency of our proposal. The second experiments, which concerned fuzzy quantied queries, show that the extra cost induced by the fuzzy quantied nature of the queries remains very limited, even in the case of rather complex fuzzy quantied queries.

The results of the experiments performed in this chapter are summarized in Table 5. 5.

Each cell of the table contains three values corresponding to the percentage of time devoted to the compilation, the crisp evaluation and the score calculation stages respectively. They

show that in both experiments the compilation and the score calculation stages are strongly dominated by the crisp SPARQL evaluation. The latter represents at least 95% of the overall process. Thus, these results conrm the hypothesis that the extra cost due to the introduction of fuzziness remains limited/acceptable.

Finally, these experiments are preliminary and more work is required to further assess FURQL by using dierent variety of queries (e.g., complex path queries of undetermined length) and considering large databases.

Introduction

Int he previous chapters, we addressed mainly the issue of dening an ecient approach for exible querying in a particular type of graph databases, namely RDF databases. This approach makes it possible to express fuzzy nonquantied and quantied queries into an extension of the SPARQL language.

In the present chapter, we place ourselves in a more general framework: graph database [START_REF] Angles | Survey of graph database models[END_REF]]. An ecient approach for exible querying of fuzzy 6.1. Background Notions graph databases has been proposed in [START_REF] Pivert | On a fuzzy algebra for querying graph databases[END_REF]. This approach makes it possible to express only fuzzy nonquantied conditions. However, fuzzy quantied queries have a high potential in this setting since they can exploit the structure of the graph, beside the attribute values attached to the nodes or edges. So far, only one approach from the literature, described in [START_REF] Castelltort | Fuzzy queries over NoSQL graph databases: Perspectives for extending the Cypher language[END_REF], considered fuzzy quantied queries to graph databases but only in a rather limited way.

This chapter is based on our work reported in [Pivert et al., 2016e], in which we showed how it is possible to integrate fuzzy quantied queries in a framework named FUDGE that was previously dened in [Pivert et al., 2014a]. FUDGE is a fuzzy extension of Cypher [START_REF] Cypher | Cypher[END_REF] which is a declarative language for querying (crisp) graph databases.

This work is mostly related to the work presented in Chapter 4 in which we deal with the same type of fuzzy quantied structural query but in a more specic type of graph databases, called RDF database.

The remainder of this chapter is organized as follows. Section 6.1 presents the dierent elements that constitute the context of the work. Section 6.2 discusses related work. In Section 6.3, we propose a syntactic format for expressing fuzzy quantied queries in the FUDGE language, and we describe its interpretation. Section 6.4 deals with query processing and discusses implementation issues. In Section 6.5, some experimental results showing the feasibility of the approach are presented.

Background Notions

In this section, we recall important notions about graph databases, fuzzy graph theory, fuzzy graph databases, and the query language FUDGE. 6.1.1 Graph Databases In the last few years, graph databases has attracted a lot of attention for their ability to handle complex data in many application domains, e.g., social networks, cartographic databases, bibliographic databases, etc [Angles andGutierrez, 2008, Angles, 2012]. They aim to eciently manage networks of entities where each node is described by a set of characteristics (for instance a set of attributes), and each edge represents a link between entities.

A graph database management system enables managing data for which the data structure of the schema is modeled as a graph and data is handled through graph-oriented operations and type constructors [START_REF] Angles | Survey of graph database models[END_REF] [START_REF] Angles | Survey of graph database models[END_REF] for an overview), including the attributed graph (aka., property graph) aimed to model a network of entities with embedded data. In this model, nodes and edges can be described by data in attributes (aka., properties).

Example 57 Figure 6.1 is an example of an attributed graph, inspired from DBLP 1 with crisp edges.

Nodes are assumed to be typed. If n is a node of V , then T ype(n) denotes its type. In Figure 6.1, the nodes IJIS16 and IJIS10 are of type journal, the nodes IJIS16-p, IJIS10-p and IJIS10-p1 are of type paper, and the nodes Maria, Claudio and Susan are of type author. For nodes of type journal, paper and author, a property, called name, contains the identier of the node. Information about the title and the pages may be attached to node of type paper and information about the volume and the date may be attached to node of type journal. In Figure 6.1, the value of the property name for a node appears inside the node.

Such a model may be extended into the notion of a fuzzy graph database where a degree may be attached to edges in order to express the intensity of any kind of gradual relationship (e.g., likes, is friends with, is about). In the following section, we introduce the notion of fuzzy graphs.

Fuzzy Graphs

A graph G is a pair (V, R), where V is a set and R is a relation on V . The elements of V (resp. R) correspond to the vertices (resp. edges) of the graph. Similarly, any fuzzy relation ρ on 6.1. Background Notions a set V can be regarded as dening a weighted graph, or fuzzy graph, see [Rosenfeld, 1975], where the edge (x, y) ∈ V × V has weight or strength ρ(x, y) ∈ [0, 1]. Having no edge between x and y is equivalent to ρ(x, y) = 0.

A fuzzy data graph may contain both fuzzy edges and crisp edges as a fuzzy edge with a degree of 0 or 1 can be considered as crisp. Along the same line, a crisp data graph is simply a special case of fuzzy data graph (where ρ : V × V → {0, 1} is Boolean). We then only deal with fuzzy edges and data graphs in the following.

An important operation on fuzzy relations is composition. Assume ρ 1 and ρ 2 are two fuzzy relations on V . Thus, composition ρ = ρ 1 • ρ 2 is also a fuzzy relation on V s.t. ρ(x, z) = max y min(ρ 1 (x, y), ρ 2 (y, z)). The composition operation can be shown to be associative

: (ρ 1 • ρ 2 ) • ρ 3 = ρ 1 • (ρ 2 • ρ 3 ).
The associativity property allows us to use the notation ρ k = ρ • ρ • . . . • ρ for the composition of ρ with itself k -1 times. In addition, following [Yager, 2013], we dene ρ 0 to be s. t. ρ 0 (x, y) = 0, ∀(x, y).

Useful notions related to fuzzy graphs are those of strength and length of a path. These notions were previously used in Chapter 3 in the RDF context, Their denition, drawn from [Rosenfeld, 1975], is recalled hereafter. In other words, the strength of a path is dened to be the weight of the weakest edge of the path. Two nodes for which there exists a path p with ST (p) > 0 between them are called connected. We call p a cycle if n ≥ 2 and x 0 = x n . It is possible to show that ρ k (x, y) is the strength of the strongest path from x to y containing at most k links. Thus, the strength of the strongest path joining any two vertices x and y (using any number of links) may be denoted by ρ ∞ (x, y).

Strength of a

path. A path p in G is a sequence x 0 → x 1 → . . . → x n (n ≥ 0) such that ρ(x i-1 , x i ) > 0, 1 ≤ i ≤ n
Length and distance. The length of a path p = x 0 → x 1 → . . . → x n in the sense of ρ is dened as follows: Length(p).

Length(p) = n i=1 1 ρ(x i-1 , x i ) . ( 6
( .3) It is the length of the shortest path from x to y.

DB

subgraph where variables can occur. An answer maps the variables to elements of DB.

A fuzzy graph pattern expressed à la Cypher consists of a set of expressions (n1:Type1)-[exp]->(n2:Type2) or (n1:Type1)-[e:label]->(n2:Type2) where n1 and n2 are node variables, e is an edge variable, label is a label of E, exp is a fuzzy regular expression, and Type1 and Type2 are node types. Such an expression denotes a path satisfying a fuzzy regular expression exp (that is simple in the second form e) going from a node of type Type1 to a node of type Type2. All its arguments are optional, so the simplest form of an expression is ()-[]->() denoting a path made of two nodes connected by any edge.

Conditions on attributes are expressed on nodes and edges variables in a where clause.

Example 59 [Graph pattern] We denote by P the graph pattern: ing that its support is [A-a, B+b] and its core [A, B] , then the clause has the form define fterm as (A-a,A,B,B+b). If fterm is a decreasing function, then the clause has the form definedesc fterm as (δ,γ) meaning that the support of the term is [0, γ] and its core [0, δ] (there is the corresponding defineasc clause for increasing functions).

2.

A match clause, which has the form match pattern where conditions that expresses the fuzzy graph pattern.

Example 60 [FUDGE query] Listing 6.2 is an example of a FUDGE query. This pattern aims to retrieve the authors (au2) who have, among their close contributors (connected by a short path Length is short made of contributor edges), an author (au1) who published a paper (ar1) in IJWS12 and also published a paper (ar2) in a journal (j2) which has a high impact factor (i.value is high).

The fuzzy terms short and high are dened on line 1. Figure 6.4 is a graphical representation of this pattern where the dashed edge denotes a path and information in italics denotes a node type or an additional condition on node or edge attributes.

Related Work

In the last decades, fuzzy quantied queries have proved useful in a relational database context for expressing dierent types of imprecise information needs [Bosc et al., 1995]. Recently, in a graph database context, such statements started to attract increasing attention of many researchers [Yager, 2013, Castelltort and Laurent, 2014, Castelltort and Laurent, 2015] since they can exploit the structure of the graph, beside the attribute values attached to the nodes or edges.

In [Yager, 2013], R.R. Yager briey mentions the possibility of using fuzzy quantied queries in a social network database context, such as the question of whether most of the people residing in western countries have strong connections with each other and suggests

In [START_REF] Castelltort | Extracting fuzzy summaries from NoSQL graph databases[END_REF], the same authors propose an approach aimed to summarize a (crisp) graph database by means of fuzzy quantied statements of the form Q X are A, in the same spirit as what [START_REF] Rasmussen | Summary SQL -A fuzzy tool for data mining[END_REF]] did for relational databases. Again, they consider that the degree of truth of such a statement is obtained by a sigma-count (according to Zadeh's interpretation) and show how the corresponding queries can be expressed in Cypher. More precisely, given a graph database G and a summary S = a[r ]>b, Q, the authors consider two degrees of truth of S in G dened as follows:

truth 1 (S) = µ Q ( count(distinct S) count(distinct a) ) (6.4) truth 2 (S) = µ Q ( count(distinct S) count(distinct a[r ]>(?)) ) (6.5)
They illustrate these notions using a database representing students who rent or own a house or an apartment. The degree of truth (in the sense of the second formula above) of the summary S = student [rent ]>apartment, most meaning most of the students rent an apartment (as opposed to a house) is given by the membership degree to the fuzzy quantier most of the ratio: (number of times a relationship of type rents appears between a student and an apartment) over (number of relations of type rents starting from a student node). The corresponding Cypher query is: A limitation of this approach is that only the quantier is fuzzy (whereas in general, in a fuzzy quantied statement of the form Q B X are A, the predicates A and B may be fuzzy too).

The work the most related to that presented here is [START_REF] Pivert | Fuzzy quantied queries to fuzzy RDF databases[END_REF] described in Chapter 4, where we introduced the notion of fuzzy quantied statements in a (fuzzy) RDF database context. We showed how this statement could be expressed in the FURQL language (which is a exible extension of the SPARQL query language) that we previously proposed in [Pivert et al., 2016c].

Fuzzy Quantied Statements in FUDGE

In this section, we show how a specic type of fuzzy quantied statements may be expressed in the FUDGE query language. We rst propose a syntactic format for these queries, then we show how they can be eciently evaluated. 6.3.1 Syntax of a Fuzzy Quantied Query

In the following, we consider fuzzy quantied queries involving fuzzy predicates (beside the quantier) over fuzzy graph databases. The fuzzy quantied statements considered are of the same type as those used in Chapter 4 in the context of RDF databases. They are of the form Q B X are A, where the quantier Q is represented by a fuzzy set and denotes either an increasing/decreasing relative quantier (e.g., most ) or an increasing/decreasing absolute one (e.g., at least three ), where B is the fuzzy condition to be connected (according to a given pattern) to a node x, X is the set of nodes in the graph, and A is the fuzzy (possibly compound) condition.

An example of such a statement is: most of the recent papers of which x is a main author, have been published in a renowned database journal.

The general syntactic form of a fuzzy quantied query of the form Q B X are A in the FUDGE language is given in Listing 6. Example 61 [Fuzzy Quantied Query] The query, denoted by Q mostAuthors , that consists in retrieving every author (a) such that most of the recent papers (p) of which he/she is a main author, have been published in a renowned database journal (j) may be expressed in FUDGE as follows:

2. the interpretation of the crisp query Q derivedBoolean , 3. the calculation of the answers to Q based on the answers to Q derivedBoolean .

Compiling

The compiling stage translates the fuzzy quantied query Q into a crisp query denoted by Q derivedBoolean . This compilation involves two translation steps.

First, Q is transcripted into a derived query Q derived whose aim is to retrieve the elements necessary to the interpretation of the fuzzy quantied statement from Q. The query Q derived , whose general form 3 is given in Listing 6.5, makes it possible to get the elements of the B part of the initial query, matching the variables res and x, for which we will then need to calculate the nal satisfaction degree. It is obtained by removing the with and having clauses from the initial query, and adding the optional match clause before the fuzzy graph pattern in condition A. The processing of Q derived is based on the derivation principle introduced by [START_REF] Pivert | Fuzzy Preference Queries to Relational Databases[END_REF] in the context of relational databases: Q derived is in fact derived into another query denoted by Q derivedBoolean . The derivation step translates the fuzzy query into a crisp one by transforming its fuzzy conditions into Boolean ones that select the support of the fuzzy statements. For instance, following this principle, the fuzzy condition p.year IS recent (where recent is dened as defineasc recent as (2013,2016)) becomes the crisp condition p.year > 2013 in order to remove the answers that do not belong to the support of the answer. Listing 6.7 of Example 62 below is an illustration of the derivation of the query Q derived .

The derivation principle applied to the FUDGE language is detailed in [Pivert et al., 2015].

Crisp interpretation

The previous compiling stage translates the fuzzy quantied query Q embedding fuzzy quantiers and fuzzy conditions into a crisp query Q derivedBoolean , that can be processed by a classical graph DBMS (e.g., Neo4j).

For the sake of simplicity, we consider in the following that the result of Q derived , denoted by Q derived , is made of the quadruples (res i , x i , µ Bi , µ Ai ) matching the query.

Final result calculation

The last stage of the evaluation calculates the satisfaction degrees µ B and µ A according to I B and I A . If the optional part does not match a given answer, then µ A = 0. The answers of the initial fuzzy quantied query Q (involving the fuzzy quantier Q) are answers of the query Q derived derived from Q, and the nal satisfaction degree associated with each element e can be calculated according to the three dierent interpretations mentioned earlier in Section 4.1. Hereafter, we illustrate this using [Zadeh, 1983] and [Yager, 1988]'s approaches (which are the most commonly used when it comes to interpreting fuzzy quantied statements ). Following Zadeh's Sigma-count-based approach (cf. Subsection 4. 1.2.1) we have:

µ(e) = µ Q {(res i ,x i ,µ Bi ,µ Ai )∈ Q derived |res i =e} min(µ Ai , µ Bi ) {(res i ,x i ,µ Bi ,µ Ai )∈ Q derived |res i =e} µ Bi (6.6)
In the case of a fuzzy absolute quantied query, the nal satisfaction degree associated with each element e is simply

µ(e) = µ Q   {(res i ,x i ,µ Bi ,µ Ai )∈ Q derived |res i =e} µ Ai   .
Example 62 [Evaluation of a Fuzzy Quantied Query] Let us consider the fuzzy quantied query Q mostAuthors of Listing 6.4. We evaluate this query according to the fuzzy data graph DB of Figure 6. Finally, assuming for the sake of simplicity that µ most (x) = x, the nal result of the query Q mostAuthors evaluated on DB using Formula 6.6 is Using Yager's OWA-based approach (cf. subsection 4. 1.2.2), for each element e returned by Q derived we calculate µ(e) = {(res i ,x i ,µ Bi ,µ Ai )∈ Q derived |res i =e} w i × c i . The weights of the OWA operator are dened by

Q mostAuthors = { µ(Peter) = µ most ( 0.
w i = µ Q (S x i ) -µ Q (S x i-1 ) with S x i = i j=1 µ B j d .
The implication values are denoted by

c x i = max(1 -µ B i , µ A i )
and ordered decreasingly such that c 1 ≥ . . . ≥ c n .

Example 63 In order to calculate µ(Maria) from Q derived , let us consider B (resp.

A) the set of satisfaction degrees corresponding to condition B (resp. A) of element Maria as follows B={0.33/IJAR14, 0.6/IJIS16} and A={1/IJAR14, 6.4. About Query Processing The compilation uses the derivation principle introduced in [START_REF] Bosc | SQLf query functionality on top of a regular relational database management system[END_REF] in the context of relational databases. 2. In a post-processing step, the Score calculator module performs a grouping (according to the with clause of the initial query) of the elements, then calculates µ B , µ A and µ for each returned answer, and nally ranks the answers. For quantied queries of the type introduced in the previous sections (i.e., using relative quantiers), the principle is to rst evaluate the fuzzy query Q derivedBoolean derived from the original query.

For each element x ∈ Q derivedBoolean , we return the satisfaction degrees related to conditions A and B, denoted respectively by µ A and µ B . The nal satisfaction degree µ can be calculated according to Formulas (4.3), (4.8) or (4.17) (presented in Chapter 4 Subsection 4. 1.2) using the values of µ B and µ A . At the current time, [Zadeh, 1983]'s approach and [Yager, 1988]'s OWA-based approach have been implemented, and the choice of the interpretation to be used is made through the system conguration tool. Finally, a set of answers ranked in decreasing order of their satisfaction degree is returned.

As a proof-of-concept of the proposed approach, the FUDGE prototype is available at www-shaman.irisa.fr/fudge-prototype.

A screenshot of this prototype is shown in Figure 6.7 which contains the nal result of the evaluation of the query Q mostAuthors of Example 61. The GUI is composed of two frames:

• a central frame for visualizing the graph and the results of a query, and

• an input eld frame (placed under the central one), for entering and running a FUDGE query. Figure 6.7: Screenshot of the FUDGE prototype 6.5 Experimental Results In order to conrm the eectiveness and eciency of the approach, we carried out some experiments on a computer running on Windows 7 (64 bits) with 8 Gb of RAM. The queries used in these experiments are based on the typology of [Angles, 2012] that considers three categories of queries:

• Adjacency query: tests whether two nodes are adjacent (or neighbors) when there exists an edge between them or whether two edges are adjacent when they have a common node.

• Reachability query: tests whether two given nodes are connected by a path. Two types of paths are considered: xed length paths, which contain a xed number of nodes and

• The fourth query Q 4 (Listing 6.11), where A is a pattern matching, aims to nd the authors (a) such that most of the recent papers (p) of which they are main authors, have been published in a renowned database journal (j). The results of the processing of these queries over the RDF datasets from Table 6.1 are depicted in Figure 6.8 where Figure 6. The main result is that the processing time taken by the compiling and the score calculation stages, which are related to the introduction of exibility into the query language, are very strongly dominated by the time taken by the crisp Cypher evaluator.

Moreover, the FUDGE compiling stage takes so little time compared to the other two stages that it cannot even be seen in Figure 6.

Conclusion

In this chapter, we have dealt with fuzzy quantied structural queries, addressed to fuzzy graph databases. We have rst dened the syntax and semantics of a fuzzy extension of the query language Cypher. This extension makes it possible to express and interpret such queries with dierent approaches from the literature. A query processing strategy based on the derivation of nonquantied fuzzy queries has also been proposed. Then, we updated the software SURF described in [Pivert et al., 2015[START_REF] Pivert | SUGAR: A graph database fuzzy querying system[END_REF] to be able to express such queries and performed some experiments using dierent sizes of fuzzy graphs in order to study its performances. The results of these experiments show that the cost of dealing with fuzzy quantication in a query is reasonable w.r.t. the cost of the overall evaluation.

Conclusion

The last decade has witnessed an increasing interest in expressing preferences inside database queries for their ability to provide the user with the best answers, according to his/her information need. Even though most of the work in this area has been devoted to relational databases, several proposals have also been made in the Semantic Web area in order to query RDF databases in a exible way. However, it appears that these approaches are mainly straightforward adaptations of proposals made in the relational database context: they make it possible to express preferences on the values of the nodes, but not on the structure of the RDF graph. Structural preferences are quite important in a graph database context and may concern the strength of a path, the distance between two nodes, etc. Moreover, these approaches consist of exible extensions of the SPARQL query language that only deal with crisp RDF data. In the real world, though, semantic Web data often carry gradual notions such as friendship in social networks, aboutness in a bibliographic context, etc. Such notions can be modeled by fuzzy sets, which leads to attaching a degree in [0, 1] to the edges of the graph.

Motivated by these concerns, we addressed in this thesis the issue of ecient querying of (fuzzy) RDF data with the aim of extending the SPARQL query language so as to be able to express i) fuzzy preferences on data (e.g., the release year of a movie is recent )

and on the structure of the data graph (e.g., the path between two friends is required to be short ). and ii) fuzzy quantied preferences (e.g., most of the albums that are recommended by an artist, are highly rated and have been created by a young friend of this artist).

To the best of our knowledge, this thesis is the rst attempt in this direction in which we provide solutions for these dierent issues. After motivating our work, we presented in Chapter 1 basic notions related to our thesis, namely the RDF data model, the SPARQL query language and fuzzy set theory.

In Chapter 2 we provided an overview of the main proposals made in the literature that propose a exible extension of SPARQL based on user preferences queries, relaxation techniques and approximate matching. We discussed these approaches, classied them and pointed out their limits.

Chapter 3 was dedicated to the denition of a fuzzy extension of SPARQL that goes beyond the previous proposals in terms of expressiveness inasmuch as it makes it possible i) to deal with both crisp and fuzzy RDF databases, and ii) to express fuzzy structural conditions beside more classical fuzzy conditions on the values of the nodes present in the RDF graph.

The language, called FURQL, is based on the notion of fuzzy graph pattern which extends Boolean graph patterns introduced by several authors in a crisp querying context.

Then, in Chapter 4 we proposed to integrate more complex conditions, namely, fuzzy quantied statements of the type Q B X are A into the FURQL language (addressed to fuzzy RDF database) previously introduced in Chapter 3. We dened the syntax and semantics of an extension of the FURQL query language, that makes it possible to deal with such queries. A query processing strategy based on the derivation of nonquantied fuzzy queries has also been proposed.

These functionalities were successfully implemented using a prototype called SURF.

Experimental results, described in Chapter 5, show the validity of the approach. In the case of fuzzy nonquantied queries, the results obtained indicate that introducing fuzziness into a SPARQL query comes with a very limited cost. And in the case of fuzzy quantied queries, the results show that the extra cost induced by the fuzzy nature of the queries remains also very limited, even in the case of rather complex fuzzy quantied queries.

Finally, the last chapter was devoted to integrating fuzzy quantied queries in an extension of the Neo4j Cypher language, called FUDGE, (described in [START_REF] Pivert | On a fuzzy algebra for querying graph databases[END_REF][START_REF] Pivert | SUGAR: A graph database fuzzy querying system[END_REF]) in a more general (fuzzy) graph database context (of which fuzzy RDF databases are a special case). We rst proposed a syntactic format for expressing these queries in the FUDGE language, and we described their interpretation using dierent approaches from the literature. Then, we carried out some experimentations in order to assess the performances of the evaluation method. The results of these experiments show that the cost of dealing with fuzzy quantication in a query is very reasonable w.r.t. the cost of the overall evaluation.

Future Work

In this thesis, we have proposed a fuzzy extension of the SPARQL query language that makes it possible to express fuzzy structural conditions and fuzzy quantied statements in an ecient way. This work serves as a baseline and leaves some open questions to solve and sets the basis for further extensions. Dierent perspectives on short-term and long-term work have been identied and are outlined hereafter.

Extend the FURQL and FUDGE languages with more sophisticated preferences

In this thesis, we limited fuzzy structural properties to the distance and the strength where the distance between two nodes is the length of the shortest path between these two nodes and the strength of a path is dened to be the weight of the weakest edge of the path. It is also worth to consider other structural properties, like:

• the centrality, the prestige and the inuence used in social networks analysis [START_REF] Rusinowska | Social networks: prestige, centrality, and inuence[END_REF]. For instance, the degree of centrality of a node measures the extent to which this node is connected with other nodes in a given social network.

The question to answer is how central this node is in this network. The degree of prestige measures the extent to which a social actor in a network receives or serves as the object of relations sent by others in the network. Persons, who are chosen as friends by many others have a special position (prestige) in the group.

• the clique which is one of the basic concepts of classical graph theory. Ronald R. Yager in [Yager, 2014] redened this notion in the case of a fuzzy graph.

Moreover, we introduced a specic type of fuzzy quantied queries of the form: Q nodes, among those that are connected to a node x according to a certain pattern, satisfy a fuzzy condition c. An example of such a statement is most of the papers whose x is a main author, have been published in a renowned database journal. It would be interesting to study other types of fuzzy quantied queries, in particular, those that aim to nd the nodes x such that x is connected (by a path) to Q nodes reachable by a given pattern and satisfying a given condition c. An example of such a query is nd the authors x that had a paper published in most of the renowned database journals. And also those that aim to nd if there exists a path from x to a node satisfying c such that this path contains Q nodes (where Q is an absolute quantier).

Make SURF and SUGAR more user-friendly

The softwares that we developed make it possible to express fuzzy user preferences where the query is explicitly written in the syntax of the formal query language (FURQL for RDF data and FUDGE for graph data) and the fuzzy terms are dened in the query by a predened clause define. These softwares may be improved further in order to make them more user-oriented.

One can think rst about proposing a way to help non-expert users dene fuzzy terms easily. There is, therefore, a denite need about developing a user interface in order to help casual users dene their preferences and the underlying fuzzy membership functions in a more easy way, following the work of [START_REF] Smits | ReqFlex: Fuzzy Queries for Everyone[END_REF] in which the authors described ReqFlex, an intuitive user interface to the denition of preferences and the construction of fuzzy queries in a relational context.

Moreover, we may think also about integrating and analysing user proles in order to focus more on the user's interest and preferences and take into account the user's context in order to personalise the retrieved information.

Add Quality-Related Metadata Another important perspective concerns the management of quality-related metadata [START_REF] Fürber | Using semantic web resources for data quality management[END_REF]. Since the RDF model that we used in this thesis makes it possible to model fuzzy notions, we can extend this model to represent data quality dimensions (e.g., accuracy, completeness, timeliness, consistency and so on). Indeed, these dimensions are of fuzzy nature and the values returned by the associated metrics may be viewed as satisfaction degrees.

Then, it would be also worth investigating the way our framework FURQL could be extended:

1. to express fuzzy preferences queries concerning some quality dimensions. 2. to associate quality information with the answers to a query. This would make it possible to rank-order the answers according to their quality level (on one or several dimensions) and to warn the user about the presence of suspect answers, for instance. [START_REF] Bizer | The Berlin SPARQL Benchmark[END_REF], DBpedia SPARQL Benchmark (DBPSB) [START_REF] Morsey | DBpedia SPARQL BenchmarkPerformance Assessment with Real Queries on Real Data[END_REF], etc.) for data generator and benchmark queries in order to evaluate the performance of RDF stores. However, none of the existing benchmarks provides fuzzy RDF data or explicitly deals with fuzzy user preferences.

For that purpose, in this thesis, we initially performed the evaluation of our approaches using a fuzzy RDF database inspired by Musicbrainz 4 with synthetic data generated by a script that allowed us to create datasets of dierent sizes.

A future work would be to consider further evaluation using some of the existing real-world data benchmarks or ideally create our own Fuzzy RDF Benchmark.

Obviously, many research problems remain open and this thesis is only a rst step which will help, we hope, to convince the databases community of the interest of using fuzzy logic for the exible/intelligent management of data in information systems.

Example 2 [

 2 RDF graph] Let us consider an example of an RDF subgraph extracted from the MusicBrainz database 1 which is an open music encyclopedia that collects music metadata. The resource uri:lemonade is an album, entitled Lemonade. It was released in 2016, with genre R&B and rating 8.7. It was created by the resource uri:beyonce, named Beyonce, being 38 years old and a rating of 7. The resource uri:sorry and the resource uri:holdup entitled hold up are tracks of the latter resource. The resource uri:beyonce also created the resource uri:B'Day, entitled B'Day, that was released in 2006.

Figure 1 . 1 Figure 1 . 1 :

 1111 Figure 1.1: Sample RDF graph extracted from MusicBrainz

  In fact, RDF data may be represented by dierent syntaxes such as, RDF/XML (eXtensible Markup Language) 2 , N-Triples 3 , Notation 3 or N3 4 and Turtle (Terse RDF Triple Language) 5 , etc. Example 3 [RDF representations] Listing 1.1 is the RDF/XML representation corresponding to the resource uri:Lemonade from the RDF graph of Figure 1.1.

  rdf:resource=mo:album </rdf:type> 11 <dc:track> rdf:resource="uri:sorry" </dc:track> 12 <dc:track> rdf:resource="uri:hold up" </dc:track> 13 </rdf:Description> 14 </rdf:RDF> Listing 1.1: RDF/XML document In this listing, line 1 indicates an XML declaration and line 2 says that the following XML document is about RDF. Lines 2-4 declare namespaces which indicate the URI that will be used later. Lines 5-14, as the tag is closed in line 14, present the description of a resource in which lines 6-12 describe characteristics of this resource. Its corresponding N-Triples representation is given in Listing 1.2.

Listing 1 . 3 :

 13 A SPARQL Basic Graph PatternA graphical representation of this graph pattern is depicted in Figure1.2.

Figure 1 . 2 :

 12 Figure 1.2: A graphical representation of the graph pattern from Listing 1.3

Figure 1 . 3 :

 13 Figure 1.3: Possible subgraphs from Figure 1.1

  .

  4. The set of t-norms (resp. t-conorms ) has an upper (resp. lower) element which is the minimum (resp. maximum) operator. Example 22 Let us come back to Example 19. The intersection of the two fuzzy subsets, taking = min, is as follows:

  Most fuzzy terms are assumed to be represented by a trapezoidal membership function (see for instance a possible representation of recent in Figure2.1).

Figure 2 . 1 :

 21 Figure 2.1: Membership function of recent

Figure 2 . 2 :

 22 Figure 2.2: Membership function of the fuzzy number at least Y

Listing 2 . 1 :

 21 An f-SPARQL query This query aims to retrieve from a music database the albums by Beyonce that have been recently released. If the MusicBrainz RDF database of Figure 1.1 on page 23 is queried, then the album entitled Lemonade belongs to the answer, with a satisfaction degree of 0.66, which corresponds to the degree of membership of value 2016 to the fuzzy term recent (see Figure 2.1). The other album from Figure 1.1, released in 2006, does not belong to the answer as it is not at all recent according to Figure 1.1.

Figure 2 .

 2 Figure2.3, where J, P and S are binary variables corresponding to the colors of the jacket, the pants and the shirt respectively.

b

  ∧ b : r w w ∧ b : w r b ∧ w : w r w ∧ w : r w

Figure 2 . 3 :

 23 Figure 2.3: CP-net of Example 34

Figure 2 . 4 :

 24 Figure 2.4: An RDFS Ontology

[

  or vague. They propose a conceptual framework to relax RDF queries relying on a matcher function (i.e., distance function) that assigns a relaxation score in [0,1] to a pair of values.

  tated in the previous chapter, RDF is a graph-based standard data model for representing semantic web information, and SPARQL is a standard query language for querying RDF data. Because of the huge volume of linked open data published on the web, these standards have aroused a large interest in the last years.

  extension allows(1) to query both crisp and fuzzy RDF data model, and (2) to express fuzzy preferences on values present in the graph as well as on the structure of the data graph, which has not been proposed in any previous fuzzy extension ofSPARQL.

62 3 . 1 .

 31 Fuzzy RDF (F-RDF) GraphThis work has been published in the proceedings of the 25th IEEE International Conference on Fuzzy Systems (Fuzz-IEEE'16),Vancouver, Canada, 2016.

Figure 3 . 1 :

 31 Figure 3.1: Fuzzy RDF graph G M B inspired by MusicBrainz

  41 [Distance and strength between two nodes] Let us consider the cycle-free paths from G M B connecting Beyonce to Euphoria, depicted in Figure 3.2, and let us compute the distance and the strength between the pair of nodes (Beyonce, Euphoria). The distance between the pair of nodes (Beyonce, Euphoria) is calculated as follows distance(Beyonce, Euphoria) = min (length(p 1 ), length(p 2 ), length(p 3 )), with length (p 1 )= 1/ζ (Beyonce, recommends, Euphoria )= 1/0

Figure 3 . 3 :

 33 Figure 3.3: A possible representation of the fuzzy term short

Figure 6 Figure 3 . 4 :

 634 Figure 6.3 is a graphical representation.

2 .Figure 3 . 5 :

 235 Figure 3.5: Representation of the fuzzy term low applied to a rating value

Figure 3 . 5 ,

 35 Figure 3.5, and the following clause denes the fuzzy term short of Figure 3.3.

Figure 3 . 6 :

 36 Figure 3.6: Some paths from G M B .

  .6 , satisfy f 1 with the following satisfaction degrees:sat f 1 (EnriqueI, Justied) = min(ζ(EnriqueI, friend, JustinT), ζ(JustinT, creator, Justied)) = min(0.4, 1) = 0.4, sat f 1 (Shakira, Buttery) = min(ζ(Shakira, friend, MariahC), ζ(MariahC, creator, Buttery)) = min(0.7, 1) = 0.7, sat f 1 (Beyonce, Euphoria) = max(min(ζ(Beyonce, friend, Rihanna), ζ(Rihanna, friend, EnriqueI),ζ(EnriqueI, creator, Euphoria)), min(ζ(Beyonce, friend, MariahC), ζ(MariahC, friend, Shakira), ζ(Shakira, friend, EnriqueI), ζ(EnriqueI, creator, Euphoria))) = max(min(0.6, 0.2, 1), min(0.8, 0.3, 0.5, 1)) = 0.3, sat f 1 (Rihanna, Euphoria) = min(ζ(Rihanna, friend, EnriqueI), ζ(EnriqueI, creator, Euphoria)) = min(0.2, 1) = 0.2, sat f 1 (MariahC, Euphoria) = min(ζ(MariahC, friend, Shakira), ζ(Shakira, friend, EnriqueI), ζ(EnriqueI, creator, Euphoria)) = min(0.3, 0.5, 1) = 0.3, and sat f 1 (Shakira, Euphoria) = min(ζ(Shakira, friend, EnriqueI), ζ(EnriqueI, creator, Euphoria))

Figure 3 .

 3 Figure3.8 gives the set of subgraphs of G M B satisfying the pattern P rec_low .The matching value of Art1 is either Shakira or EnriqueI who match the pattern P rec_low (i.e they are the only artists that have liked a low rated album created by another artist among their close friends).Note that (f riend + ) distance is short .creator is the fuzzy regular expression f 2 of Example 44 with sat f 2 (EnriqueI, Justied) = 0.4, sat f 2 (Shakira, Buttery) = 0.7 and sat f 2 (Shakira, Euphoria) = 0.5 and we consider µ low_rating (4) = 0.66, µ low_rating (6) = 0.33 and µ low_rating (9) = 0 dened in Figure3.5 on page 70.Then, the evaluation of the pattern P rec_low over the RDF graph G M B includes two mappings with their respective satisfaction degrees:

Figure 3 . 8 :

 38 Figure 3.8: Subgraphs satisfying P rec_low

Figure 4 . 1 Figure 4 . 1 :

 4141 Figure 4.1 gives two examples of monotonous decreasing and increasing fuzzy quantiers respectively.

Figure 4 . 2 :

 42 Figure 4.2: The fuzzy quantier at least ve

  us consider a quantied statement of the form Q B X are A from Example 47 and Q(x) = x 2 .

Figure 4 . 3 :

 43 Figure 4.3: Membership functions of Example 51

1 Figure 4 . 4 :

 144 Figure 4.4: Membership function of the fuzzy term strong

Figure 4 . 5 :

 45 Figure 4.5: Fuzzy RDF graph G M B inspired by MusicBrainz

6 :

 6 Query R atBoolean derived from R at This query returns a list of artist (?art1) with their recommended albums (?alb), satisfying the conditions of query R at , along with their respective satisfaction degrees µ B = min(µ recent (?alb), ζ(?art1, recommends, ?alb)) and µ A = min(µ high (?rating), µ young (?age), ζ(?art1, f riend, ?art2)).

Figure 5 . 1 :

 51 Figure 5.1: Reication of fuzzy triple of Example 55

ClientFigure 5 . 2 :

 52 Figure 5.2: Implementation of a specic FURQL query evaluation engine

Figure 5 . 3

 53 Figure 5.3 illustrates this architecture.

Figure 5 . 3 :

 53 Figure 5.3: SURF software architecture

3 .

 3 For a classical SPARQL query, we skip the Query compiler and Score calculator modules and the original query is transferred directly to the classical SPARQL engine. All the answers returned by the SPARQL engine are kept in the nal resultset with a satisfaction degree equal to1.

Figure 5 . 4 :

 54 Figure 5.4: Screenshot of SURF

Figure 5 . 5 :

 55 Figure 5.5: Edge query of the form edge-so

  Figure 5.8: Experimental results about the evaluation of FURQL queries

Figure 5 . 9 :

 59 Figure 5.9: Experimental results of Fuzzy Quantied queries involving crisp conditions

Figure 5 .

 5 Figure 5.10: Experimental results of Fuzzy Quantied queries involving fuzzy conditions

  and where n is the number of links in the path. The strength of the path is dened asST (p) = min i=1..n ρ(x i-1 , x i ).

4 (

 4 -[:author_of]->(ar1:paper), (ar1)-[:published]->(j1), au1)-[:author_of]->(ar2:paper), (ar2)-[:published]->(j2) 5 where j1.name="IJWS12" and j1.name <> j2.name Listing 6.1: Pattern expressed à la Cypher This pattern models information concerning authors (au2) who have, among their contributors, an author (au1) who published a paper (ar1) in IJWS12 and also published a paper (ar2) in another journal (j2).

Figure 6 . 3

 63 is a graphical representation of P.

Figure 6 . 3 :

 63 Figure 6.3: Pattern P

4 ( 5 (

 45 -[(contributor+)|Length is short]->(au1:author), au1)-[:author_of]->(ar1:paper), (ar1)-[:published]->(j1),

5 :

 5 Derived query Q derived Such a query allows to retrieve the pairs {res, x} that belong to the graph and all the information needed for the calculation of µ B and µ A , i.e., the combination of fuzzy degrees associated with relationships and node attribute values involved in B(res,x) and in A(x), respectively denoted by I B and I A . The Listing6.6 of Example 62 below presents the derived query associated with the query Q mostAuthors .

2 .

 2 In order to interpret Q mostAuthors , we rst derive the following query Q derived from Q mostAuthors , that retrieves the authors (a) who highly contributed to at least one recent paper (p) (corresponds toB(a,p) in lines 1 and 2) possibly (optional) published in a renowned database journal (corresponds to A(p) in lines 3 to 5).

1

  match (a:author)-[author_of|ST IS strong]->(p:paper) 2 where p.year is recent 3 optional match (p)-[:published]->(j:journal), 4 (j)-[:impact_factor]->(i:impact_factor), (j)-[:domain]->(d:dom) 5 where i.value is high and d.name="database" 6 return a p µ A µ B Listing 6.6: Query Q derived derived from Q mostAuthors For the running example, Q derived returns the four answers {Peter, Maria, Claudio, Michel}. The authors Andreas, Susan and Bazil do not belong to the result of Q mostAuthors because Susan has not written a journal paper yet and Andreas and Bazil do not have a recent paper.For the running example, we then have Q derived (P eter) = {((0.2, 1)/IJAR14_p)}, Q derived (M aria) = {((0.33, 1)/IJAR14_p), ((0.6, 0.33)/IJIS16_p)}, Q derived (Claudio) = {((0.33, 1)/IJAR14_p), ((0.3, 0.07)/IJUFK15_p)}, and Q derived (M ichel) = {((0.3, 0.07)/IJUFK15_p)}.

  2 0.2 ) = 1, µ(Maria) = µ most ( 0.66 0.93 ) = 0.71, µ(Claudio) = µ most ( 0.4 0.63 ) = 0.63, µ(Michel) = µ most ( 0.07 0.3 ) = 0.23}.

  the fuzzy set B = {µ B 1 /x 1 , ..., µ Bn /x n } such that µ B 1 ≤ ... ≤ µ Bn , the fuzzy set A = {µ A 1 /x 1 , ..., µ An /x n } and d = n i=1 µ B i .

Figure 6 Figure 6 . 6 :

 666 Figure 6.6 illustrates this architecture.

  p) are ( (p)-[:published]->(j:journal), 7 (j)-[:impact_factor]->(i:impact_factor), (j)-[:domain]->(d:dom) 8 where i.value is high and d.name="database" ) 9 return a Listing 6.11: Fuzzy quantied query with pattern matching Our experiments have been performed on a database inspired from DBLP containing crisp (e.g., published ) and fuzzy edges (e.g., contributor ). A java script have been developed to create random graph data of dierent sizes. In these experiments, four database sizes have been considered, see Table 6

  .

  1.

  8.(a) (resp., Figure 6.8.(b)) presents the execution time in milliseconds using Zadeh's interpretation (resp., Yager's OWA-based interpretation).

  8. This time remains almost constant, and is independent on the size of the dataset while slightly increasing in the presence of complex patterns or fuzzy conditions. As to the score calculation stage, it represents around 9% of the time needed for evaluating a fuzzy quantied FUDGE query. The time used for calculating the nal satisfaction degree is of course dependent on the size of the result set and the nature of the patterns.

  Figure 6.8: Experimental results of fuzzy quantied queries in FUDGE

  'interroger un modèle de données RDF ou dans lequel les triplets sont porteurs de notions graduelles (dont le modèle RDF non ou est un cas particulier), et 2. d'exprimer des préférences oues portant non seulement sur les données mais également sur la structure du graphe, que celui-ci soit ou ou non.

	Modèle RDF ou Dans cette thèse, nous considérons un modèle de données,
	appelée	F-RDF,	qui	synthétise	les	modèles	RDF	ous	de	la	littérature

  Par exemple, le triplet ou Beyonce, recommande, Euphoria auquel est attaché le degré 0.8 indique que Beyonce, recommande, Euphoria est satisfait au niveau 0.8, ce qui peut être interprété comme Beyonce recommande fortement Euphoria. Les degrés ous peuvent être donnés ou calculés, matérialisés ou non. Dans sa forme la plus simple, un degré peut correspondre au calcul d'une notion statistique reétant l'intensité de la relation à laquelle le degré est attaché. Par exemple, l'intensité d'une relation d'amitié d'une personne p 1 vers une autre personne p 2 peut être calculée par la proportion d'amis communs par rapport au nombre total d'amis de p 1 .

[

  Pivert et al., 2016f] Pivert, O., Slama, O., and Thion, V. (2016f ). Requêtes quantiées oues structurelles sur des bases de données graphe. In Actes des Rencontres Franco-

	phones sur la Logique Floue et ses Applications (LFA'16), La Rochelle, France, pages
	9-16.

  Denition 1 (RDF triple). Let U be the set of URIs, B the set of blank nodes, and L the set of literals. An RDF triple t:= s, p, o ∈ (U ∪ B) × U × (U ∪ L ∪ B) where the subject s denotes the resource being described, the predicate p denotes the property of the resource, and the object o denotes the property value. A triple t states that the subject s has a property p with a value o.Example 1 [RDF triple] For instance, the triple Beyonce, creator, Lemonade states that Beyonce has Lemonade as a creator property, which can be interpreted as Beyonce is a creator ofLemonade.

  1 <?xml version="1.0"?> 2 <rdf:RDF xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" 3 xmlns:mo="http://purl.org/ontology/mo/" 4 xmlns:dc="http://purl.org/dc/elements/1.1/"> 5

<rdf:Description rdf:about="uri:Lemonade">

  :Lemonade> <http://www.w3.org/1999/02/22-rdf-syntax-ns#/type> <mo:album> .

	Listing 1.2: N-Triples le
	<uri:Lemonade> <http://purl.org/dc/elements/1.1/date> "2016" .
	<uri:Lemonade> <http://purl.org/dc/elements/1.1/title> "Lemonade" .
	<uri:Lemonade> <http://purl.org/dc/elements/1.1/rating> "8.7" .
	<uri:Lemonade> <http://purl.org/dc/elements/1.1/genre> "R & B" .

<uri:Lemonade> <http://purl.org/dc/elements/1.1/track> <uri:sorry> . <uri:Lemonade> <http://purl.org/dc/elements/1.1/track> <uri:hold up> .

<uri

  SPARQL: Crisp Querying of RDF data

	In	order	to	eciently	query	RDF	data,	the	SQL-like	language	SPARQL
	[Prud'hommeaux and Seaborne, 2008] is promoted by the W3C as a standard query
	language. It is a declarative query language based on graph pattern matching, in the sense
	that the query processor searches for sets of triples in the data graph that satisfy a graph
	pattern expressed in the query.
		A Basic Graph Pattern (BGP) is a basic building block of SPARQL, containing a set of
	triple patterns. A triple pattern is an RDF triple where variables may occur in the subject,
	predicate, or object position. Each variable is prexed by the question mark symbol.

the results that do not match a given graph pattern. The second one uses theminus clause and aims to remove answers related to another pattern. Example 15 [Negation queries] The following query aims to nd the artists

  exp 1 and exp 2 are property path expressions, then, exp 1 |exp 2 and exp 1 /exp 2 are property path expressions, if exp is a property path expression, then, exp * , exp + , exp ? and ˆexp are property path expressions.where exp 1 |exp 2 denotes alternative expressions, exp 1 /exp 2 denotes a concatenation of exp 1 and exp 2 , exp * denotes a path that connects the subject and object of the path by zero or more matches of exp, exp + is a shortcut for exp * /exp and denotes a path that connects the subject and object of the path by one or more matches of exp, exp ? denotes a path that connects the subject and object of the path by zero or one matches of exp, ˆexp is an inverse path (from an object to the subject).

	Example 13 [Update query] The following query aims to add some infor-
	mation about a new artist "Ed Sheeran" in the default graph.
	insert data {	].	These works proposed more expressive
	languages and extended SPARQL by allowing path extraction queries (generally of uri:EdSheeran dc:title "Ed Sheeran" . uri:EdSheeran dc:age "26" .
	unknown length) within RDF datasets. Property paths came with the same principle uri:EdSheeran dc:rating "8" . }
	which is to allow for navigational querying over RDF graphs and are ocially integrated Listing 1.14: An example of an Update query
	in SPARQL 1.1. A property path is a possible path through a graph between two
	nodes. It can be of a variable length. A property path of length exactly 1 is a triple • Subqueries: The principle is the same as subqueries in SQL: a query may use the
	pattern. output of other queries for achieving complex results.
	Denition 3 (SPARQL property path expressions). SPARQL property path expressions Example 14 [Subqueries in SPARQL] Return a name (the one with the
	are recursively dened by: lowest sort order) for all the artists who are friend with beyonce and have a
	name. an IRI 9 is a property path expression that denotes a path of length one, select ?art ?minName where {
		uri:beyonce uri:friend ?y .
		{
		select ?art (min(?name) as ?minName) where {
		?art uri:title ?name .
		} group by ?art
		} }
		Listing 1.15: Query involving a subquery
	• Negation: can be expressed in two ways. The rst uses the not exists clause and aims
	Example 12 [SPARQL property path query] Find the names of the artists to lter out who have issued no albums in 2015.
	that recommend albums made by friends or related friends of friends. select ?name where {
	select ?name where { ?artist dc:creator ?album .
		?art1 dc:title ?name . ?art1 dc:recommends ?alb . filter not exists { ?artist dc:date "2005" . }
	}	?art2 dc:creator ?alb . ?art1 dc:friend+ ?art2 .
	} Listing 1.16: SPARQL query with negation (not exists)
		Listing 1.13: SPARQL query with property path
	The query that aims to retrieve names of artists having no albums is depicted
	in Listing 1.17.
	• Update functionalities: In addition to querying and manipulating RDF data, select ?name where {
	SPARQL 1.1 Update [Gearon et al., 2012] oers the possibility to modify the graph by ?artist dc:title ?name .
	adding/deleting triples, loading/clearing/creating/dropping an RDF graph and many minus { ?artist dc:creator ?album . }
	other facilities. }
		Listing 1.17: SPARQL query with negation (minus)

if

  , when X is a nite set {x 1 , ..., x n }, is:

	Example 18 Let us consider the example of the predicate tall described in Ta-A more convenient notation
	ble 1.3. Tall can be dened by a Boolean condition (height ≥ 180). It corresponds
	to the crisp set (non fuzzy set) of Figure 1.5 and the result is in the third column
	of Table 1.3.
			Name	height(cm)	Memberships
						Crisp	Fuzzy
			Chris	210		1	1
			Marc	200		1	1
			John	190		1	1
			Tom	180		1	0.66
			David	170		0	0.33
			Tom	160		0	0
			David	150		0	0
			Table 1.3: Tall men
	However, it seems more natural to dene the predicate tall as a fuzzy set (cf., Fig-
	ure 1.6). The membership degrees associated with some individuals are shown in
	the fourth column of Table 1.3.
	Degree of
	membership
	1
	0
			160	170	180		190	200	210
									Height, cm
	Figure 1.5: Graphical representation of the predicate tall (crisp set)
	Degree of
	membership
	Degree of 1
	membership
	0.66
	0.33	1					µ A
	0
		0	A -a 160	A 170	180	B	190	200 B + b	210 X Height, cm
	Figure 1.4: Trapezoidal membership function Figure 1.6: Graphical representation of the predicate tall (fuzzy set)

Table 1 .

 1 . 4: Properties of t-norm and t-conorm operators

	Property	T-norm	T-conorm
	Identity

Table 2 .

 2 ..,θ y with α being an RDF statement and θ 1 ,...,θ y being its annotations over a xed set Γ = {p 1 , ..., p y } of independent

	annotation dimensions.
	Example 29 Let us consider the RDF statement about music concerts shown
	in Table 2.1.	Each statement is annotated by a set of dimensions Γ =
	{Time, Source, Certainty}.
					Dimensions
	Id	Statement	Time	Source	Certainty
	#1	TAL playsIn Le Grand Rex	03.02.17	www.legrandrex.com	0.9
	#2	KUNGS playsIn L'OLYMPIA	15.01.17	www.fnacspectacles.com	0.7
	#3	TAL hasRating 7	10.01.17	www.itunes.apple.com	0.5
	#4	KUNGS hasRating 8	08.02.17	www.itunes.apple.com	0.5

1: The set of annotated RDF statements

  32 In order to illustrate the form taken by skyline queries in PrefS-PARQL, let us consider again the query from Example 2.7. Listing 2.8 expresses

	this in PrefSPARQL.
	select ?artist ?concert where {
	?artist dc:concert ?concert. ?concert dc:starts ?startingTime.
	?concert dc:ends ?endingTime. ?artist dc:rating ?rating .
	preferring ( ?rating = ft:excellent and
	(?startingTime between (9pm, 1am) and ?endingTime between (9pm, 1am)
	prior to highest (?endingTime)))}
	Listing 2.8: Skyline query in PrefSPARQL
	Example 33 So as to illustrate conditional preferences, let us now assume that
	a user prefers a concert which takes place after 7:30pm on the weekdays and before
	7pm during the weekends, formulated in Listing 2.9.

This extension of SPARQL called PrefSPARQL supports not only the expression of qualitative preferences (skyline) but also conditional ones (if-then-else). A PrefSPARQL query returns a set of partially ordered tuples according to the satisfaction of the preferences.

Example

select ?concert where { ?concert dc:day ?D. ?concert dc:starts ?startingTime. preferring (if (?D = ``Saturday'' || ?D = ``Sunday'') then ?startingTime < 7pm else ?startingTime >= 7:30pm)} Listing 2.9: Conditional preference in PrefSPARQL

Table 2 . 2

 22

: RDFS Inferences Rules Example 36 The rule (4) from Table 2.2 states that if a is a subclass of b and

Table 2

 2

	Predicate relaxation for example, using rule (2) from Table 2.2, the triple pattern
	(?X, proceedingsEditorOf, ?Y) can be relaxed into (?X, editorOf, ?Y) and then into
	(?X, contributorOf, ?Y) since we have (proceedingsEditorOf, sp, editorOf ) ∈ cl(O)
	and then (editorOf, sp, contributorOf ) ∈ cl(O);
	Predicate to domain relaxation for example, using rule (5) from Table 2.2, the
	triple pattern (a, p, b) can be relaxed into the triple pattern (a, type, c), since we
	have the triple pattern (p, dom, c) ∈ cl(O).

.2

, the triple pattern (?X, type, ConferenceArticle) can be relaxed into (?X, type, Article) and then into (?X, type, Publication) since we have (ConferenceArticle, sc, Article) ∈ cl(O) and then (Article, sc, Publication) ∈ cl(O);

  and has as a principle to determine if two given graphs are the same; if they are, nd a matching (mapping) between them (i.e., which nodes

	However,	all of the existing classical graph isomorphism algorithms do not
	t the semantic characteristics of RDF graphs (i.e.,	directed graphs with la-
	beled	edges	and	nodes)	[Carroll, 2002].	Then,	an	ecient	semantic	similar-
	ity measure based on RDF graph is required.	Therefore, few approaches have
	proposed	new	techniques	dealing	with	approximate	querying	over	RDF	data

from one graph correspond to which nodes in the other. Similarity measures based on graph matching are commonly used in this context. Essentially, queries are represented as a graph (called the query graph ) and the aim is to nd an appropriate matching between the query graph and the resource graph.

  1 and y is the object of t n .

	Example	40 [Path		between		two	nodes]	The	(cy-
	cle	free)	paths		between		the	nodes	Beyonce	and
	Euphoria from the fuzzy RDF graph G M B of Figure 3.1 are shown in Fig-
	ure 3.2.
			Beyonce	recommends(0.8)	Euphoria
							(p 1 )
	Beyonce	friend(0.6)	Rihanna	friend(0.2)	EnriqueI	creator	Euphoria
							(p 2 )
	Beyonce	friend (0.8)	MariahC	friend (0.3)	Shakira	friend (0.5)	EnriqueI	creator	Euphoria
							(p 3 )
	dened by
				distance(x, y) =	min
							p∈P aths(x,y)

Figure 3.2: Cycle-free paths from G M B connecting Beyonce to Euphoria Denition 6 (Distance between two nodes). The distance between two nodes x and y is

•

  If P is a fuzzy graph pattern and C is a fuzzy condition then (P filter C) is a fuzzy graph pattern. A fuzzy condition is a logical combination of fuzzy terms dened by:

if {?x, ?y} ⊆ V and c ∈ (U ∪ L), then bound(?x), ?x θ c and ?x θ ?y are fuzzy conditions, where θ is a fuzzy or crisp comparator, if ?x ∈ V and F term is a fuzzy term then, ?x is F term is a fuzzy condition, if C 1 and C 2 are fuzzy conditions then (¬C 1 ) and (C 1 C 2 ) (where is a fuzzy connective) are fuzzy conditions.

  1 , o 1 , ..., s n , p n , o n ) ⊆ G be a path of G.The statement p satises exp with a satisfaction degree of sat exp (p) is dened as follows, according to the form of exp (in the following, f , f 1 and f 2 are fuzzy regular

	expressions):

  Finally, the result of the query of Example 43 (Listing 3.2 on page 71) over G M B is the singleton {Shakira} which is m(?art1) in the mapping {?art1 → Shakira, ?alb → Buttery, ?r → 4}, i.e., the only mapping of P rec_low G M B having a

	satisfaction degree greater or equal to 0.4.
		?Art1	(f riend + ) distance is short .creator	?Alb	rating	?r
				recommends				low
			Figure 3.7: Graphical representation of pattern P rec_low
	g 1 :	EnriqueI	friend(0.4)	JustinT	creator	Justied	rating	6
				recommends(0.6)			0.33
	g 2 :	Shakira	friend(0.7)	MariahC	creator	Buttery	rating	4
				recommends(0.8)				0.66

Table 4 .

 4

1: Characteristics of monotonous fuzzy quantiers

  Listing 4.5: Query R at derived from R mostAlbums Then, we evaluate the SPARQL query R f latBoolean given in Listing4.6, derived from the FURQL nonquantied query R f lat of Listing4.5.

	1 select ?art1 ?alb µB µA where {
	2	?art1 recommends ?alb . ?alb date ?date .
	3	filter ( ?date > 2010.0 )
	4	optional {
	5	?art1 friend ?art2 . ?art2 creator ?alb .
	6	?alb rating ?rating . ?art2 age ?age .
	1 select ?art1 ?alb µB µA where {
	2	?art1 recommends ?alb . ?alb date ?date .
	3	filter (?date is recent)
	4	optional {
	5	?art1 friend ?art2 . ?art2 creator ?alb .
	6	?alb rating ?rating . ?art2 age ?age .
	7	filter (?rating is high && ?age is young) } }

  . . ≥ c n . Example 54 In order to calculate µ(Shakira) from R at , let us consider B (resp. A) the set of satisfaction degrees corresponding to condition B

	(resp. A ) of element Shakira as follows B ={ 0.1/Euphoria, 0.2/Butterfly,
	0.3/Justified} and A= { 0.07/Euphoria, 0/Butterfly, 0.4/Justified}. We
	have d = 0.6 and:
	S Euphoria =	0.1 0.6	= 0.17, S Buttery =	0.1 + 0.2 0.6	= 0.5, and
	S Justied =	0.1 + 0.2 + 0.3 0.6	= 1.

  RDF data is inspired by Musicbrainz 4 linked data (which is originally crisp), and for representing fuzzy information, we used the reication mechanism that makes it possible to attach fuzzy degrees to triples, as discussed earlier in

	Subsection 5.1.1
	Table 5.1: Fuzzy RDF datasets
	Dataset	Size	Reied Triples
	DB 1	11796 triples	47185 triples
	DB 2	65994 triples	263977 triples
	DB 3	112558 triples	450393 triples
	DB 4	175416 triples	701665 triples
	A java script have been developed to create random fuzzy RDF data of dierent sizes.

Table 5 .

 5

		2: Dierent types of FURQL queries
	Type	crisp query	Fuzzy Condition	Fuzzy Structural
	Edge query

Table 5 .

 5 3: Set of fuzzy quantied queries with crisp conditions

	Query	P B	P A	Conditions
	Q1 crisp	simple	simple	crisp
	Q2 crisp complex simple	crisp
	Q3 crisp	simple	complex	crisp

Table 5 .

 5 4: Set of fuzzy quantied queries with fuzzy conditions

	Query	P B	P A	Conditions
	Q1 fuzzy	simple	simple	fuzzy
	Q2 fuzzy complex simple	fuzzy
	Q3 fuzzy	simple	complex	fuzzy
	Q4 fuzzy complex complex	fuzzy

Table 5 .

 5

		Average		(0.59, 94.53, 4.89)		(0.50, 94.86, 4.63)		(0.12, 94.78, 5.10)			(0.14, 99.38, 0.47)
	5: Experimental results summarization	DB2 DB3 DB4		(0.52, 93.34, 6.15) (0.51, 93.70, 5.79) (0.2, 94.40, 5.33)		(0.49, 93.76, 5.75) (0.32, 94.29, 5.40) (0.23, 94.50, 5.27)		(0.42, 92.76, 6,82) (0.15, 95.42, 4.43) (0,12, 94.78, 5.10)			(0.01, 99.78, 0.21) (0.00, 99.95, 0.04) (0.00, 99.96, 0.04)
		DB1	Nonquantied queries	(1.04, 96.66, 2.30) Nonquantied edge	queries	(0.97, 96.92, 2.12) Nonquantied star	queries	(0.87, 95.40, 3.73) Nonquantied path	queries	Quantied queries	(0.55, 97.85, 1.60) Quantied queries	with crisp conditions	Quantied queries	with fuzzy conditions

  . Among the existing systems, let us mention

	IJIS16	dans	IJIS16_p	Susan author_of	Maria c o n t r ib u t o r
	IJIS10 where: Mai 2016} {volume: 30, IJIS10_p author_of d a n s	{volume: 25, where: Avril 2010} {titre: An ..., pages: 81-98} Basil dans	IJIS10_p1 {title: About ..., pages: 365-385} a u t h o r _ o f a u t h o r _ o f Claudio contributor
	{titre: A ...,pages: 287-325}
	AllegroGraph [allegrograph, 2017], InniteGraph [innitegraph, 2017], Neo4j [Neo4j, 2017]
	and Sparksee [sparksee, 2017]. Dierent models of graph databases have been proposed in the

Figure 6.1: An Attributed graph inspired from DBLP literature (see

  .2) Clearly Length(p) ≥ n (it is equal to n if ρ is Boolean, i.e., if G is a nonfuzzy graph). We can then dene the distance between two nodes x and y in G as

	Distance(x, y) =	min

all paths p f rom x to y

  This query contains a list of define clauses for the fuzzy quantiers and the fuzzy terms declarations, a match clause for fuzzy graph pattern selection, a having clause for the fuzzy quantied statement denition, and a return clause for specifying which elements should be returned in the resultset. B(res, x) denotes the fuzzy graph pattern involving the nodes res and x and expressing the (possibly fuzzy) conditions inB. B(res, x) takes the form of a fuzzy graph pattern expressed à la Cypher by P B where C B (see Section 6.1.4). A(x) denotes the fuzzy graph pattern involving the node x and expressing the (possibly fuzzy) conditions inA. A(x) takes the form of a fuzzy graph pattern expressed à la Cypher by P A where C A (see

	3.
	1 define... in
	2 match B(res, x)
	3 with res having Q(x) are A(x)
	4 return res
	Listing 6.3: Syntax of a fuzzy quantied query
	Section 6.1.4).

Table 6 . 1

 61

		: Fuzzy graph datasets
	Dataset	Size
	DB 1	700 nodes & 1447 edges
	DB 2	2100 nodes & 4545 edges
	DB 3	3500 nodes & 7571 edges
	DB 4	4900 nodes & 10494 edges

http://franz.com/agraph/allegrograph/

https://musicbrainz.org/

http://www.w3.org/TR/rdf-syntax-grammar/

http://www.w3.org/2001/sw/RDFCore/ntriples/

http://www.w3.org/DesignIssues/Notation3

http://www.w3.org/TR/turtle/

http://www.franz.com/agraph/allegrograph/

http://jena.apache.org/

http://jena.apache.org/

1.2. SPARQL: Crisp Querying of RDF data

1.3. Fuzzy Set Theory

2.1. Preference Queries on RDF Data

Considering paths containing a cycle would not change the result of the following expressions (3.1) and (3.3).

Hereafter, the define clauses are omitted for the sake of simplicity.

https://www-shaman.irisa.fr/surf/

https://jena.apache.org

https://vaadin.com/home

https://musicbrainz.org/

http://www.informatik.uni-trier.de/~ley/db/

http://www.informatik.uni-trier.de/~ley/db/

Hereafter, the define clauses are omitted for the sake of simplicity.

The general syntactic form of a fuzzy quantied query of the type Q B X are A in the FURQL language is given in Listing 4. 1. define ... select ?res where { B(?res,?x) group by ?res having Q(?x) are ( A(?x) ) } Listing 4.1: Syntax of a FURQL quantied query R

The define clause allows to dene the fuzzy terms and the fuzzy quantier (denoted here by Q). Fuzzy quantiers are declared in the same way as fuzzy terms (see Subsection 3.2.1 of Chapter 3). The select clause species which variables ?res should be returned in the result set. The group by clause contains the variables (here ?res) that should be partitioned.

Expression B(?res,?x) (in the where clause) denotes the fuzzy graph pattern, dened in the FURQL language (see Denition 9 on page 69), involving the variables ?res and ?x and expressing the (possibly fuzzy) conditions in B and expression A(?x) (in the having clause) denotes the fuzzy graph pattern involving the variable ?x that appears in A.

Example 51 [Fuzzy Quantied Query in FURQL] The query, denoted by R mostAlbums , that aims to retrieve every artist (?art1) such that most of the recent albums (?alb) that he/she recommends are highly rated and have been created by a young friend (?art2) of his/hers may be expressed in FURQL as follows:

1 defineqrelativeasc most as (0.3,0.8), defineasc high as (2,5) 2 definedesc young as (25,40), defineasc recent as (2010,2015) 3 select ?art1 where { 4

?art1 recommends ?alb . ?alb date ?date . where the defineqrelativeasc clause denes the fuzzy relative increasing quantier most of Figure 4.3.(c), the defineasc clauses dene the (increasing) membership functions associated with the fuzzy terms high and recent of Figure 4.3.(a) and (b), and the definedesc clause denes the (decreasing) membership function associated with the fuzzy term young of Figure 4.3.(d). In this query, ?art1 corresponds to ?res of Listing 4.2, ?alb corresponds to ?x of Listing 4.2, lines 4 to 5 correspond to B(?res,?x) of Listing 4.2 and lines 8 to 10 correspond to A(?x) of Listing 4.2.

Implementation of FURQL

In this section, we discuss implementation issues related to the FURQL query language. Two aspects have to be considered: i) the storage of fuzzy RDF graphs (see Subsection 5.1.1), and ii) the evaluation of FURQL queries with and without fuzzy quantied statements (see Subsection 5.1.2).

Storage of Fuzzy RDF Graphs

In this thesis we deal with fuzzy RDF graph, for which we need to attach fuzzy degrees to some edges in the RDF graph. Example 55 The fuzzy RDF triple ( Shakira, friends, MariahC , 0.7) states that Shakira, friends, MariahC is satised to the degree 0.7, which could be interpreted as Shakira is a close friend of MariahC.

The representation of this fuzzy RDF triple using reication is given in Listing 5.1. The satisfaction degree 0.7 is given by the statement in Line 5.

A possible graphical representation of this reication is depicted in Figure 5.1.

The nodes in dashed lines represent reied nodes with the properties rdf:type, • Star queries (star-shaped queries): consist of three acyclic triple patterns that share the same node (called central node). The central node may appear in dierent positions;

i.e., it can be the subject of the three triples patterns (denoted by star-s3 ), the object of three triples patterns (denoted by star-o3 ), the subject of a triple patterns and the object of the two others (denoted by star-s1-o2 ), or the subject of two triples patterns and the object of the remaining triple pattern (denoted by star-s2-o1 ).

Again we used four queries of the form star-s2-o1 shown in Figure 5.6.

• Path queries: consist of two or three triple patterns that form a path such that two triples share a variable. We may nd path shaped queries of length two or three. We consider in the following an example of a path shaped query of length three of the form given in Figure 5.7. Query Q 3.4 is a fuzzy structural simple path query containing a fuzzy structural condition that aims to nd every artist who has among his close friends an artist who created an album (cf., Listing 5.13). Its crisp counterpart, denoted by Q 3.3 , aims to nd every artist who has among his friends (with a friendship degree greater than 0.8) an artist who created an album (cf., Listing 5.12).

select ?art1 where { ?art2 creator ?alb. ?alb date ?d . /* reification */ ?X1 subject ?art1. ?X1 predicate friend. ?X1 object ?art2. ?X1 degree ?degree. filter ( ?degree > 0.8 ) } Listing 5.12: Crisp strutural path query Q 3.3 defineasc strong as (0.7, 0.9) select ?alb where { ?art2 creator ?alb. ?alb date ?d. /* structural condition */ ?art1 (friend | ST is strong) ?art2 .} Listing 5.13: Fuzzy structural path query Q 3.4 We evaluated separately each type of queries over the dierent sizes of database given in Table 5.1 on page 103. The results of these queries are depicted in Figure 5.8. Figure 5.8.(a) Although these experimental results are preliminary observations, they appear very encouraging since they show that our approach does not entail any important overhead cost. 5.2.3 The main objective of these experiments is to assess the cost of each stage involved in the evaluation of fuzzy quantied queries and to show that the extra cost due to the introduction of fuzzy quantied statements remains limited/acceptable.

Fuzzy quantied query involving crisp conditions

In the rst experiment, we processed four fuzzy quantied queries with crisp conditions (of the type Q B X are A) by changing each time the nature of the patterns corresponding to conditions B and A from simple to complex ones. These queries are summarized in Table 5. 3.

A complex pattern diers from a simple one by the number of its statements. Here, a complex pattern is composed of nine triple patterns at most, while a simple pattern has 6.1.3 Fuzzy Graph Databases We are interested in fuzzy graph databases where nodes and edges can carry data (e.g., keyvalue pairs in attributed graphs). So, we consider an extension of the notion of a fuzzy graph :

the fuzzy data graph as dened in [Pivert et al., 2014a].

Denition 14 (Fuzzy data graph). Let E be a set of labels. A fuzzy data graph G is a quadruple (V, R, κ, ζ), where V is a nite set of nodes (each node n is identied by n.id), R = e∈E {ρ e : V × V → [0, 1]} is a set of labeled fuzzy edges between nodes of V , and κ (resp. ζ) is a function assigning a (possibly structured) value to nodes (resp. edges) of G.

In the following, a graph database is meant to be a fuzzy data graph. The following example illustrates this notion.

Example 58 [Fuzzy data graph] Figure 6.2 is an example of a fuzzy data graph, inspired from DBLP 2 with some fuzzy edges (with a degree in brackets), and crisp ones (degree equal to 1).

In this example, the degree associated with A -contributor-> B is the proportion of journal papers co-written by A and B, over the total number of journal papers written by B. The degree associated with J -domain -> D is the extent to which the journal J belongs to the research domain D.

Nodes are assumed to be typed. If n is a node of V , then T ype(n) denotes its type. In Figure 6.2, the nodes IJWS12, IJAR14, IJIS16, IJIS10 and IJUFK15 are of type journal, the nodes IJWS12-p, IJAR14-p, IJIS16-p, IJIS10-p, IJIS10-p1 and IJUFK15-p of type paper, and the nodes Andreas, Peter, Maria, Claudio, Michel, Bazil and Susan are of type author, the nodes named Database are of type domain and the other nodes are of type impact_factor. For nodes of type journal, paper, author and domain, a property, called name, contains the identier of the node and for nodes of type impact_factor, a property, called value, contains the value of the node. In Figure 6.2, the value of the property name or value for a node appears inside the node. 6. 1.4 The FUDGE Query Language FUDGE, based on the algebra described in [Pivert et al., 2015], is an extension of the Cypher language [START_REF] Cypher | Cypher[END_REF] propose any formal language for expressing such queries.

A rst attempt to extend Cypher with fuzzy quantied queries in the context of a regular (crisp) graph database is described in [Castelltort and[START_REF] Castelltort | [END_REF][START_REF] Castelltort | [END_REF]. In [START_REF] Castelltort | Fuzzy queries over NoSQL graph databases: Perspectives for extending the Cypher language[END_REF], the authors take as an example a graph database representing hotels and their customers and consider the following fuzzy quantied query: In this query, a corresponds to res, p corresponds to x, lines 3 and 4 correspond to B and lines 6 to 8 correspond to A.

According to the general syntax introduced in Listing 6.3, the variable a instantiates res and the variable p instantiates x. 6.3.2 where µ q denotes the membership degree of the predicate q and ρ e (x, y) denotes the weight of the edge (x, y).

Let us consider Q derived (a) the set of answers of the query Q derived for a given author a. The set Q derived (a) provides a list of papers with their respective satisfaction degrees. This result set is of the form Then, with µ most (x) = x, we get µ Q (S IJAR14 ) = 0.35 and µ Q (S IJIS16 ) = 1.

Therefore, the weights of the OWA operator are:

The implication values are: Lastly, the nal result of the query Q mostAuthors evaluated on DB, given by Formula 6.7, is:

84, µ(Michel) = 0.7, µ(Maria) = 0.61}.

About Query Processing

For the implementation of these quantied queries, we updated the SUGAR software described in [Pivert et al., 2014a[START_REF] Pivert | SUGAR: A graph database fuzzy querying system[END_REF], which is a software add-on layer that implements the FUDGE language over the Neo4j graph DBMS. This software eciently evaluates FUDGE queries that contain fuzzy preferences, but its initial version did not support fuzzy quantied statements.

The SUGAR software basically consists of two modules, which implement the Compiling and Final result calculation stages dened in Section 6. 3.2. These modules interact with a Neo4j engine, which implements the Crisp implementation stage dened in Section 6.3.2.

1. In a pre-processing step, the Query compiler module produces

• the query-dependent functions that allow us to compute µ B , µ A and µ, for each returned answer, according to the chosen interpretation, and,

• the (crisp) Cypher query Q derivedBoolean , which is then sent to the Neo4j engine for retrieving the information needed to calculate µ B and µ A .

edges; and regular simple paths, which allow some node and edge restrictions (e.g., regular expressions).

• Pattern matching query: graph pattern matching consists in nding all subgraphs of a data graph that are isomorphic to a graph pattern.

During our experiments, we considered four queries with various forms of condition A.

• The rst query Q 1 (Listing 6.8), where A is an adjacency pattern, aims to nd the authors such that most of the recent papers of which they are main authors, have been published in a journal.

Sample of Queries

The following listing is an example of a derived nonfuzzy query. • Q 4crisp : A fuzzy quantied query with complex pattern in B and complex pattern in A, involving crisp conditions (see Listing A.5), defineqrasc most AS (0,1) defineasc strong AS (0. ?art2 <uri:creator> ?alb2 . ?alb2 <uri:rating> ?rating2 . filter ( ?rating2 is high && ?age2 is young ) )

Listing A.7: A fuzzy quantied query Q 2f uzzy • Q 3f uzzy : A fuzzy quantied query with simple pattern in B and complex pattern in A, involving fuzzy conditions (see Listing A.8), defineqrasc most AS (0,1) defineasc recent AS (2014AS ( ,2016) ) definedesc young AS (25,32) defineasc high AS (3,6) defineasc high AS (2,5) select ?art1 where { ?art1 <uri:recommends> ?alb2 . ?alb2 <uri:date> ?date2 . filter ( ?date2 is recent )} group by ?art1 having most(?alb2) are ( ?art1 ( <uri:friend> | ST IS strong ) ?art2 . ?art2 <uri:age> ?age2 . ?art2 <uri:creator> ?alb2 . ?alb2 <uri:rating> ?rating2 . ?art2 <uri:rating> ?r2 . ?art2 <uri:memberOf> ?m2 . ?art2 <uri:gender> ?g2 . ?art2 <uri:type> ?t21 . ?alb2 <uri:type> ?t22 . filter ( ?rating2 is high && ?age2 is young ) )

Listing A.8: A fuzzy quantied query Q 3f uzzy

• Q 4f uzzy : A fuzzy quantied query with complex pattern in B and complex pattern in A, involving fuzzy conditions (see Listing A.9).

defineqrasc most AS (0,1) defineasc recent AS (2014AS ( ,2016) ) definedesc young AS (25,32) defineasc high AS (3,6) defineasc high AS (2,5) select ?art1 where { ?art1 (recommends | ST is strong) ?alb2 . ?alb2 <uri:date> ?date2 . ?art1 <uri:rating> ?r1 . ?art1 <uri:memberOf> ?m1 . ?art1 <uri:gender> ?g1 . ?art1 <uri:age> ?age1. ?art1 <uri:type> ?t11. filter ( ?date2 is recent )} group by ?art1 having most(?alb2) are ( ?art1 ( <uri:friend> | ST IS strong ) ?art2 . ?art2 <uri:age> ?age2 . ?art2 <uri:creator> ?alb2 . ?alb2 <uri:rating> ?rating2 . ?art2 <uri:rating> ?r2 . ?art2 <uri:memberOf> ?m2 . ?art2 <uri:gender> ?g2 . ?art2 <uri:type> ?t21 . ?alb2 <uri:type> ?t22 . filter ( ?rating2 is high && ?age2 is young ) )

Listing A.9: A fuzzy quantied query Q 4f uzzy