3. We provide algorithms for our solutions to these two problems. In particular, since RDF graphs may be large, we provide algorithms that allow computing lggs of small-to-huge general RDF graphs (i.e., that fit either in memory, in data management systems or in MapReduce clusters) w.r.t. any set of entailment rules from the RDF standard. Our algorithms for RDF graphs have been Organization This thesis is organized as follows. In Chapter 1, we introduce the RDF data model and its SPARQL query language. Then, we study the problem of computing an lgg of RDF graphs in Chapter 2, and of BGPQs in Chapter 3. In Chapter 4, we present algorithms for the two aforementioned problems and we report on the experiments we conducted to evaluate our technical contributions in Chapter 5. We present related works in Chapter 6. Finally, we conclude and draw some perspectives in Chapter 7.

1. This may seem counter-intuitive at first glance, because RDF graph saturation builds on simple entailment between RDF graph, which is NP-complete. The polynomial complexity follows from the fact that the set of entailment rules from the RDF standard is fixed, hence the size (number of triples) in the bodies of these rules is bounded by some constant.

1. generalizes the merge operator for RDF graphs. It corresponds to the union of the input BGPQ bodies after renaming their non-answer variables with fresh ones.

1. From the definition of a cover graph G of the RDF graphs G1 and G2 (Definition 1), the homomorphisms φ1 and φ2 defined as if bt 1 t 3 (resp. bt 2 t 4 ) is a G blank node then the homomorphisms φ1(bt 1 t 3 ) = t1 and φ2(bt 1 t 3 ) = t3 (resp. φ1(bt 2 t 4 ) = t2 and φ2(bt 2 t 4 ) = t4), are clearly such that G1 |= φ 1 G and G2 |= φ 2 G hold. Figure D.13 -DBPEDIA extracted ontology O (13).

Table des matières

Liste of algorithms

First of all I would like to express my sincere gratitude to my thesis director François GOASDOU É and my co-supervisor Hélène JAUDOIN for all that they brought me on a professional and personal level, it was very pleasant to work in this team.

I also want to thank the president of the jury members Farouk TOUMANI, and I thank Marie Christine ROUSSET and Jean-Marc PETIT for agreeing to be the referees of this thesis.

I am thankful for all members of the Shaman team and the Expression team for their kindness, warm hospitality and encouragement, and I would like to thank all the people who have contributed from near or far to carrying out this research.

I would like to thank Bretagne region and Lannion agglomeration for funding this thesis.

Finally I thank my parents and my sister Yasmine for their enthusiasm and encouragement throughout my thesis, I especially thank my mother for making long trips to support me and attend my defense. I also thank my husband Anass for his presence, his enthusiasm and his support during my moments of doubt, and my daughter Lara who was the third contribution of this thesis and a real booster for my success.

Introduction

La recherche des points communs entre des descriptions de données ou des connaissances est un problème de raisonnement fondamental en Machine Learning qui a été formalisé par G. Plotkin dans les années 70s sous la forme du calcul du plus petit généralisant (least general generalization, noté lgg) de ces descriptions. Dans les années 90, ce problème a également été étudié dans le domaine de la représentation des connaissances où le lgg a été rebaptisé plus petit subsumer commun (least common subsumer). Il a plus particulièrement été investigué dans les logiques des descriptions et les graphes conceptuels. Récemment, ce problème a été exploré dans le domaine du web sémantique, notamment dans le modèle de données "graphe" Resource Description Framework (RDF) et dans son langage de requête associé SPARQL, qui sont deux standards du web sémantique du W3C.

Le lgg peut être utilisé dans de nombreuses applications importantes. Par exemple, en optimisation de requêtes, un lgg des requêtes reçues caractérise le plus grand ensemble de leurs points communs dont le traitement peut être factorisé. Dans le cadre d'un entrepôt des données, un lgg permet d'identifier les fragments de requêtes qui reviennent souvent et qui peuvent être matérialisés sous forme de vues. En recommandation, et plus particulièrement dans les réseaux sociaux, un lgg d'un ensemble des descriptions d'utilisateurs (profiles) peut aider à recommander les utilisateurs entre eux, à créer des groupes ou à former une communauté, si leurs centres d'intérêts sont assez proches. Par ailleurs, un lgg d'un ensemble de requêtes émises par les mêmes utilisateurs permet de les recommander entre eux si ce qu'ils cherchent est assez proche.En classification, un lgg d'un ensemble des données peut être utilisé pour les classer en considérant leurs informations communes. Il peut aussi être utilisé pour identifier la structure commune de certaines organisations (criminelles par exemple). Enfin, un lgg d'un ensemble de requêtes permet de les regrouper selon points communs et ainsi de recommander des recherches similaires ou complémentaires.

L'objectif de cette thèse est de revisiter le problème du calcul du lgg entre des descriptions du web sémantique, quand celles-ci sont des graphes RDF et des requêtes SPARQL, et pour lesquelles l'état de l'art ne fournit que des solutions structurellement et sémantiquement limitées.

Préliminaires

Les contributions de cette thèse reposent sur RDF et le fragment conjonctif de SPARQL, Basic Graph Pattern Queries (BGPQ). Un graphe RDF est un ensemble de triplets de la forme (s, p, o) où s est le sujet qui a la propriété p et la valeur de cette propriété est l'objet o. Un triplet appartient à l'ensemble (U ∪ B) × U × (U ∪ L ∪ B), avec U est l'ensemble des identifiants uniformes de ressource (URIs), B est l'ensemble des ressources anonymes qui identifient les valeurs manquantes du graphe RDF et L est l'ensemble des littéraux qui correspondent aux constantes dans un graphe RDF. Un triplet est une assertion de classe (relation unaire) ou de propriété (relation binaire). Un graphe RDF peut être enrichi avec des contraintes ontologiques entre les classes et leur propriétés. Une contrainte ontologique est un triplet qui contient une assertion RDF Schema (RDFS). Ces contraintes ontologiques permettent de dériver des triplets implicites. Ils sont rendus explicites en appliquant d'une manière exhaustive en chaînage avant sur un ensemble de règles d'implication R fournies par le standard RDF. En ajoutant tous les triplets dérivés à notre graphe initial, nous obtenons un graphe stable et unique nommé la saturation du graphes RDF qui matérialise la sémantique du graphe RDF. Le standard RDF définit une relation de généralisation/spécialisation entre graphes RDF nommée l'implication simple entre les graphes RDF (|=) qui permet de comparer les graphes en se basant sur leurs triplets explicites uniquement. Il a également défini une autre relation de généralisation/spécialisation entre graphes RDF nommée l'implication standard entre graphes RDF (|= R ) qui permet de comparer les graphes selon leurs triplets explicites et implicites. Dans la suite, nous allons utilisé l'implication standard pour calculer les lggs. Le langage de requête associé à RDF est SPARQL. Une requête SPARQL est composée de deux parties, la tête qui contient les variables de réponse et le corps qui est composé d'un ensemble de triplets. Un triplet du corps d'une requête SPARQL généralise un triplet du graphe RDF en autorisant les variables dans le sujet, la propriété et l'objet. Ainsi un triplet d'une requête SPARQL appartient à (V ∪U ∪B)×(V ∪U)×(V ∪U ∪L∪B) avec V est l'ensemble des variables. Dans ce travail, nous considérons les ressources anonymes dans une requêtes SPARQL comme des variables. Il existe deux notions importantes qui caractérisent comment un graphe RDF contribue à une requête : l'implication d'une requête q qui indique si oui ou non un graphe G RDF fournit une réponse à la requête (G |= R q) et répondre à une requête q qui identifie l'ensemble des réponses d'une requête dans un graphe (q(G)). Comme pour les graphes RDF, il existe une relation de généralisation/spécialisation entre les requêtes SPARQL nommée l'implication standard entre les requêtes (|= R ).

Trouver les points communs entre des graphes RDF

Le plus petit généralisant commun (lgg) entre des descriptions est la plus spécifique des descriptions qui généralise toutes les autres descriptions, selon une relation d'implication entre des descriptions. Dans le contexte de RDF, les descriptions sont les graphes RDF et nous utilisons l'implication entre les graphes RDF comme relation de généralisation/spécialisation. Nous avons prouvé que le lgg de graphes existe toujours et qu'il est sémantiquement unique par rapport à l'implication. Le calcul du lgg de n graphes est équivalent au calcul d'une séquence de n-1 lgg de deux graphes. Sans perte de généralité, nous avons étudié une technique pour calculer le lgg de deux graphes G 1 et G 2 . Pour cela, nous avons défini la notion de graphe couvrant qui est formé de l'ensemble des anti-unifications de chaque paire de triplets pris dans G 1 et G 2 respectivement. L'anti-unification désigne la transposition aux triplets RDF, de la notion d'anti-unification de deux atomes du premier ordre défini par Plotkin et qui construit un atome qui est leur plus petite généralisation. Cette notion est duale à celle de l'unification qui représente la spécialisation la plus générale entre deux atomes.Le lgg de deux graphes est le graphe couvrant de leur saturation. Nous avons prouvé que le temps du calcul d'un lgg ainsi que sa taille sont au pire quadratique par rapport à la taille des graphes RDF (saturées) en entrée.

Trouver les points communs entre les requêtes SPARQL

Pour définir le lgg entre des requêtes, nous utilisons les requêtes Basic Graph Pattern Queries (BGPQ), le fragment conjonctive de SPARQL, comme descriptions et l'implication standard entre BGPQs comme relation de spécialisation/généralisation. Dans ce cas, la définition du lgg a un intérêt pratique limité comme le montre le scénario qui suit. Soit deux requêtes : q 1 ← (x, τ, Conf P aper), (x, hasContactAuthor, y 1 ) qui cherche les articles de conférence qui ont un auteur de contact, et q 2 ← (x, τ, JourP aper), (x, hasAuthor, y) qui cherche les articles de journaux qui ont un auteur. Leur lgg en considérant l'implication standard est la requête qui cherche les ressources qui ont un auteur : q lgg (x) ← (x, τ, y). Ce lgg est très éloigné sémantiquement des requêtes initiales q 1 et q 2 . Néanmoins, en considérant un ensemble de contraintes ontologiques externes, comme (i) avoir un auteur de contact est plus spécifique qu'avoir un auteur, (ii) les articles de conférence (resp. articles de journal) sont des articles, nous pouvons définir un lgg plus spécifique qui cherche les articles qui ont un auteur : q lgg (x) ← (x, τ, P ublication), (x, hasAuthor, y). Afin de trouver cette requête, nous avons défini une nouvelle relation d'implication entre requête BGPQs qui tient compte d'un ensemble de règles R et d'un ensemble de contraintes ontologiques O, notée |= R,O . Cette relation repose sur une relation nouvellement introduite de saturation de requête selon R et O. Celle-ci permet de compléter le corps d'une requête avec tous les triplets qui peuvent être dérivés depuis le corps de la requête uniquement et à partir de O. Nous avons montré que la requête et sa saturation sont équivalentes d'un point de vue des deux notions ; l'implication de requête et de réponses à une requête, et que l'opération d'implication selon R et O entre requêtes est bien fondée par rapport à ces deux notions. Nous avons proposé une nouvelle définition du lgg fondée sur l'implication de requête selon un ensemble de règles R et un ensemble de contraintes ontologique O.Nous avons prouvé que le lgg d'un ensemble de requêtes BGPQs peut ne pas exister, et que s'il existe, il est unique par rapport à la relation d'implication entre BGPQs.

Algorithmes et expérimentations

Pour calculer le lgg entre des graphes RDF, nous avons proposé trois algorithmes. Le premier permet de construire des lggs de graphes, resp. de requêtes qui tiennent en mémoire. Pour les graphes qui ne tiennent pas en mémoire, nous proposons un deuxième algorithme qui s'appuie sur les systèmes de gestion de bases de données. Enfin pour les graphes de très grande taille, nous avons défini un troisième algorithme qui fait appel au modèle de programmation MapReduce pour calculer le lgg. Nous avons également proposé un algorithme qui permet de construire des lggs de requêtes BGPQs. Ces algorithmes exploitent un algorithme qui calcule la plus petite antiunification entre deux triplets de graphes ou de requêtes BGPQs.

Les expérimentations que nous avons menées avaient pour objectif de valider nos approches et de montrer la valeur ajoutée qu'apportent les contraintes ontologies dans le calcul du lgg de graphes RDF et de requêtes BGPQs. Pour cela, nous avons extrait un ensemble de graphes issues des données réelles de DBPedia, et défini des requêtes sur DBPedia et sur des données synthétiques LUBM représentant des universités.

Nous avons défini deux métriques pour mesurer le gain en précision apporté par l'utilisation de l'implication standard entre les graphes (|= R ) et respectivement, par l'utilisation de l'implication entre requêtes BPGQs en présence de contraintes ontologiques (|= R,O ) plutôt que l'implication simple (|=) -utilisée dans l'état de l'art -dans le calcul des lggs de graphes et de requêtes respectivement.

Nous avons calculé ces différents lggs et les gains de précision respectifs. Nos résultats confirment nos hypothèses : l'utilisation de l'implication standard entre les graphes RDF (|= R ) et de l'implication entre BGPSs en considérant un ensemble de contraintes ontologiques (|= R,O ) produit des lggs plus précis. En effet, l'exploitation des contraintes ontologiques permet de trouver les généralisants communs entre les classes et les propriétés qui sont utilisés à la place des classes et des propriétés des graphes et des requêtes initiaux. En utilisant l'implication simple, ces classes et ces propriétés ne peuvent être remplacées par des noeuds blancs dans les graphes et par des variables dans le cas des requêtes, ce qui engendre des très (trop) grandes généralisations, comme nos expérimentations le montrent.

État de l'art et conclusion

L'objectif de cette thèse est de revisiter le problème de la recherche des points communs entre des graphes RDF et des requêtes SPARQL, les deux standards populaires du web sémantique, et cela en calculant leur plus petit généralisant communs. Ce problème est très connu dans le domaine du Machine Learning [Plotkin, 1970, Plotkin, 1971, Buntine, 1988, Nienhuys-Cheng and de Wolf, 1996, Nienhuys-Cheng and de Wolf, 1997] et a été étudié dans d'autres domaines, comme les logiques des descriptions [Küsters, 2001, Baader et al., 2007, Zarrieß and Turhan, 2013], les graphes conceptuels [START_REF] Chein | Graph-based Knowledge Representation -Computational Foundations of Conceptual Graphs[END_REF] et récemment dans RDF [START_REF] Colucci | Common subsumbers in RDF[END_REF], Colucci et al., 2016] et SPARQL [Lehmann andBühmann, 2011, Bühmann et al., 2016]). Les contributions de cette thèse reposent sur des idées développées en ILP pour calculer le lgg des clauses du premier ordre [Plotkin, 1970, Plotkin, 1971, Buntine, 1988, Nienhuys-Cheng and de Wolf, 1996, Nienhuys-Cheng and de Wolf, 1997], dans le cadre de RDF et son langage de requête SPARQL. Les contributions de cette thèse améliorent l'état de l'art dans le domaine du web sémantique car nous considérons les graphes RDF et les BGPQs dans leur généralité, i.e., nous n'imposons aucune restriction ni structurelle ni sémantique sur les graphes et les requêtes en entrée.

Dans cette thèse nous donnons la définition, les caractéristiques et le calcul d'un lgg de graphes RDF et de requêtes BGPQs (fragment conjonctif de SPARQL).

Introduction

Finding the commonalities between descriptions of data or knowledge is a foundational reasoning problem of Machine Learning, which was formalized by G. Plotkin in the early 70's as computing a least general generalization (lgg) of such descriptions [Plotkin, 1971, Plotkin, 1970].

This seminal work had been the basis of many research efforts in Machine Learning, in particular in its Inductive Logic Programming (ILP) subfield [Buntine, 1988, Nienhuys-Cheng and de Wolf, 1996, Nienhuys-Cheng and de Wolf, 1997].

Since the early 90's, this problem has also attracted the attention of the Knowledge Representation field, where the notion of least general generalization was rebaptized least common subsumers [START_REF] Cohen | Computing least common subsumers in description logics[END_REF]. In particular, it has been studied in Description Logics, e.g., [START_REF] Cohen | Computing least common subsumers in description logics[END_REF], Baader et al., 1999, Baader et al., 2007, Küsters, 2001, Zarrieß and Turhan, 2013], and in Conceptual Graphs [START_REF] Chein | Graph-based Knowledge Representation -Computational Foundations of Conceptual Graphs[END_REF].

Also, more recently, this problem has started being investigated in the Semantic Web field, for the Resource Description Framework (RDF) [START_REF] Colucci | Defining and computing least common subsumers in RDF[END_REF], El Hassad et al., 2017a] and its associated SPARQL query language [START_REF] Lehmann | Autosparql: Let users query your knowledge base[END_REF], Bühmann et al., 2016, El Hassad et al., 2017e, El Hassad et al., 2017b], the two prominent and now wellestablished Semantic Web standards by W3C.

Motivations. In this thesis, we revisit the problem of computing an lgg of input descriptions in the Semantic Web setting (contributions to be outlined shortly), when these descriptions are either RDF graphs (i.e., datasets) or SPARQL queries, for which the literature provides limited solutions (limitations to be pointed out shortly).

Solutions to this problem can be applied to a variety of useful important applications, ranging from query optimization to exploration and recommendation in RDF data management systems or in SPARQL endpoints, as exemplified next.

In Query optimization, an lgg of incoming queries characterizes the largest set of their commonalities whose processing may be shared in multi-query optimization [START_REF] Le | Scalable multi-query optimization for SPARQL[END_REF].

Similarly, lggs of subsets of a query workload correspond to candidate views that may be recommended for materialization in view selection [START_REF] Goasdoué | View selection in semantic web databases[END_REF], a typical optimization for data warehouses [START_REF] Colazzo | RDF analytics: lenses over semantic graphs[END_REF], and among which can be selected those that allow rewrit-13 ing (partially or totally) the workload while minimizing a combination of rewriting processing, view storage and view maintenance costs.

In Recommendation, in particular in a social context, lggs of sets of user descriptions (i.e., profiles) may help recommending users other users, or to form a community, when they share enough interests [START_REF] Cheng | Explass: Exploring associations between entities via top-k ontological patterns and facets[END_REF], Lohmann et al., 2010]. Also, lggs of sets of queries issued by distinct users may help recommending users to each other, if what they ask for is enough related [START_REF] Huang | Kbenabled query recommendation for long-tail queries[END_REF].

In Exploration, lggs of datasets may be used to classify/categorize them w.r.t. their common information [START_REF] Grimnes | Instance based clustering of semantic web resources[END_REF], to identify common social graph patterns between organizations [START_REF] Jin | Discovering frequent topological structures from graph datasets[END_REF], Perner, 2017] (e.g., criminal ones), or to help identifying new potential links between datasets in the Linked Data Cloud [START_REF] Sherif | Wombat -A generalization approach for automatic link discovery[END_REF]. Clustering user queries found in system logs, based on their lggs, may help classifying the queries and identifying the kind of data each category accesses [START_REF] Chuang | Towards automatic generation of query taxonomy: A hierarchical query clustering approach[END_REF]. Further, finding the relevant user query cluster for an incoming query may help recommending similar and complementary searches [START_REF] Huang | Kbenabled query recommendation for long-tail queries[END_REF], Heckel et al., 2017].

Contributions. The contribution of this thesis to the problem of computing a least general generalizations in the RDF and in SPARQL queries are as follows:

1. We define and study the problem of computing an lgg of RDF graphs in the entire RDF standard: we do not restrict RDF graphs in any way, i.e., neither their structure nor their semantics defined upon RDF entailment (inference). The recent work [START_REF] Colucci | Common subsumbers in RDF[END_REF], Colucci et al., 2016] brings a limited solution to the problem. It allows finding the commonalities between single entities extracted from RDF graphs (e.g., users in a social network), ignoring RDF entailment. In contrast, we further aim at considering the problem in all its generality, i.e., finding the commonalities between general RDF graphs, hence modeling multiple interrelated entities (e.g., social networks of users), faithfully w.r.t. their standard semantics. This work has been published in [El Hassad et al., 2017a] and presented to the ILP community [START_REF] Hassad | Learning commonalities in RDF[END_REF].

2. We define and study the problem of computing an lgg of general SPARQL conjunctive queries, a.k.a. Basic Graph Pattern Queries (BGPQs), while the literature only considers unary tree-shaped conjunctive queries (UTCQ) [START_REF] Lehmann | Autosparql: Let users query your knowledge base[END_REF]. Further, when available, we devise how to use background knowledge, formalized as ontological constraints modeling the application domain, in order to compute much more precise lggs. This work has been published in [El Hassad et al., 2017e, El Hassad et al., 2017c] and presented to the french database community [START_REF] Hassad | Learning commonalities in SPARQL[END_REF].

published in [El Hassad et al., 2017a].

4. We report on experiments using DBpedia, a real dataset, which demonstrate the added-value of considering standard entailment when learning lggs between RDF graphs. We also report on experiments using synthetic data (LUBM) and real data (DBpedia), which show to which extent lggs of BGPQs are much more precise when standard entailment endowed with background knowledge is used. To this aim, we define metrics to compute the gain in precision using RDF entailment yields.

Chapter 1

Preliminaries Contents

Introduction

In this chapter we recall the basics of the prominent W3C's Semantic Web standards: the RDF data model in Section 1.2, and its associated SPARQL query language in Section 1.3.

Resource Description Framework (RDF) 1.2.1 RDF graphs

The RDF data model allows specifying RDF graphs. An RDF graph is a set of triples of the form (s, p, o). A triple states that its subject s has the property p, the value of which is the object o. Triples are built using three pairwise disjoint sets: a set U of uniform resources identifiers (URIs), a set L of literals (constants), and a set B of blank nodes allowing to support incomplete information. Blank nodes are identifiers for missing values (unknown URIs or literals). Well-formed triples, as per the RDF Notations. We use s, p, o in triples as placeholders. We note Val(G) the set of values occurring in an RDF graph G, i.e., the URIs, literals and blank nodes; we note Bl(G) the set of blank nodes occurring in G. A blank node is written b possibly with a subscript, and a literal is a string between quotes. For instance, the triples (b, hasTitle, "LGG in RDF") and (b, hasContactAuthor, b 1 ) state that something (b) entitled "LGG in RDF" has somebody (b 1 ) as contact author.

(p, ← d , o), (s 1 , p, o 1 ) → (s 1 , τ, o) rdfs3 (p, → r , o), (s 1 , p, o 1 ) → (o 1 , τ, o) rdfs5 (p 1 , sp , p 2 ), (p 2 , sp , p 3 ) → (p 1 , sp , p 3 ) rdfs7 (p 1 , sp , p 2 ), (s, p 1 , o) → (s, p 2 , o) rdfs9 (s, sc , o), (s 1 , τ, s) → (s 1 , τ, o) rdfs11 (s, sc , o), (o, sc , o 1 ) → (s, sc , o 1 ) ext1 (p, ← d , o), (o, sc , o 1 ) → (p, ← d , o 1 ) ext2 (p, → r , o), (o, sc , o 1 ) → (p, → r , o 1 ) ext3 (p, sp , p 1 ), (p 1 , ← d , o) → (p, ← d , o) ext4 (p, sp , p 1 ), (p 1 , → r , o) → (p, → r , o)
A triple models an assertion, either for a class (unary relation) or for a property (binary relation). Table 1.1 (top) shows the use of triples to state such assertions. The RDF standard [W3C-RDF, 2014] provides built-in classes and properties, as URIs within the rdf and rdfs pre-defined namespaces, e.g., rdf:type which can be used to state that the above b is a conference paper with the triple (b, rdf:type, ConfPaper).

Adding ontological knowledge to RDF graphs

An essential feature of RDF is the possibility to enhance the descriptions in RDF graphs by declaring ontological constraints between the classes and properties they use. This is achieved with RDF Schema (RDFS) statements, which are triples using particular built-in properties. Table 1.1 (bottom) lists the allowed constraints and the triples to state them; domain and range denote respectively the first and second attribute of every property. For example, the triple (ConfPaper, rdfs:subClassOf, Publication) states that conference papers are publications, the triple (hasContactAuthor, rdfs:subPropertyOf, hasAuthor) states that having a contact author is having an author, the triple (hasAuthor, rdfs:domain, Publication) states that only publications may have authors, and the triple (hasAuthor, rdfs:range, Researcher) states that only researchers may be authors of something. Notations. For conciseness, we use the following shorthands for built-in properties: τ for rdf:type, sc for rdfs:subClassOf, sp for rdfs:subPropertyOf, ← d for rdfs:domain, and → r for rdfs:range.

Deriving the implicit triples of an RDF graph

The implicit triples of an RDF graph are derived with the help of entailment rules from the RDF standard [W3C- [START_REF]RDF 1.1 semantics[END_REF]].

An entailment rule r is of the form body(r) → head(r), where body(r) is an RDF graph called the body of r and head(r) is also an RDF graph, called the head of r; it states that the RDF graph body(r) entails the RDF graph head(r). Table 1.2 shows the strict subset of these rules that we will use to illustrate important notions as well as our contributions in the next chapters. Crucially, our contributions hold for the entire set of entailment rules of the RDF standard, and any subset of thereof. The rules in Table 1.2 concern the derivation of implicit triples using ontological constraints (i.e., RDFS statements). They encode the propagation of assertions through constraints (rdfs2, rdfs3, rdfs7, rdfs9), the transitivity of the sp and sc constraints (rdfs5, rdfs11), the complementation of domains or ranges through sc (ext1, ext2), and the inheritance of domains and of ranges through sp (ext3, ext4).

An entailment rule r can be applied to an RDF graph G to identify some G implicit triple(s) if G simply entails body(r), i.e., G contains some particular case(s) of body(r). Simple entailment between RDF graphs is the generalization/specialization relation from the RDF standard [W3C- [START_REF]RDF 1.1 semantics[END_REF] When an RDF graph G simply entails the body of an entailment rule r due to some homomorphism φ, in which case we say that G triggers (a.k.a. fires) r due to φ, this rule allows deriving that G entails [head(r)] φ , because [body(r)] φ ⊆ G holds and clearly [body(r)] φ → [head(r)] φ is a particular case of the rule r.

Notation. From now, we denote by G |= φ G the fact that the RDF graph G is simply entailed by the RDF graph G due to the homomorphism φ.

Given a set R of entailment rules from the RDF standard, a.k.a. entailment regime, the saturation (or closure) of an RDF graph G w.r.t. R is the RDF graph G ∞ obtained by adding to G all the implicit triples that follow from G and R. The saturation G ∞ materializes the semantics of G w.r.t. R. It corresponds to the fixpoint reached by repeatedly applying the rules in R to G in a forward-chaining fashion, while adding to G the new triples they derive. More formally, given an RDF graph G and a set R of entailment rules, the saturation of G with R is the fixpoint G ∞ recursively defined as:

-

G 0 = G -G n = G n-1 ∪ {[head(r)] φ | r ∈ R ∧ G n-1 |= φ body(r) ∧ G 0≤i<n-1 |= φ body(r)},
such that if a blank node b in head(r) has no image through φ, then φ(b) is a fresh blank node. Further, for any RDF graph and set of entailment rules from the RDF standard, the following holds [W3C-RDFS, 2014]: Property 1. The saturation is finite, unique (up to blank node renaming), and can be computed in polynomial time 1 .

The interested reader may find, for particular sets of entailment rules from the RDF standard, the upper bounds of worst-case saturation time (polynomials of low degrees) and of saturation size in e.g., [ter Horst, 2005, Goasdoué et al., 2013].

The saturation of the RDF graph G shown in Figure 1.1 corresponds to the RDF graph G ∞ in which all the G implicit triples (dashed edges) are made explicit (solid edges). It is worth noting how, starting from G, applying RDF entailment rules mechanizes the construction of G ∞ . For instance, recall the reasoning sketched above for deriving the triple (b 1 , τ, Researcher). This is automated by the following sequence of applications of RDF entailment rules: (hasContactAuthor, sp , hasAuthor) and (b, hasContactAuthor, b 1 ) trigger rdfs7 that adds (b, hasAuthor, b 1 ) to the RDF graph. In turn, this new triple together with (hasAuthor, → r , Researcher) triggers rdfs3 that adds (b 1 , τ, Researcher).

Comparing RDF graphs.

The RDF standard defines a generalization/specialization relationship between two RDF graphs, called entailment between graphs, that goes beyond simple entailment by taking into account the explicit and the implicit triples of the compared RDF graphs. Roughly speaking, an RDF graph G is more specific than another RDF graph G , or equivalently G is more general than G, whenever there is a graph homomorphism from G to the saturation of G, i.e., the complete set of triples that G models. Formally, given any subset R of RDF entailment rules, an RDF graph G entails an RDF graph [G ] φ is the RDF graph obtained from G by replacing every blank node b by its image φ(b). Further, deciding entailment between two RDF graphs is NP-complete [W3C-RDFS, 2014]; this follows from (i) the fact that the saturation of G can be computed in polynomial time and (ii) from the NP-completeness of deciding whether there exists a homomorphism between two graphs. 1.2. In particular, G |= R G holds for the homomorphism φ such that: φ(b) = b and φ(b 2 ) = "LGG in SPARQL". By contrast, when R is empty, this is not the case (i.e., G |= R G ), as the dashed edges in G are not materialized by saturation, hence the G triple (b, τ, Publication) cannot have an image in G through some homomorphism.

G , denoted G |= R G , iff there exists an homomorphism φ from Bl(G ) to Val(G ∞ ) such that [G ] φ ⊆ G ∞ , where
Notations. When relevant to the discussion, we designate by G |= φ R G the fact that the entailment G |= R G holds due to the graph homomorphism φ.

Importantly, from the definition of entailment between two RDF graphs [W3C-RDF, 2014], the following holds: Property 2. Given two RDF graphs G, G and a set R of RDF entailment rules,

1. G and G ∞ are equivalent (G |= R G ∞ and G ∞ |= R G hold), noted G ≡ R G ∞ , 2. G |= R G holds iff G ∞ |= G holds.
From a practical viewpoint, Property 2 points out that checking G |= R G can be done in two steps: a reasoning step that computes the saturation G ∞ of G, followed by a standard graph homomorphism step that checks if G ∞ |= G holds.

Finally, we remark that when entailment rules are not considered, i.e., R = ∅, the relations of simple entailment and of (general) entailment coincide.

SPARQL conjunctive queries 1.3.1 Basic graph pattern queries

The well-established conjunctive fragment of SPARQL queries, a.k.a. Basic Graph Pattern queries (BGPQs), is the counterpart of the select-project-join queries for databases; it is the most widely used subset of SPARQL queries in real-world applications [START_REF] Picalausa | A structural approach to indexing triples[END_REF].

A Basic Graph Pattern (BGP) is a set of triple patterns, or simply triples by a slight abuse of language. They generalize RDF triples by allowing the use of variables. Given a set V of variables, pairwise disjoint with U, L and B, triple patterns belong to:

(V ∪ U ∪ B) × (V ∪ U) × (V ∪ U ∪ L ∪ B).
Notations. We adopt the usual conjunctive query notation q(x) ← t 1 , . . . , t α , where {t 1 , . . . , t α } is a BGP. The head of q, noted head(q), is q(x), and the body of q, noted body(q), is the BGP {t 1 , . . . , t α }, the cardinality of which is the size of q. The query head variables x are called answer variables, and form a subset of the variables occurring in t 1 , . . . , t α ; for Boolean queries, x is empty. The cardinality of x is the arity of q. We use x and y in queries, possibly with subscripts, for answer and non-answer variables respectively. Finally, we note VarBl(q) the set of variables and blank nodes occurring in the query q, and Val(q) the set of all its values, i.e., URIs, blank nodes, literals and variables.

Entailing and answering queries

Two related important notions characterize how an RDF graph contributes to a query.

The weaker notion, called query entailment, indicates whether or not an RDF graph holds some answer(s) to a query. It generalizes entailment between RDF graphs, to account for the presence of variables in the query body, for establishing whether an RDF graph entails a query, i.e., whether the query embeds in that graph. Formally, given a BGPQ q, an RDF graph G and a set R of RDF entailment rules, G entails q, noted G |= R q, iff G |= R body(q) holds, i.e., there exists a homomorphism φ from VarBl(q) to Val(G ∞ ) such that [body(q)] φ ⊆ G ∞ . Further, similarly to entailment between RDF graphs (and for the same reasons), deciding query entailment is NP-complete [W3C-SPARQL, 2008].

The RDF graph G in Figure 1.1 entails the query q(x 1 , x 2 ) ← (x 1 , τ, x 2 ) asking for all the resources and their classes for instance, because of the homomorphism φ such that φ(x 1 ) = b and φ(x 2 ) = ConfPaper. Observe that this entailment holds for any subset of RDF entailment rules, since the above homomorphism φ already holds for R = ∅, i.e., considering only the explicit triples in Figure 1.1.

Notations. Similarly to entailment between RDF graphs, we denote by G |= φ R q that the entailment G |= R q holds due to the homomorphism φ.

The stronger notion characterizing how an RDF graph contributes to a query, called query answering, identifies all the query answers that this graph holds. Formally, given a BGPQ q with set x of answer variables, the answer set of q against G is

q(G) = {(x) φ | G |= φ R body(q)}
where (x) φ is the tuple of G ∞ values obtained by replacing every answer variable x i ∈ x by its image φ(x i ). In case of a Boolean query, q is false iff q(G) = ∅; otherwise q is true and q(G) = { } where denotes the empty tuple. Further, because query entailment is NP-complete, clearly, identifying an answer of a BGPQ against an RDF graph is NP-complete [W3C-SPARQL, 2008].

The answer set to the above query q(x 1 , x 2 ) ← (x 1 , τ, x 2 ) against the RDF graph G in rules in Table 1.2, i.e., considering the explicit and implicit triples in Figure 1.1. Importantly, from the definition of answer set of a SPARQL query against an RDF graph [W3C-SPARQL, 2008], the following holds: Property 3. Given an RDF graph G, a set R of entailment rules and a BGPQ q,

1. G |= R q holds iff G ∞ |= q holds, 2. q(G) = q(G ∞ ) holds.
From a practical viewpoint, Property 3 points out that query entailment G |= R q, respectively query answering q(G), can be done in two steps: a reasoning step that computes the saturation G ∞ of G, followed by a standard graph homomorphism step that checks if G ∞ |= φ q holds for some homomorphism φ, respectively enumerates all the homomorphisms φ for which G ∞ |= φ q holds.

Comparing queries

Similarly to RDF graphs, queries can be compared through the generalization/specialization relationship of entailment between queries.

Let q, q be BGPQs with the same arity, whose heads are q(x) and q (x ), and R the set of RDF entailment rules under consideration. q entails q , denoted q |= R q , iff body(q) |= φ R body(q ) with (x ) φ = x holds. Here, body(q) |= φ R body(q ) is the adaptation of the above-mentioned entailment relationships between RDF graphs to the fact that the query bodies may feature variables, i.e., φ is a homomorphism from VarBl(body(q )) to Val(body(q) ∞ ) such that [body(q )] φ ⊆ body(q) ∞ ; the saturation of a BGP body, here body(q) ∞ , is the obvious generalization of RDF graph saturation that treats variables as blank nodes, since they both equivalently model unknown information within BGPs [W3C-SPARQL, 2008]. Similarly to entailment between RDF graphs (and for the same reasons), deciding entailment between two BGPQs is NP-complete [W3C-RDFS, 2014, W3C-SPARQL, 2008].

For instance, the query q 1 (x) ← (x, τ, ConfPaper), (x, hasContactAuthor, y) entails the query q 2 (x) ← (x, τ, y) with φ(x) = x, φ(y) = ConfPaper and any set of entailment rules.

We remark that entailment between queries, query entailment and query answering (obviously) relate as follows:

Property 4. Given an RDF graph G, a set R of entailment rules and two BGPQs q, q such that q |= R q , 1. if G |= R q holds then G |= R q holds, 2. q(G) ⊆ q (G) holds.

Finally, query entailment, query answering and entailment between queries treat blank nodes in queries exactly as non-answer variables [W3C- SPARQL, 2008]. Hence, hereafter, we assume without loss of generality that queries do not use blank nodes.

Conclusion

In this chapter, we recalled the RDF and SPARQL notions on which the main contributions of this PhD thesis build: the definition and computation of the largest set of commonalities between RDF graphs or between BGPQs, which we present in the next two chapters.

Preliminaries

Introduction

In this chapter, we present the first main contribution of this thesis: we define and solve the problem of learning the commonalities between RDF graphs, formalized as a least general generalization (lgg for short) of these RDF graphs w.r.t. the standard relation of entailment between RDF graphs.

In Section 2.2, we define and study the lgg of input RDF graphs, as well as how to compute it and the resources needed for that in Section 2.3. Such an lgg is an RDF graph that represents the largest set of commonalities of the input RDF graphs. Crucially, and in constrast with the state of the art (see Chapter 6), our approach is faithful to the entire W3C standard: we do not restrict the structure of the input/output RDF graphs in any way, nor their semantics, which is based on RDF entailment.

Defining the lgg of RDF graphs

A least general generalization of n descriptions d 1 , . . . , d n is a most specific description d generalizing every d 1≤i≤n for some generalization/specialization relation between descriptions [Plotkin, 1970, Plotkin, 1971]. In RDF, we use RDF graphs as descriptions and entailment between RDF graphs as relation for generalization/specialization: Definition 1 (lgg of RDF graphs). Let G 1 , . . . , G n be RDF graphs and R a set of RDF entailment rules.

-

A generalization of G 1 , . . . , G n is an RDF graph G g such that G i |= R G g holds for 1 ≤ i ≤ n. -A least general generalization (lgg) of G 1 , . . . , G n is a generalization G lgg of G 1 , . . . , G n such that for any other generalization G g of G 1 , . . . , G n , G lgg |= R G g holds.
Importantly, in the RDF setting, the following holds:

Theorem 1. An lgg of RDF graphs always exists; it is unique up to entailment.

Proof. An lgg of RDF graphs always exists, since we can always construct a (possibly empty) RDF graph that is the lgg of RDF graphs, in particular the cover graph of RDF graphs devised in Section 2.3.

Also, an lgg of RDF graphs is unique up to entailment (since G lgg |= R G g holds for any G g in Definition 1). Indeed, if it were that RDF graphs have multiple lggs incomparable w.r.t. entailment, say lgg 1 , . . . , lgg m , their merge1 lgg 1 • • • lgg m would be a single strictly more specific lgg, a contradiction. graphs G 1 andG 2 , as well as their minimal lgg G lgg (with lowest number of triples), when we consider the RDF entailment rules shown in Table 1.2. G 1 describes a conference paper i 1 with title "Disaggregations in Databases" and author Serge Abiteboul, who is a researcher; also conference papers are publications. G 2 describes a journal paper i 2 with title "Computing with First-Order Logic", contact author Serge Abiteboul and author Victor Vianu, who are researchers; moreover, journal papers are publications and having a contact author is having an author. G lgg states that their common information comprises the existence of a resource (b i 1 i 2 ) having some type (b C(onf)P(aper)J(our)P(aper) ), which is a particular case of publication, with some title (b D(iD)C(wFOL) ) and author Serge Abiteboul, who is a researcher.

Though unique up to entailment (i.e., semantically unique), an lgg may have many syntactical forms due to redundant triples.

Such triples can be either explicit ones that could have been left implicit if the set of RDF entailment rules at hand allows deriving them from the remaining triples (e.g., materializing the only G lgg implicit triple in Figure 2.1 would make it redundant if we consider the entailment rules in Table 1.2) or triples generalizing others without needing RDF entailment rules, i.e., w.r.t. |= ∅ (e.g., adding the triple (b, hasAuthor, b ) to G lgg in Figure 2.1 would be redundant w.r.t. (b i 1 i 2 , hasAuthor, SA)). Also, an lgg may have several minimal syntactical variants obtained by pruning out redundant triples. For example, think of a minimal lgg comprising the triples (A, sc , B), (B, sc , A) and (b, τ, A), i.e., there exists an instance of the class A, which is equivalent to class B. Clearly, an equivalent and minimal variant of this lgg is the RDF graph comprising the triples (A, sc , B), (B, sc , A) and (b, τ, B). Importantly, the above discussion is not specific to lggs of RDF graphs, since any RDF graph may feature redundancy. The detection and elimination of RDF graph redundancy has been studied in the literature, e.g., [Meier, 2008, Pichler et al., 2010, Pichler et al., 2013]. Hence we focus in this work on the following learning problem:

Problem 1. Given the RDF graphs G 1 , . . . , G n and a set R of RDF entailment rules, we want to compute some lgg of G 1 , . . . , G n .
The proposition below states that an lgg of n RDF graphs, with n ≥ 3, can be inductively defined (hence computed) as a sequence of n -1 lggs of two RDF graphs.

Finding Commonalities between RDF graphs

Intuitively, assuming that k≥2 is an operator computing an lgg of k input RDF graphs, the next proposition establishes that:

[basis] 3 (G 1 , G 2 , G 3 ) ≡ R 2 ( 2 (G 1 , G 2 ), G 3 ) [induction] n (G 1 , . . . , G n ) ≡ R 2 ( n-1 (G 1 , . . . , G n-1 ), G n ) ≡ R 2 ( 2 (• • • 2 ( 2 (G 1 , G 2 ), G 3 ) • • • , G n-1 ), G n ) Proposition 1. Let G 1 , . . . , G n≥3 be n RDF graphs and R a set of RDF entailment rules. G lgg is an lgg of G 1 , . . . , G n iff G lgg is an lgg of an lgg of G 1 , . . . , G n-1 and G n .
Proof. The proof relies on the next lemma.

Lemma 1. Let G 1 , . . . , G n be RDF graphs and R a set of RDF entailment rules. If G 1 lgg is an lgg of G 1 , . . . , G k<n and G 2 lgg is an lgg of G 1 , . . . , G n , then G 1 lgg |= R G 2 lgg holds.
Let us show that the above lemma holds. Suppose that G 1 lgg is an lgg of G 1 , . . . , G k<n , i.e., by Definition 1

: (i) G 1≤i≤k |= R G 1 lgg holds and (ii) for any RDF graph G such that G 1≤i≤k |= R G holds, G 1 lgg |= R G holds. Suppose also that G 2 lgg is an lgg of G 1 , . . . , G n , i.e., by Definition 1: (i) G 1≤i≤n |= R G 2 lgg holds and (ii) for any RDF graph G such that G 1≤i≤n |= R G holds, G 2 lgg |= R G holds. Clearly, G 2 lgg is a possible value for G above, because G 1≤i≤n |= R G 2 lgg implies G 1≤i≤k<n |= R G 2 lgg , hence G 1 lgg |= R G 2 lgg holds. ¡
Now, let us prove Proposition 1 using the above lemma.

(⇒) Assume that G lgg is an lgg of G 1 , . . . , G n and let us show that it is also an lgg of some lgg of G 1 , . . . , G n-1 and G n . By Definition 1, because G lgg is an lgg of G 1 , . . . , G n , we have: (i) G 1≤i≤n |= R G lgg holds and (ii) for any RDF graph G such that

G 1≤i≤n |= R G holds, G lgg |= R G holds.
Let G lgg be some lgg of G 1 , . . . , G n-1 . From (i) and the above lemma, (*)

G lgg |= R G lgg and G n |= R G lgg holds.
Moreover, for any RDF graph G, if it were that

G lgg |= R G and G n |= R G and G lgg |= R G, then G 1≤i≤n |= R G would hold and contradict the fact that G lgg is an lgg of G 1 , . . . , G n . Therefore, (**) for any RDF graph G, if G lgg |= R G and G n |= R G holds, then G lgg |= R G holds.
From Definition 1, (*) and (**) we get that

G lgg is an lgg of an lgg of G 1 , . . . , G n-1 and G n . (⇐) Assume that G lgg is an lgg of an lgg G of G 1 , . . . , G n-1 and G n , and let us show that it is also an lgg of G 1 , . . . , G n . By Definition 1, (i) G |= R G lgg and G n |= R G lgg hold, hence G 1≤i≤n-1 |= R G lgg and G n |= R G lgg hold, i.e., (*') G 1≤i≤n |= R G lgg holds. Moreover, (ii) for any RDF graph G such that G |= R G and G n |= R G hold, G lgg |= R G holds. By Definition 1, G 1≤i≤n-1 |= R G holds, therefore we get: (**') for any RDF graph G such that G 1≤i≤n |= R G holds, G lgg |= R G holds.
From Definition 1, (*') and (**') we get that G lgg is an lgg of G 1 , . . . , G n .

Based on the above result, without loss of generality, we focus in the next section on the particular instance of Problem 1 for n = 2.

Computing an lgg of RDF graphs

We first devise the cover graph of two RDF graphs G 1 and G 2 (to be defined shortly, Definition 3 below), which is central to our technique for computing an lgg of G 1 and G 2 . We indeed show (Theorem 2) that this particular RDF graph corresponds to an lgg of G 1 and G 2 when considering their explicit triples only, i.e., ignoring RDF entailment rules. Then, we show the main result of this section (Theorem 3): an lgg of G 1 and G 2 , for any set R of RDF entailment rules, is the cover graph of their saturations w.r.t. R. We also provide the worst-case size of cover graph-based lggs, as well as the worst-case time to compute them.

Our notion of cover graph builds on that of least general anti-unification of two first order atoms [Plotkin, 1970, Plotkin, 1971, Robinson and Voronkov, 2001], which defines an atom that is their least general generalization. This is the dual to the well-known notion of most general unifier of two first order atoms [Robinson, 1965, Robinson andVoronkov, 2001], which defines an atom that is their most general specialization. We transfer it to the RDF setting as follows:

Definition 2 (Anti-unification of triples). Let ς be an injective generalization function from (U ∪ L ∪ B) × (U ∪ L ∪ B) to U ∪ L ∪ B that maps (i) any pair of same input URI or literal value to itself, i.e., ς(v, v) = v, and (ii) any other pair of values (URIs, blank nodes, literals and mix thereof ) to a blank node.

The anti-unification of the two triples (t 1 , p, t 2 ) and (t 3 , p, t 4 ) is the triple (ς(t 1 , t 3 ), p, ς(t 2 , t 4 )).

Observe that anti-unification is only defined for triples with same property URI. Indeed, anti-unifying triples of the form (t 1 , p, t 2 ) and (t 3 , p , t 4 ), with p = p , would lead to a non-well-formed triples of the form (t 5 , b, t 6 ) (recall that property values must be URIs in RDF graphs), where b is the blank node required to generalize the distinct values p and p .

With the notion of anti-unification of triples in place, we are now able to define our central notion of cover graph: Definition 3 (Cover graph). The cover graph G of two RDF graphs G 1 and G 2 is the RDF graph, which may be empty, such that for every property p in both G 1 and G 2 :

(t 1 , p, t 2 ) ∈ G 1 and (t 3 , p, t 4 ) ∈ G 2 iff (t 5 , p, t 6 ) ∈ G with t 5 = t 1 if t 1 = t 3 and t 1 ∈ U ∪ L, else t 5 is the blank node b t 1 t 3 , and, similarly t 6 = t 2 if t 2 = t 4 and t 2 ∈ U ∪ L, else t 6 is the blank node b t 2 t 4 .
It is worth noting that the definition of cover graph does not manipulate explicitly the injective generalization function ς. It is left implicitly in our way of defining the values of t 5 and t 6 : t 5 = t 1 if t 1 = t 3 and t 1 ∈ U ∪ L corresponds to the particular case ς(v, v) = v for v a URI or literal, while otherwise t 5 is the blank node b t 1 t 3 corresponds to all the other cases, i.e., t 5 = b t 1 t 3 = ς(t 1 , t 3 ); this is the same for t 6 .

Intuitively, the cover graph is a generalization of G 1 and G 2 (first item in Definition 1) as each of its triple (t 5 , p, t 6) is a least general anti-unification of a triple (t 1 , p, t 2 ) from G 1 and a triple (t 3 , p, t 4 ) from G 2 . Further, the cover graph is an lgg for the explicit triples in G 1 and those in G 2 (second item in Definition 1) since we capture their common structures by consistently naming, across all the anti-unifications begetting G, the blank nodes used to generalize pairs of distinct subject values or of object values: each time the distinct values t from G 1 and t from G 2 are generalized by a blank node while anti-unifying two triples, it is always by the same blank node b tt in G. This way, we establish joins between G triples, which reflect the common join structure on t within G 1 and on t within G 2 .

For example in Figure 2.1, the G 1 explicit triples (i 1 , τ, ConfPaper), (ConfPaper, sc , Publication), (i 1 , title, "DiD") and the G 2 explicit triples (i 2 , τ, JourPaper), (JourPaper, sc , Publication), (i 2 , title, "CwFOL"), lead to the triples (b The second results from anti-unifying again ConfPaper and JourPaper into b CPJP , and, Publication and Publication into Publication (as a constant is its own least general generalization). Finally, the third results from anti-unifying again i 1 and i 2 into b i 1 i 2 , and, "DiD" and "CwFOL" into b DC . By reusing consistently the same blank node name b i 1 i 2 for each anti-unification of the constants i 1 and i 2 (resp. b CPJP for ConfPaper and JourPaper)), the cover graph triples join on b i 1 i 2 (resp. b CPJP ) in order to reflect that, in G 1 and in G 2 , there exists a particular case of publication (i 1 in G 1 and i 2 in G 2 ) with some title ("DiD" in G 1 and "CwFOL" in G 2 ).

i 1 i 2 , τ, b CPJP ), (b CPJP , sc , Publication), (b i 1 i 2 , title, b DC ) in the cover graph of G 1 and G 2 shown in
The next theorem formalizes the above discussion by stating that the cover graph of two RDF graphs is an lgg of them, just in case of an empty set of RDF entailment rules.

Theorem 2. The cover graph G of the RDF graphs G 1 and G 2 is an lgg of them for the empty set R of RDF entailment rules (i.e., R = ∅).

Proof. The proof can be directly derived from that of the more general Theorem 3 (see below), noting that in the particular case of Theorem

2, R = ∅ holds, hence G ∞ 1 = G 1 and G ∞ 2 = G 2 holds.
We provide below worst-case bounds for the time to compute a cover graph and for its size; these bounds directly follows from the definition of a cover graph (Definition 3)

b i 1 i 2 b SAVV SA Researcher τ b i 1 SA b CPR b i 1 VV b DC b CPJP Publication title τ hasAuthor τ sc τ τ b SAi 2 b RJP τ b i 1 i 2 b SAVV b PR SA Researcher τ b i 1 SA b CPR b i 1 VV b DC b PJP b CPP b CPJP Publication title τ τ τ τ hasAuthor hasAuthor τ sc τ τ τ τ b RP b SAi 2 b RJP τ τ Figure 2.2 -
, i.e., G 1 |= R G and that G 2 |= R G. If G is empty, its trivial. Otherwise, consider the RDF graph G obtained from G by replacing every blank node b v 1 v 2 by the value v 1 . Clearly, G |= R G and, by construction of G, G ⊆ G 1 , i.e., G 1 |= R G. Showing G 2 |= R G is done in a similar way. Hence, G is a generalization of G 1 and G 2 .
Let us show now that G is an lgg of G 1 and G 2 . Let G lgg be any lgg of G 1 and G 2 . To prove our claim, we need to show that

G |= R G lgg holds. If G lgg is empty, then so is G, since G lgg |= R G (G lgg is an lgg of G 1 and G 2 ,
and G only a generalization of them). Otherwise, since G lgg is an lgg of G 1 and G 2 , there exist two homomorphisms φ 1 and φ 2 from the blank nodes in

G lgg to the values in G ∞ 1 and in G ∞ 2 respectively, such that [G lgg ] φ 1 ⊆ G ∞ 1 and [G lgg ] φ 2 ⊆ G ∞ 2 . Consider the graph G lgg obtained from G lgg by replacing every blank node b by b v 1 v 2 where v 1 = φ 1 (b) and v 2 = φ 2 (b). Clearly, G lgg ≡ R G lgg holds. Let us show that G |= R G lgg holds, i.e.
, there exists a homomorphism φ from the blank nodes in G lgg to the terms in G ∞ such that [G lgg ] φ ⊆ G ∞ . By construction of G, it is easy to see that the above holds when

φ maps b v 1 v 2 either to v 1 if v 1 = v 2 and v 1 ∈ U ∪ L, or to itself otherwise. It therefore follows that G |= R G lgg , hence G |= R G lgg .
As an immediate consequence of the above results, we get the following worst-case bounds for the time to compute a cover graph-based lgg of two RDF graphs G 1 and G 2 , and for its size. Here, we assume given the saturation G ∞ 1 and G ∞ 2 , as the times to compute them and their sizes depend on the RDF entailment rules at hand.

Corollary 1. An lgg of two RDF graphs G 1 and G 2 can be computed in O(|G ∞ 1 |×|G ∞ 2 |) and its size is bounded by |G ∞ 1 | × |G ∞ 2 |.
Remark that computing naively the cover graph-based lgg of n RDF graphs of size M based on Proposition 1 may lead to an lgg of size M n , in the unlikely worst-case where all the triples of all the RDF graphs use the same property URI. However, removing the redundant triples from the intermediate and final cover graph-based lggs limits their size to at most M . 1.2. In contrast to Figure 2.2 (top), which shows an lgg of the same RDF graphs when RDF entailment rules are ignored, we further learn that Serge Abiteboul is an author of some particular publication (i 1 in G 1 and i 2 in G 2 ). Moreover, removing the redundant triples (the gray ones) yields precisely the lgg G lgg of G 1 and G 2 shown in Figure 2.1.

Conclusion

In this chapter, we first defined the notion of an lgg of RDF graphs (Definition 1) faithful to the entire W3C standard, for which we showed (Theorem 1) that there exists a unique equivalent class of lggs of RDF graphs: though syntactically different lggs of some RDF graphs exist, they are all equivalent w.r.t. the standard relation of entailment between RDF graphs. We also showed that the problem (Problem 1) of computing such an lgg of n > 2 RDF graphs can be solved, without loss of generality, if we have a solution to the particular instance of this problem where n = 2 (Proposition 1).

We therefore devised the notion of cover graph of two input RDF graphs (Definition 3), which is an RDF graph, for which we showed that it corresponds (i) to an lgg of the input RDF graphs when no entailment rules are considered (Theorem 2), i.e., when the semantics of RDF graph based on RDF entailment is ignored, and to (ii) an lgg of the input RDF graphs w.r.t. the entailment rules under consideration (Theorem 3), when the input RDF graphs are saturated with these rule before computing their cover graph. Further, we showed (Proposition 2 and Corollary 1) that the time to compute a cover graph, and its size, are at most quadratic in the size of the input (saturated) RDF graphs.

Introduction

In this chapter, we present the second main contribution of this thesis: we define and solve the problem of learning the commonalities between conjunctive SPARQL queries, i.e., BGPQs, formalized as an lgg of these queries w.r.t. a well-founded extension of the standard relation of entailment between BGPQs. Indeed, one may be tempted to adapt to our SPARQL setting the notion of lgg for RDF graphs (Definition 1) by using BGPQs in place of RDF graphs and the off-the-shelf entailment between BGPQs instead of entailment between RDF graphs: Definition 4 (lgg of BGPQs). Let q 1 , . . . , q n be BGPQs with the same arity and R a set of RDF entailment rules.

-A generalization of q 1 , . . . , q n is a BGPQ q g such that q i |= R q g for 1 ≤ i ≤ n.

-A least general generalization of q 1 , . . . , q n is a generalization q lgg of q 1 , . . . , q n such that for any other generalization q g of q 1 , . . . , q n : q lgg |= R q g .

Unfortunately, this straightforward definition is of limited practical interest as the next example shows. Consider the BGPQs q 1 and q 2 in Figure 3.1, which respectively ask for the conference papers having some contact author, and for the journal papers having some author. Clearly, with the RDF entailment rules shown in Table 1.2, an 37

x 1 ConfPaper y 1 τ hasContactAuthor x 2 JourPaper y 2 τ hasAuthor x y τ q 1 (x 1 ) q 2 (x 2 ) q lgg (x)
Figure 3.1 -Sample BGPQs q 1 , q 2 and their minimal lgg q lgg .

Publication hasAuthor Researcher

ConfPaper JourPaper hasContactAuthor

← d → r sp ← d → r sc sc Figure 3.2 -Sample set O of RDFS ontological constraints .
lgg of q 1 and q 2 is the very general BGPQ q lgg (x) ← (x, τ, y) asking for the resources having some type shown in Figure 3.1 (right).

We argue that the value of lggs could be significantly augmented by taking into account some background knowledge formalized as ontological constraints. For example, if we consider the RDFS statements shown in Figure 3.2 that hold in the scientific publication domain, a more precise lgg for the above-mentioned q 1 , q 2 would be q lgg (x) ← (x, τ, Publication), (x, hasAuthor, y), (y, τ, Researcher) asking for the publications having some researcher as author, since (i) having a contact author is having an author, (ii) only publications have authors, (iii) only researchers are authors, and (iv) conference and journal papers are publications. It is worth noting that, while background knowledge is part of an RDF graph when it contains RDFS constraints, background knowledge is not part of a BGPQ even if it contains RDFS constraints: a BGPQ only defines select-project-join search conditions to be matched against an RDF graph.

To define such more precise lggs and state our learning problem in Section 3.3, we start by generalizing the standard specialization/generalization relation of entailment between BGPQs in Section 3.2, in order to allow comparing BGPQs w.r.t. an extra set of RDFS ontological constraints. In particular, this novel relation (i) coincides with the standard one when extra constraints are unavailable and (ii) behaves like the standard one w.r.t. the central reasoning tasks of query entailment and of query answering when extra constraints are available. Finally, we present our solution to the novel learning problem we identified in Section 3.4.

Comparing Queries w.r.t. Ontological Constraints

Our new entailment relation between queries builds on the following notion of saturation of a query, which materializes the semantics of the query in the light of some given background knowledge:

Definition 5 (BGPQ saturation w.r.t. RDFS constraints). Let R be a set of RDF entailment rules, O a set of RDFS statements, and q a BGPQ. The saturation of q w.r.t. O, noted q ∞ O , is the BGPQ with the same answer variables as q and whose body, noted body(q ∞ O ), is the maximal subset of (body(q) ∪ O) ∞ such that for any of its subset S: if O |= R S holds then body(q) |= R S holds.

Observe that this saturation coincides with that of BGPQs (Section 1.3) when the set of RDF constraints O is empty. Also, such a saturation is pertinent just in case the RDF entailment rules under consideration utilize the RDFS constraints, e.g., those in Table 1.2; otherwise the set of constraints is useless.

In essence, the saturation of a BGPQ comprises all the triples in the saturation of its body together with the RDFS constraints, from which are pruned out the triples derived solely from the constraints, i.e., which are not related to what the query is asking for. This corresponds exactly to the non-hatched subset of (body(q) ∪ O) ∞ shown in Figure 3.4: The next theorem establishes that our novel saturation is well-founded w.r.t. the central reasoning tasks of query entailment and query answering, i.e., a BGPQ and its saturation are equivalent w.r.t. the query entailment and query answering viewpoints: Theorem 4. Let R be a set of RDF entailment rules, O a set of RDFS statements, and q a BGPQ whose saturation w.r.t. O is q ∞ O . For any RDF graph G whose set of RDFS statements is O:

body(q ∞ O ) = (body(q) ∪ O) ∞ \ (O ∞ \ body(q) ∞ ).
1. G |= R q holds iff G |= R q ∞ O holds, 2. q(G) = q ∞ O (G) holds. Proof. Let us first show item 1. Showing that G |= R q iff G |= R q ∞ O holds amounts to showing that G ∞ |= q iff G ∞ |= q ∞ O holds (recall Chapter 1). If G ∞ |= φ q ∞
O holds for some homomorphism φ, then G ∞ |= φ q holds also since body(q

) ⊆ body(q ∞ O ). Now, if G ∞ |= q holds then G ∞ |= body(q) ∪ O holds since O ⊆ G, hence G ∞ |= (body(q) ∪ O) ∞ holds (because G ∞ |= body(q) ∪ O holds iff there exists a homomorphism φ such that [body(q) ∪ O] φ ⊆ G ∞ and therefore [body(q) ∪ O] ∞ φ ⊆ G ∞ holds). By definition of the saturation of a BGPQ, body(q ∞ O ) ⊆ (body(q) ∪ O) ∞ , thus G ∞ |= body(q ∞ O ) holds.
Item 2. directly follows from: (i) the fact that, above, item 1. holds for any homomorphism φ and (ii) q and q ∞ O have, by definition, the same answer variables.

Finally, the next theorem states the computational complexity of our novel saturation of a query: Theorem 5. The saturation of a BGQP w.r.t. a set of RDFS constraints can be computed in polynomial time.

Proof. The polynomial time result directly follows from the fact that, in Definition 5, (i) q ∞ O has the same head variables as q (hence these can be computed in linear time) and (ii) the body of q ∞ O can be computed based on the set characterization displayed in Figure 3.4, i.e., as (body(q)∪O) ∞ \(O ∞ \body(q) ∞ ) (hence in polynomial time, since the saturation of BGP/RDF graphs can be computed in polynomial time (Chapter 1)).

With the above notion of saturation in place, we endow entailment between queries with background knowledge as follows:

Definition 6 (Entailment between BGPQs w.r.t. RDFS constraints). Given a set R of RDF entailment rules, a set O of RDFS statements, and two BGPQs q and q with the same arity, q entails q w.r.

t. O, denoted q |= R,O q , iff q ∞ O |= q holds.
Clearly, the above definition coincides with standard RDF entailment between BGPQs when O is empty (recall Section 1.3).

Using the set R of entailment rules in Table 1.2, the above mentioned BGPQ q lgg (x) ← (x, τ, Publication), (x, hasAuthor, y), (y, τ, Researcher) is neither entailed by q 1 nor by q 2 from Figure 3.1, while it is entailed by both of them w.r.t. the set O of constraints displayed in the same Figure, i.e., it is entailed in the standard fashion by their saturations shown in Figure 3

.3: q 1 ∞ O |= φ 1 q holds for φ 1 (x) = x 1 and φ 1 (y) = y 1 , and q 2 ∞ O |= φ 2 q holds for φ 2 (x) = x 2 and φ 2 (y) = y 2 .
Further, the main theorem below states that our novel entailment relation is wellfounded w.r.t. the central reasoning tasks of query entailment and query answering, i.e., when a query is entailed by another w.r.t. some background knowledge, similarly to Property 4 in Section 1.3 where no background is considered, the former generalizes the latter from the query entailment and query answering viewpoints: Theorem 6. Let R be a set of RDF entailment rules, O a set of RDFS statements, and two BGPQs q and q such that q |= R,O q . For any RDF graph G whose set of RDFS statements is O:

1. if G |= R q holds then G |= R q holds, 2. q(G) ⊆ q (G) holds.
Proof. Let us first show item 1.

By Theorem 4, item 1.,

G |= R q holds iff G |= R q ∞ O holds. Consider some φ such that G |= φ R q ∞ O
holds. Also, by Definition 6, consider some φ such that q ∞ O |= φ q . By composing φ and φ into ψ, we get G |= ψ R q , i.e., G |= R q .

Item 2. directly follows from: (i) the fact that, above, item 1. holds for any pair of homomorphisms φ, φ such that G |= φ R q ∞ O and q ∞ O |= φ q hold, and (ii) q and q ∞ O have, by definition, the same answer variables.

Finally, we establish that entailment between queries w.r.t. background knowledge is as hard as standard entailment between queries:

Theorem 7. Deciding entailment between two BGPQs w.r.t. RDFS constraints is NPcomplete.

Proof. The problem is NP-hard because entailment between two BGPQs w.r.t. RDFS constraints collapses to standard entailment between BGPQs, which is NP-complete (recall Section 1.3), when the set of RDFS constraints under consideration is empty.

The problem is in NP since, as stated in Definition 6, q |= R,O q iff q ∞ O |= q , i.e., q |= R,O q can be decided by first computing q ∞ O in polynomial time (Theorem 5) and then using simple entailment between BGPQs, which is NP-complete (recall Section 1.3), to check if q ∞ O |= q holds.

3.3 Learning the lgg of Queries w.r.t. Ontological Contraints

In the light of the preceding results, we revise/generalize Definition 4 as follows:

Definition 7 (lgg of BGPQs w.r.t. RDFS constraints). Let R be a set of RDF entailment rules, O a set of RDFS statements, and q 1 , . . . , q n BGPQs with the same arity.

-A generalization of q 1 , . . . , q n w.r.t. O is a BGPQ q g such that q i |= R,O q g for 1 ≤ i ≤ n. -A least general generalization of q 1 , . . . , q n w.r.t. O is a generalization q lgg of q 1 , . . . , q n w.r.t. O such that for any other generalization q g of q 1 , . . . , q n w.r.t. O:

q lgg |= R,O q g .
By constrast with an lgg of RDF graphs that always exists (Theorem 1), we found:

Theorem 8. An lgg of BGPQs w.r.t. RDFS statements may not exist for some set of RDF entailment rules; when it exists, it is unique up to entailment (|= R,O ).

Proof. It is easy to show that an lgg of BGPQs may not exist. For instance, consider the BGPQs q 1 (x 1 ) ← (x 1 , hasAuthor, y 1 ) asking for the resources having some author, and q 2 (x 2 ) ← (y 2 , hasAuthor, x 2 ) asking for the authors of some resource. Clearly, when the set R of entailment rules is empty or comprises the rules in Table 1.2, no BGPQ can generalize q 1 and q 2 , hence there is no lgg of them. By contrast, if we use the complete set of RDF entailment rules, an lgg of q 1 and q 2 is q lgg (x) ← (x, τ, rdf:Resource), since every RDF value is an instance of the built-in class rdf:Resource.

When an lgg of BGPQs w.r.t. RDFS constraints exists, it is unique up to entailment, i.e., is semantically unique, because q lgg |= R,O q g holds for any q g in Definition 4. If it were that queries have multiple lggs incomparable w.r.t. entailment, say the BGPQs lgg 1 (x), . . . , lgg m (x), the BGPQ defined as q lgg (x) ← body(lgg 1 ) • • • body(lgg m ) 1 would be a single strictly more specific lgg, a contradiction.

Similarly to the case of RDF graphs, though unique up to entailment, there exist many syntactic variants (an infinity actually) of an lgg of BGPQs due to redundant triples, i.e., triples entailed by others within the lgg. For example, think of an lgg q lgg (x) ← (x, τ, A), (x, τ, B), (x, y, z) w.r.t. the set of constraints O = {(A, sc , B), (B, sc , A)}, which asks for resources of types A and B that are somehow related to some resource, and it is known that A and B are equivalent classes.

Clearly, different equivalent and minimal variants (w.r.t. the number of triples) of this lgg are q lgg (x) ← (x, τ, A) and q lgg (x) ← (x, τ, B), since (x, y, z) is entailed by each of the two other triples, and (x, τ, B) is entailed by (x, τ, A) w.r.t. O, and vice versa, because A and B are equivalent.

Again, importantly, redundancy of triples is not specific to lggs of BGPQs w.r.t. RDFS constraints, since obviously any BGPQ may feature redundancy. The detection and elimination of such redundancy have been studied in the literature [Meier, 2008, Pichler et al., 2013], hence we focus in this work on learning some lgg of BGPQs w.r.t. RDFS constraints; learning as minimal as possible lggs is a perspective of this work discussed in Section 7.2.

Based on the above discussion, the learning problem we propose to study is: Problem 2. Given a set R of RDF entailment rules, a set O of RDFS statements, and the BGPQs q 1 , . . . , q n with the same arity, find an lgg of q 1 , . . . , q n w.r.t. O.

The proposition below, which is the counterpart of Proposition 1 that we established for RDF graphs, shows that an lgg of n ≥ 3 BGPQs can be inductively defined, hence computed, as a sequence of n -1 lggs of two BGPQs. That is, assuming that k≥2 is an operator computing an lgg of k input BGPQs, the next proposition establishes that:

[basis] 3 (q 1 , q 2 , q 3 ) ≡ R,O 2 ( 2 (q 1 , q 2 ), q 3 ) [induction] n (q 1 , . . . , q n ) ≡ R,O 2 ( n-1 (q 1 , . . . , q n-1 ), q n ) ≡ R,O 2 ( 2 (• • • 2 ( 2 (q 1 , q 2 ), q 3 ) • • • , q n-1 ), q n ) Proposition 3.
Let q 1 , . . . , q n≥3 be n BGPQs, O a set of RDFS statements and R a set of RDF entailment rules. q lgg is an lgg of q 1 , . . . , q n w.r.t. O iff q lgg is an lgg w.r.t. O of an lgg of q 1 , . . . , q n-1 w.r.t. O and q n .

Proof. The proof relies on the next lemma.

Lemma 2. Let q 1 , . . . , q n be BGPQs, O a set of RDFS statements and R a set of RDF entailment rules. If q 1 lgg is an lgg of q 1 , . . . , q k<n w.r.t. O and q 2 lgg is an lgg of q 1 , . . . , q n w.r.t. O, then q 1 lgg |= R,O q 2 lgg holds. Let us show that the above lemma holds. Suppose that q 1 lgg is an lgg of q 1 , . . . , q k<n w.r.t. O, i.e., by Definition 4: (i) q 1≤i≤k |= R,O q 1 lgg holds and (ii) for any BGPQ q such that q 1≤i≤k |= R,O q holds, q 1 lgg |= R,O q holds. Suppose also that q 2 lgg is an lgg of q 1 , . . . , q n w.r.t. O, i.e., by Definition 4: (i) q 1≤i≤n |= R,O q 2 lgg holds and (ii) for any BGPQ q such that q 1≤i≤n |= R,O q holds, q 2 lgg |= R,O q holds. Clearly, q 2 lgg is a possible value for q above, because q 1≤i≤n |= R,O q 2 lgg implies q 1≤i≤k<n |= R,O q 2 lgg , hence q 1 lgg |= R,O q 2 lgg must hold. ¡

Now, let us prove Proposition 3 using the above lemma.

(⇒) Assume that q lgg is an lgg of q 1 , . . . , q n w.r.t. O and let us show that it is also an lgg w.r.t. O of some lgg of q 1 , . . . , q n-1 and q n w.r.t. O. By Definition 4, because q lgg is an lgg of q 1 , . . . , q n w.r.t. O, we have: (i) q 1≤i≤n |= R,O q lgg holds and (ii) for any BGPQ q such that q 1≤i≤n |= R,O q holds, q lgg |= R,O q holds. Let q lgg be an lgg of q 1 , . . . , q n-1 w.r.t. O. From (i) and the above lemma, (*) q lgg |= R,O q lgg and q n |= R,O q lgg hold. Moreover, for any BGPQ q, if it were that q lgg |= R,O q and q n |= R,O q and q lgg |= R,O q, then q 1≤i≤n |= R,O q would hold and contradict the fact that q lgg is an lgg of q 1 , . . . , q n w.r.t. O. Therefore, (**) for any BGPQ q, if q lgg |= R,O q and q n |= R,O q holds, then q lgg |= R,O q holds.

From Definition 4, (*) and (**) we get that q lgg is an lgg w.r.t. O of an lgg of q 1 , . . . , q n-1 and q n w.r.t. O.

(⇐) Assume that q lgg is an lgg w.r.t. O of an lgg q of q 1 , . . . , q n-1 and q n w.r.t. O, and let us show that it is also an lgg of q 1 , . . . , q n w.r.t. O.

By Definition 4, (i) q |= R,O q lgg and q n |= R,O q lgg hold, hence q 1≤i≤n-1 |= R,O q lgg and q n |= R,O q lgg hold, i.e., (*') q 1≤i≤n |= R,O q lgg holds.

Moreover, (ii) for any BGPQ q such that q |= R,O q and q n |= R,O q hold, q lgg |= R,O q holds. By Definition 4, q 1≤i≤n-1 |= R,O q holds, therefore we get: (**') for any BGPQ q such that q 1≤i≤n |= R,O q holds, q lgg |= R,O q holds.

From Definition 4, (*') and (**') we get that q lgg is an lgg of q 1 , . . . , q n w.r.t. O.

Based on the above result, without loss of generality, we study in the next Section the particular instance of our learning problem for n = 2.

Computing an lgg of Queries w.r.t. ontological constraints

Our solution to the above learning problem (Problem 2) adapts that we devised for RDF graphs to BGPQs. We first define the notion of anti-unification of BGPQ triple patterns (Definition 8), based on which we devise the notion of cover query of two BGPQs (Definition 9). Then, we establish that the cover query of two BGPQs q 1 and q 2 is an lgg of q 1 and q 2 just in case both RDF entailment rules and ontological constraints are ignored (Theorem 9). Further, we show (Theorem 10) that an lgg of q 1 and q 2 as defined in Definition 7, i.e., when RDF entailment rules and ontological constraints are taken into consideration, is the cover query of the saturations of q 1 and of q 2 with the RDF entailment rules and ontological constraints at hand (Definition 5). Importantly, we also show that the existence of such cover queries and lggs coincide.

We also provide the size of these cover query-based lggs (i.e., number of triples), as well as the time to compute them.

We transfer the notion of anti-unification [Plotkin, 1970, Plotkin, 1971, Robinson and Voronkov, 2001] to the SPARQL setting as follows:

Definition 8 (Anti-unification of triple patterns). Let ς be an injective generalization function from (U ∪ L ∪ V) × (U ∪ L ∪ V) to U ∪ L ∪ V that maps (i) any pair of same input URI or literal value to itself, i.e., ς(v, v) = v, and (ii) any other pair of values (URIs, literals, variables and mix thereof ) to a variable.

The anti-unification of the two triples (t 1 , t 2 , t 3 ) and (t 4 , t 5 , t 6 ) is the triple (ς(t 1 , t 4 ), ς(t 2 , t 5 ), ς(t 3 , t 6 )).

Observe that, by contrast with RDF graph triples, there is no restriction on the BGPQ triples that can be anti-unified, as any triples from

(U ∪ L ∪ V) × (U ∪ L ∪ V) × (U ∪ L ∪ V) is well-formed.
We are now able to define our central notion of cover query:

Definition 9 (Cover query). Let q 1 , q 2 be two BGPQs with the same arity n.

If there exists the BGPQ q such that -head(q 1 ) = q(x 1 1 , . . . , x n 1 ) and head(q

2 ) = q(x 1 2 , . . . , x n 2 ) iff head(q) = q(v x 1 1 x 1 2 , . . . , v x n 1 x n 2 ) -(t 1 , t 2 , t 3 ) ∈ body(q 1
) and (t 4 , t 5 , t 6 ) ∈ body(q 2 ) iff (t 7 , t 8 , t 9 ) ∈ body(q) with, for 1 ≤ i ≤ 3, t i+6 = t i if t i = t i+3 and t i ∈ U ∪ L, otherwise t i+6 is the variable v t i t i+3 then q is the cover query of q 1 , q 2 .

It is worth noting that the definition of cover query, like that of cover graph (Definition 3), graph does not manipulate explicitly the generalization function ς. It is left implicitly in our way of defining the value of t i for 1 ≤ i ≤ 3: t i+6 = t i if t i = t i+3 and t i ∈ U ∪ L corresponds to the particular case ς(v, v) = v for v a URI or literal, while otherwise t i+6 is the variable b t i t i+3 corresponds to all the other cases, i.e., t i+6 = v t i t i+3 = ς(t i , t i+3 ).

The rationale behind the above definition of cover query is that (i) q's head is defined as the least general anti-unifier of the heads of q 1 and q 2 (first item above), trivially extended to the fact these queries can be of any arity, and (ii) each q triple is defined as a least general anti-unifier of an explicit q 1 triple and an explicit q 2 triple (second item above), so that, when the cover query exits (If . . . then . . . above), it is a generalization of q 1 and q 2 just in case RDF entailment rules and ontological constraints are not considered (first item in Definition 7 with R = ∅ and O = ∅). Moreover, similarly to the blank nodes introduced in the cover graph of RDF graphs (Section 2.3), (iii) the variables used to generalize pairs of distinct values across all the anti-unifications begetting q are consistently named: each time the distinct values α from q 1 and β from q 2 are generalized by a variable across these anti-unifications, it is always by the same q variable v αβ . This naming scheme enforces joins between q triples, which capture the common join structure within q 1 and q 2 , so that q is not only a generalization of q

1 v x1x2 v y1y2 v CPJP v y1JP v CPy2 v hCAhA τ v hCAτ v τ hA q c (v x 1 x 2 ) v x1x2 v y1y2 v CPy2 v CPP v CPJP v y1JP v y1P v Py2 v PJP Researcher Publication v x1y2 v y1R v PR v CPR v y1x2 v Ry2 v RJP v RP τ v τ hA τ τ τ v τ hA v hCAτ v hAτ v hAτ v hCAτ τ v hCAhA hasAuthor τ τ v τ hA τ τ v hCAτ v hAτ q c O (v x 1 x 2 )
Figure 3.5 -Cover queries of the BGPQs q 1 and q 2 in Figure 3.1 (top), and of their saturations q 1 ∞ O and q 2 ∞ O in Figure 3.3 (bottom). Triples in gray are redundant w.r.t. those in pink. and q 2 but also a least general generalization of them (second item in Definition 7 with R = ∅ and O = ∅).

The cover query q of the BGPQs q 1 and q 2 is displayed in Figure 3.5 (top). Its triple (v x 1 x 2 , τ, v CPJP ) results from anti-unifying the q 1 triple (x 1 , τ, ConfPaper) and the q 2 triple (x 2 , τ, JourPaper); the variable v x 1 x 2 is the least general value for the subject values x 1 and x 2 , the URI τ is that for the property values τ (because a constant is the least generalization of itself), and the variable v CPJP is that for the object values ConfPaper and JourPaper. This q triple captures that q 1 and q 2 both ask for resources having some type. Here, the fact this type is related to scientific publications is missed, due to the absence of background knowledge relating conference papers, journal papers and scientific publications. Similarly, the q triple (v x 1 x 2 , v hCAhCA , v y 1 y 2 ) results from anti-unifying the q 1 triple (x 1 , hasContactAuthor, y 1 ) and the q 2 triple (x 2 , hasAuthor, y 2 ). Because of our consistent naming of variables within q, this q triple and the preceding one join on v x 1 x 2 . Unfortunately, this second triple does not enhance the description of v x 1 x 2 in q, since it generalizes, hence is redundant with, the preceding one. It only captures from q 1 and q 2 that q asks for resources having somehow related to something. Here again, the fact that this relationship is to have some author is missed due to the absence of background knowledge. The two other anti-unifications begetting q's body also produce redundant triples.

As mentioned earlier, the cover query q of two BGPQs q 1 and q 2 may not exist. This happens when q, as defined in Definition 9, has its head not compatible with its body: some required answer variable(s) cannot be supplied by q's body. For instance, recall the BGPQs q 1 and q 2 used in Section 3.3 to point out that an lgg may no exist. Their cover query does not exist either, because Definition 9 leads to q(v x 1 x 2 ) ← (v x 1 y 2 , hasAuthor, v y 1 x 2 ), which is not a BGPQ (the answer variable v x 1 x 2 does not appear in the body). Importantly, the existence of an lgg of BGPQs and the existence of their cover query coincide.

The next theorem formalizes the above discussion: Theorem 9. Given two BGPQs q 1 , q 2 with the same arity and empty sets R of RDF entailment rules and O of RDFS statements:

1. the cover query of q 1 and q 2 exists iff an lgg of q 1 and q 2 exists; 2. the cover query of q 1 and q 2 is an lgg of q 1 and q 2 . Proof. The proof can be directly derived from that of the more general Theorem 10 (see below), noting that in the particular case of Theorem 9 R = ∅ and O = ∅ hold, hence q 1 ∞ O = q 1 and q 2 ∞ O = q 2 hold.

It follows from the above result that the cover query q of two BGPQs q 1 and q 2 displayed in Figure 3.5 (top) is an lgg of them just in case both RDF entailment rules and extra RDFS ontological constraints are ignored.

We provide below the worst-case time to compute a cover query, and its size; they directly follow from the definition of cover query (Definition 9). Proposition 4. The cover query of two BGPQs q 1 and q 2 can be computed in O(|body(q 1 )| × |body(q 2 )|); its size is |body(q 1 )| × |body(q 2 )|.

The next theorem generalizes the preceding one in order to use the notion of cover query to compute an lgg of two queries w.r.t. extra RDFS ontological constraints and any set of RDF entailment rules.

Theorem 10. Given a set R of RDF entailment rules, a set O of RDFS statements and two BGPQs q 1 , q 2 with the same arity, 1. the cover query q of q 1 ∞ O , q 2 ∞ O exists iff an lgg of q 1 , q 2 w.r.t. O exists; 2. the cover query q of q 1 ∞ O , q 2 ∞ O is an lgg of q 1 , q 2 w.r.t. O.

Proof. We start by showing that the cover query q, when it exists, is a generalization w.r.t. O of q 1 and q 2 , i.e., q 1 |= R,O q and that q 2 |= R,O q. Clearly, once proved, this entails the fact that if q exists, then an lgg of q 1 and q 2 w.r.t. O exists.

Consider the BGPQ q obtained from q by replacing every variable v t 1 t 2 by the value t 1 . Clearly, q |= R,O q and, by construction of q, q = q 1 ∞ O , i.e., q 1 |= R,O q. Showing that q 2 |= R,O q holds is done in a similar way. Therefore, the cover query q is a generalization of q 1 and q 2 w.r.t. O, thus an lgg of q 1 and q 2 w.r.t. O also exists. Now, let us show that the cover query q, when it exists, is an lgg of q 1 and q 2 w.r.t. O.

Let q lgg be any lgg of q 1 and q 2 w.r.t. O. Without loss of generality, assume that BGPQs do not contain blank nodes (recall that they can be equivalently replaced by non-answer variables, Chapter 1). Also, assume that q, q 1 , q 2 , q lgg heads are q(x), q 1 ( x1 ), q 2 ( x2 ), q lgg (x lgg ) respectively.

To prove our claim, we need to show that q |= R,O q lgg holds. Since q lgg is an lgg of q 1 and q 2 w.r.t. O, there exist two homomorphisms φ 1 and φ 2 from the variables in q lgg to the values (variables and constants) in

q 1 ∞ O and in q 2 ∞ O respectively, such that [body(q lgg )] φ 1 ⊆ body(q 1 ∞ O ) and φ 1 (x lgg ) = x1 , and similarly, [body(q lgg )] φ 2 ⊆ body(q 2 ∞ O ) and φ 2 (x lgg ) = x2 .
Consider the BGPQ q lgg obtained from q lgg by replacing every variable v by v t 1 t 2 where t 1 = φ 1 (v) and t 2 = φ 2 (v). Clearly, q lgg ≡ R,O q lgg holds. Assume that the head of q lgg is q lgg (x lgg ); by construction is has the same head as q.

Let us show that q |= R,O q lgg holds, i.e., there exists a homomorphism φ from the variables in q lgg to values in q ∞ O such that [body(q lgg )] φ ⊆ body(q ∞ O ) and φ( x lgg ) = x. By Definition of q, it is easy to see that the above holds when φ maps v t 1 t 2 either to t 1 if t 1 = t 2 and t 1 ∈ U ∪ L, or to itself otherwise. Crucially, this entails (i) the existence of the cover query q when an lgg q lgg exists and (ii) that q |= R,O q lgg holds, hence q |= R,O q lgg holds, and therefore q is an lgg of q 1 and q 2 w.r.t. O.

As an immediate consequence of the above results, we get the following worst-case time to compute an lgg of two BGPQs q 1 and q 2 , and its size. We assume given the saturation q 1 ∞ O and q 2 ∞ O w.r.t. the sets O of RDFS constraints and R of RDF entailment rules under consideration, as the times to compute q 1 ∞ O and q 2 ∞ O , and their sizes, depend on the particular sets O and R at hand. Corollary 2. A cover query-based lgg of two BGPQs q 1 and q 2 is computed in Figure 3.5 exemplifies the benefits of taking into account extra ontological constraints modeling background knowledge when identifying the commonalities between queries, thus of endowing the RDF relation of generalization/specialization between queries with such knowledge. When background knowledge is ignored (top), we only learn that both q 1 and q 2 ask for the resources having some type. In contrast, when we do consider background knowledge (bottom), we further learn that these resources, which both q 1 and q 2 ask for, are publications, which have some researcher as author.

O(|body(q 1 ∞ O )| × |body(q 2 ∞ O )|) and its size is |body(q 1 ∞ O )| × |body(q 2 ∞ O )|.

Conclusion

In this chapter, we first devised an extension of the standard relation of entailment between BGPQs (Definition 6), in order to compare them w.r.t. background knowledge formalized as RDFS ontological constraints. In particular, we showed that this novel generalization/specialization relation is well-founded w.r.t. the central reasoning tasks of query entailment and of query answering (Theorem 6) and that deciding entailment between BGPQs w.r.t. RDFS constraints is NP-complete (Theorem 7). Crucially, the definition of this relation builds on a notion BGPQ saturation w.r.t. background knowledge (Definition 5), which leverages the relevant background knowledge to complement the query.

Then, we adapted the notion of lgg that we defined for RDF graphs in the preceding chapter, to our SPARQL setting by using BGPQs in place of RDF graphs and our new entailment relation between BGPQs in place of entailment between RDF graphs (Definition 7), because we pointed out that the shortcomings of using standard entailment between BGPQs. Notably, and by constrast with the notion of lgg of RDF graphs, we showed that an lgg of BGPQs may not exist (Theorem 8), whether or not we consider background knowledge. Similarly to the notion of lgg of RDF graphs, we showed (Theorem 8) that -when an lgg exists -there exists a unique equivalent class of lggs of BGPQs: though syntactically different lggs of some BGPQs exist, they are all equivalent w.r.t. the relation of entailment between BGPQs. We also showed that the problem (Problem 2) of computing such an lgg of n > 2 BGPQs can be solved, without loss of generality, if we have a solution to the particular instance of this problem where n = 2 (Proposition 3).

We therefore devised the notion of cover query of two input BGPQs (Definition 9), which is a BGPQ, whose existence coincides with that of their lgg and, further, this cover query corresponds (i) to an lgg of the input BGPQs when no entailment rules and background knowledge are considered (Theorem 9) and to (ii) an lgg of the input BGPQs w.r.t. the entailment rules and background knowledge under consideration (Theorem 10), when the input BGPQs are saturated with these rules and knowledge before computing their cover query. Also, we showed (Proposition 4 and Corollary 2) that the time to compute a cover query, and its size, are at most quadratic in the size of the input (saturated) BGPQs.

Introduction

In this chapter we provide algorithms to compute lggs of RDF graphs and BGPQs, based on the results obtained in the two preceding chapters.

In Section 4.2, we present an algorithm for computing the least general anti-unifiers of tuples of RDF values (URIs, literals, blank nodes and variables), i.e., of triples, triple patterns or query heads, on which the definitions of cover graphs and queries rely. Then, in Section 4.3, we give three algorithms to compute a cover graph-based lgg of RDF graphs, which allow handling RDF graphs of increasing size, i.e., when the input and output RDF graphs fit in memory, in data management systems or in MapReduce clusters. Also, to choose between these algorithms, we show how the exact size of a cover graph-based lgg they produce can be calculated, without computing this lgg. Finally, in Section 4.4, we provide an in-memory algorithm to compute a cover querybased lgg of BGPQs.

Least general anti-unification

Algorithm 1, called lgau, computes a least general anti-unifier (t () when n = 0 literals), blank nodes and variables. This is achieved by setting the i th value t T i of the output tuple to the least general generalization of the values found at the i th positions of the two input tuples: t i and t i . Recall that a pair of a same constant is generalized by that constant itself, while in all other cases the generalization is either a blank node in case of RDF graph triple values (Section 2.3) or a variable in case of query head answer variables or of query body triple pattern values (Section 3.4). Generalizing pairs of differents values with blank nodes or variables is controlled with the Boolean bnodes parameter. Crucially, these generated blank nodes (resp. variables) adopt the consistent naming scheme devised in Section 2.3 (resp. in Section 3.4) that allows us preserving the common input RDF graphs (resp. BGPQs) structure across the antiunifications of triples (resp. triple patterns).

lggs of RDF graphs

Following Definition 3, Algorithm 2, called lgg4g, computes the cover graph G of two input RDF graphs G 1 and G 2 : G comprises the least general anti-unification of every pair of G 1 and G 2 triples with same property. Therefore, given two RDF graphs G 1 and G 2 , a call lgg4g(G 1 , G 2 ) produces the cover graph-based lgg of G 1 and G 2 ignoring RDF entailment (Theorem 2), while a call lgg4g(G ∞ 1 , G ∞ 2 ) produces the cover graph-based lgg of G 1 and G 2 taking into account the set of RDF entailment rules at hand (Theorem 3). In the latter case, the input RDF graphs can be saturated using standard algorithms implemented in RDF data management systems, like Jena [jen, 2017] and Virtuoso [vir, 2017].

Importantly, lgg4g assumes that the input RDF graphs, as well as their output cover graph, fit in memory. Checking whether this is the case for the input RDF graphs under consideration can be done as follows.

The size of the input RDF graphs G 1 and G 2 can be computed with the following SPARQL queries counting how many triples each of them holds:

for all T 2 = (s 2 , p 2 , o 2 ) ∈ G 2 with p 1 = p 2 do 4: G ← G ∪ {lgau(T 1 , T 2 , true)} 5: return G SELECT count(*) as ?size FROM G i with i ∈ [1, 2].
Recall that the worst-case size of the output cover graph is |G| = |G 1 | × |G 2 | in the unlikely case where all the G 1 and G 2 triples use the same property (Property 2 and Corollary 1).

The precise size of the output cover graph G can be computed, without computing G, with SPARQL queries. First, we calculate for each input RDF graph G i , with i ∈ [START_REF]2 Sample RDF graph G[END_REF]2], how many triples it holds per distinct property p:

S G i = {(p, n i ) | |{(s, p, o) ∈ G i }| = n i }
This can be computed with the SPARQL query: SELECT ?p count(*) as ?n i FROM G i WHERE {(?s, ?p, ?o)} GROUP BY ?p.

Then, since every G 1 triple with property p anti-unifies with every G 2 triple with same property p, in order to beget G, the size of G is:

|G| = (p,n 1 )∈S G 1 ,(p,n 2 )∈S G 2 n 1 × n 2
This can be computed with the SPARQL query:

SELECT SUM(?n 1 *?n 2 ) as ?size WHERE {{S G 1 }{S G 2 }}
with S G 1 and S G 2 denoting the above-mentioned SPARQL queries computing these two sets, which join on their commun answer variable ?p.

When the input RDF graphs or their output cover graph cannot fit in memory, we propose variants of lgg4g that either assume that RDF graphs are stored in data management systems (DMSs, in short) or in a MapReduce cluster.

Handling large RDF graphs using DMSs

Algorithm 3, called lgg4g-dms, is an adaptation of lgg4g, which assumes that the input RDF graphs (already saturated if needed) and their cover graph are all while

B 2 = c 2 .next(n) do fetch next n G 2 triples 5: for all T 1 = (s 1 , p 1 , o 1 ) ∈ B 1 do 6:
for all

T 2 = (s 2 , p 2 , o 2 ) ∈ B 2 with p 1 = p 2 do 7: insert lgau(T 1 , T 2 , true) into G
stored in one or several DMSs. It further assumes that the system(s) storing the input RDF graphs G 1 and G 2 feature(s) the well-known database mechanism of cursor [Garcia-Molina et al., 2009, Ramakrishnan andGehrke, 2003]. This is for instance the case for RDF graphs stored in relational servers like DB2 [db2, 2012], MySQL [mys, 2017], Oracle [ora, 2017] and PostgreSQL [pos, 2016], or in RDF servers like Jena-TDB [jen, 2017] and Virtuoso [vir, 2017]. Roughly speaking, a cursor is a pointer or iterator on tuples hold in a DMS, e.g., stored a relation or computed as the results to a query, that can be used to access these tuples. In particular, a cursor can be used by an application to iteratively traverse all the tuples by fetching n of them at a time.

lgg4g-dms uses cursors to proceed similarly to lgg4g (remark that lines 5-7 in Algorithm 3 are almost the same as lines 2-4 in Algorithm 2) on pairs of n-triples subsets of G 1 and of G 2 , instead of on the whole RDF graphs themselves. It follows that the worst-case number of triples kept in memory by lgg4g-dms is M = (2 × n) + 1 at line 7 (i.e., n for B 1 , n for B 2 , and the anti-unifier triple output by lgau), with:

3 ≤ M ≤ |G 1 | + |G 2 | + 1.
The above lower bound is met for n set to 1, while the upper one is met for n set to max(|G 1 |, |G 2 |). Importantly, lgg4g-dms allows choosing the value of n in order to reflect the memory devoted to handling triples. For instance, if one wants to use 4GB of RAM for triples, assuming that any triple fits in less one 1KB (this value is much less when using dictionary encoding [Neumann and Weikum, 2010a], i.e., when triples values are mapped to integers), the value of n can be set to 2M.

This clearly contrasts with the worst-case number of triples kept in memory by lgg4g:

M = |G 1 | + |G 2 | + |G| at line 5, with: |G 1 | + |G 2 | ≤ M ≤ |G 1 | + |G 2 | + (|G 1 | × |G 2 |).
The above lower bound is met when G 1 and G 2 have no property in common in their triples (i.e., |G| = 0), while the upper one is met in the unlikely case where G 1 and G 2 use a same property in all their triples (i.e.,

|G| = |G 1 | × |G 2 |).

Handling huge RDF graphs using MapReduce

Algorithm 4, called lgg4g-mr, is a MapReduce (MR) variant of lgg4g. MR is a popular massively parallel programming framework [START_REF] Dean | Mapreduce: Simplified data processing on large clusters[END_REF], implemented by many large-scale data processing systems, like Hadoop [had, 2016] and Spark [spa, 2017], which orchestrate clusters of compute nodes.

A MR program is organized in successive jobs, each of which comprises a Map task followed by a Reduce task. The Map task consists in reading some input data from the distributed file system1 of the cluster, so as to partition the data into k, v key-value pairs. Importantly, an MR engine transparently processes the Map task by running Mapper processes in parallel on cluster nodes, each process taking care of partitioning a portion of the input data by applying a Map(key: file, value: data unit) function on every data unit of a given input file. Key-value pairs thus produced are shuffled across the network, so that all pairs with same key k, v 1 • • • k, v n are shipped to a same compute node. The Reduce task then consists in running Reducer processes in parallel, for every distinct key k received by every compute node. Each process takes care of the set V of values {v 1 , . . . , v n } emitted with key k, by applying a Reduce(key: k, values: V) function, and writing its results in a file. The result of an MR job, comprises the data, stored in a distributed fashion, in all the files output by Reducers.

In lgg4g-mr, the Map function applies to every (s i , p i , o i ) triple of the input RDF graph G i stored in file G i , and produces the corresponding key-value pair p i , (G i , (s i , p i , o i )) , for i ∈ [START_REF]2 Sample RDF graph G[END_REF]2]. Hence, all the G 1 and G 2 triples with a same key/property p are shipped to the same cluster node. Then, similarly to lgg4g at lines 2-4, the Reduce functions process, on each node, the set V of values emitted for every received key p. The least general anti-unification triples obtained at line 4 are stored in the output file G-p. At the end of the MR job, the lgg G of G 1 and G 2 is stored in the G- * files of the distributed file system, where * denotes any key/property p.

In lgg4g-mr, the Map function holds at most a single G 1 or G 2 triple in memory. In constrast, the worst-case number of triples handled by the Reduce function for a given key p is:

M = |G 1 | + |G 2 | + 1 at line 4.
This upper bound is met in the unlikely case where G 1 and G 2 use the same property p in all their triples. Similarly to lgg4g-dms, this upper bound can set to M = ( 2

× n) + 1, with 3 ≤ M ≤ |G 1 | + |G 2 | + 1, by first splitting the input RDF graphs in k i files of n G i triples (files G 1 i , . . . , G k i i )
, and then by processing every pair of n-triples of G 1 and G 2 files with an MR job (i.e., with k 1 × k 2 jobs), instead of a single MR job for the entire two input RDF graphs.

Finally, to take into account RDF entailment, the input RDF graphs G 1 and G 2 can be saturated before being stored in the MR cluster, by using standard (centralized) techniques, or within the MR cluster, by using MR-based saturation techniques [START_REF] Urbani | Scalable distributed reasoning using mapreduce[END_REF], Urbani et al., 2012]. Also, it is worth noting that RDF Algorithm 4 Cover graph of two RDF graphs: lgg4g-mr

In: file G 1 for RDF graph G 1 , file G 2 for RDF graph G 2 Out: G is the cover graph of G 1 and G 2 , stored in G- * files Map(key: file G i , value: triple T i = (s i , p i , o i )) 1: emit( p i , (G i , T i ) ) Reduce(key: p, values: set V of values emitted for key p) 1: f ← open(G-p) 2: for all (G 1 , T 1 = (s 1 , p, o 1 )) ∈ V do 3: for all (G 2 , T 2 = (s 2 , p, o 2 )) ∈ V do 4:
f.write(lgau(T 1 , T 2 , true)) 5: close(f ) graphs, thus lggs of RDF graphs, stored in an MR cluster can be queried with MRbased SPARQL engines [START_REF] Husain | Heuristics-based query processing for large RDF graphs using cloud computing[END_REF], Lee and Liu, 2013, Papailiou et al., 2014, Goasdoué et al., 2015].

lggs of BGPQs

Following Definition 9, Algorithm 5, called lgg4q, builds and returns either the cover query q of two input BGPQs q 1 and q 2 if it exists, or the ⊥ symbol otherwise.

Algorithm 5 Cover query of two BGPQs: lgg4q

In: BGPQs q 1 and q 2 Out: Cover query q of q 1 and q 2 if it exists, else ⊥ 1: head(q) ← lgau(head(q 1 ), head(q 2 ), false) 2: body(q) ← ∅ 3: for all

T 1 = (s 1 , p 1 , o 1 ) ∈ G 1 do 4: for all T 2 = (s 2 , p 2 , o 2 ) ∈ G 2 do 5:
body(q) ← body(q) ∪ {lgau(T 1 , T 2 , false)} 6: if q is a well-formed BGPQ then 7:

return q 8: else 9:

return ⊥ error: a cover query does not exist At line 1, lgg4q computes the head of q as the least general anti-unifier of the heads of q 1 and q 2 (first item in Definition 9). Then, at lines 3-5, lgg4q computes the body of q, which comprises a least general anti-unifier of every pair of q 1 body and q 2 body triples (second item in Definition 9). Finally, lgg4q checks whether q is a well-formed BGPQ, i.e., if its answer variables occur in its body triples, otherwise there is no cover query of q 1 and q 2 , and also no lgg of q 1 and q 2 (Theorems 9 and 10).

Therefore, given two BGPQs q 1 and q 2 , a call lgg4q(q 1 , q 2 ) produces the cover query-based lgg of q 1 and q 2 ignoring RDF entailment and extra ontological constraints, whenever it exists (Theorem 9), while a call lgg4q(q 1 ∞ O , q 2 ∞ O ) produces the cover querybased lgg of q 1 and q 2 taking into account the set of RDF entailment rules at hand, as well as a set of extra ontological constraints, whenever it exists (Theorem 10). In the latter case, the saturated input BGPQs can be computed using the set characterization of their triples discussed in Section 3.2.

Conclusion

In this chapter, we provided algorithms in order to compute cover graph-based lggs of RDF graphs (Definition 3, Algorithm 3) and cover query-based lggs of BGPQs (Definition 9, Algorithm 5). As input RDF graphs may not fit in memory, we also provided algorithms depending on whether they can fit in a data management system (Algorithm 3) or in a MapReduce cluster (Algorithm 4).

Introduction

In the preceding Chapter, we provided solutions for learning an lgg of RDF graphs and of BGPQs, faithful to the RDF and SPARQL W3C recommendations. Notably, we neither restrict the structure nor the semantics of RDF graphs and of BGPQs, while the literature (see Chapter 6) (i) imposes structural restrictions and (ii) only uses simple entailment (|=) between RDF graphs and between BGPQs, to define lggs, hence ignores their saturations, which are essential to consider their full semantics, in particular in presence of ontological knowledge formalized as RDFS constraints. In our experiments, we focus on showing how much more precise lggs are when entailment beween RDF graphs (|= R ) and entailment between BGPQs w.r.t. background knowledge (|= R,O ) are utilized instead of just simple entailment (|=).

In Section 5.2, we first establish metrics to quantify the gain in precision that using non-simple entailment yields when learning lggs of RDF graphs and of BGPQs. Then, in Section 5.3, we describe our experimental setting. Finally, we analyze within this 59 setting the gain in precision of lggs of RDF graphs in Section 5.4, and of BGPQs in Section 5.5, depending on the entailment relation under consideration.

Gain in precision metrics

The case of RDF graphs

The next result shows that measuring the gain in precision for an lgg of RDF graphs when standard entailment is used instead of simple entailment, amounts to measuring an entailment distance through the standard relation of entailment between RDF graphs (|= R ).

Proposition 5. Let G 1 , . . . , G n be n RDF graphs, G lgg an lgg of G 1 , . . . , G n w.r.t. the empty set of entailment rules (i.e., defined using simple entailment |= between RDF graphs) and G R lgg an lgg of G 1 , . . . , G n w.r.t. any set R of entailment rules (i.e., defined using standard entailment |= R between RDF graphs). Then, G R lgg |= R G lgg holds.

Proof. Since all the lggs of some given RDF graphs are equivalent (Theorem 1)

: (i) G lgg is equivalent to the cover graph-based lgg G of G 1 , . . . , G n , i.e., G lgg ≡ R G holds, and (ii) G R lgg is equivalent to the cover graph-based lgg G of the saturations with R of G 1 , . . . G n , i.e., G R lgg ≡ R G holds.
These cover graph-based lggs can be computed based on Proposition 1 when n > 2. Further, by definition of a cover graph (Definition 3), G is a subset of G , thus (iii) G |= G holds. Therefore, from (i), (ii) and (iii), G R lgg |= R G lgg holds.

From the above result, and by the definition of an lgg, it immediately follows that for each input RDF graph G 1≤i≤n , G i |= R G R lgg |= R G lgg holds. Further, whenever the lggs G lgg and G R lgg are the cover graph-based ones computed from G 1 , . . . , G n and from their saturations respectively, then: if

G i |= φ i R G R lgg holds then G i |= φ i R G lgg also holds, i.e., if G ∞ i |= φ i G R lgg holds then G ∞ i |= φ i G lgg
also holds, since by definition and construction of these cover graph-based lggs:

G lgg ⊆ G R lgg holds. Interestingly, in this case, the RDF graphs [G lgg ] φ i and [G R lgg ] φ i are such that [G lgg ] φ i ⊆ [G R lgg ] φ i ⊆ G ∞
i holds and they represent the triples from G i and from G ∞ i respectively, that participated in anti-unifications to beget the cover graph-based lggs G lgg and G R lgg respectively. In addition, remark that for the homomorphism φ i that directly follows from our naming of G R lgg blank nodes 1 , [G lgg ] φ i and [G R lgg ] φ i are clearly maximal as they result, by construction, of all possible anti-unifications of triples. Therefore, when φ i is maximal, the saturations of these RDF graphs (

[G lgg ] φ i ) ∞ and ([G R lgg ] φ i ) ∞ are such that ([G lgg ] φ i ) ∞ ⊆ ([G R lgg ] φ i ) ∞ ⊆ G ∞
i holds and they represent the subsets of all explicit and implicit G i triples that are generalized by those of G lgg and G R lgg respectively.

From the above observation, we measure the gain in precision of the lgg G R lgg over the lgg G lgg w.r.t. the input RDF graph G 1≤i≤n , noted ρ i , as the percentage of explicit and implicit G i triples that G R lgg generalizes while G lgg does not:

ρ i = |([G R lgg ] φ i ) ∞ | -|([G lgg ] φ i ) ∞ | |G ∞ i |
.

Finally, we measure the gain in precision of the lgg G R lgg over the lgg G lgg w.r.t. the input RDF graphs G 1 , . . . , G n , noted ρ, as the average of the above ρ 1 , . . . , ρ n :

ρ = Σ n i=1 ρ i n .

The case of BGPQs

Similarly to the case of RDF graphs, we establish: Proposition 6. Let R be a set of entailment rules, O a set of RDFS statements, and q 1 , . . . , q n BGPQs with same arity. An lgg q lgg of q 1 , . . . , q n (i.e., defined using simple entailment |=) and an lgg q R,O lgg of q 1 , . . . , q n w.r.t. R and O (i.e., defined using our novel entailment relation |= R,O ) are such that: q R,O lgg |= R q lgg holds.

Proof. Since all the lggs of some given BGPQs are equivalent (Theorem 8): (i) q lgg is equivalent to the cover query-based lgg q of q 1 , . . . , q n , i.e., q lgg ≡ R q, and (ii) q R,O lgg is equivalent to the cover query-based lgg q of the saturations with R of q 1 , . . . , q n w.r.t. O, i.e., q R,O lgg ≡ R q . These cover query-based lggs can be computed based on Proposition 3 when n > 2. Further, by definition of a cover query (Definition 9), q and q have the same heads and the body of q is a subset of that q , thus (iii) q |= q holds. Therefore, from (i), (ii) and (iii), q R,O lgg |= R q lgg holds.

From the above result, we devise a new gain in precision metric for the lggs of BGPQs, because the adaptation of the above one for the lggs of RDF graphs does not make sense here. Indeed, the above metric measures on average how much more G i triples participate in anti-unifications when standard entailment (|= R ) is used instead of simple entailment (|=) when computing a cover graph-based lgg of RDF graphs. However, in the case of BGPQs, all q i and all q R,O lgg triples participate in anti-unifications, because an unknown value is allowed in the property position of a BGPQ triples while this is not the case for RDF graph triples (recall that the property must be a URI). As a result, adapting the above metric to lggs of BGPQs would only reflect the size increase between q lgg and q R,O lgg that the saturation of q lgg w.r.t. R and O produces. Instead, we rely on the fact that from the query answering point of view, using Property 4 (Section 1.3) and the above Proposition 6, q R,O lgg (G) ⊆ q lgg (G) holds for any RDF graph G, and clearly the more q R,O lgg is specific w.r.t. q lgg through |= R , the smaller the subset q R,O lgg (G) of q lgg (G) is, i.e., the smaller |q R,O lgg (G)| is w.r.t. |q lgg (G)|. Therefore, to measure the semantic distance between q R,O lgg and q lgg through |= R , we define the gain in precision ρ that standard entailment endowed with background knowledge (|= R,O ) yields over simple entailment (|=) w.r.t. query answering as the percentage of q lgg answers against G that are not q R,O lgg against G:

ρ = 1 - | q R,O lgg (G) | | q lgg (G) | .

Experimental setting

We describe now the setup used to evaluate our technical contributions.

Software

We implemented our technical contributions in Java 1.8, on top of the Jena 3.0.1 RDF reasoner and of a PostgreSQL 9.3.11 server, all used with default settings.

We used Jena to compute the saturation of an RDF graph, against which queries must be evaluated to obtained their complete answer sets (Chapter 1); we also used Jena to compute the saturation q ∞ O of a BGPQ q w.r.t. a set O of RDFS constraints (Definition 5): we rely on Jena's saturation, union and difference operators to compute q ∞ O 's body.

We used PostgreSQL to evaluate SQLized BGPQs against a saturated RDF graph stored in a TripleDBpedia(s,p,o) table. The table is indexed by all permutations of the s, p, o columns, leading to a total of 6 indexes. This indexing choice is inspired by [Neumann andWeikum, 2010b, Weiss et al., 2008], to give PostgreSQL efficient query evaluation opportunities. There exists alternative data layouts like having one two-columns table p(s,o) per distinct property p in the RDF graph, which stores all the subject/object tuples of triples with property p [START_REF] Bursztyn | Teaching an RDBMS about ontological constraints[END_REF], or the elaborate layout of [START_REF] Bornea | Building an efficient RDF store over a relational database[END_REF] used in DB2 RDF. However, adopting another data layout than the Triple table would have no impact on our experiments, as the reported times are not related to query evaluation.

Hardware

We used an Intel Xeon (X5550) 2.67GHz machine with 32GB RAM, using Ubuntu 14.04.3 LTS (64bits).

Next, all measured times on this hardware are averaged over 5 warm runs and are in milliseconds.

Datasets

We selected two datasets to conduct our experiments, the real DBpedia dataset [START_REF] Lehmann | DBpedia[END_REF]] and a synthetic dataset on LUBM universities [START_REF] Guo | LUBM: A benchmark for OWL knowledge base systems[END_REF].

The RDF graph G LUBM , which we generated with the LUBM data generator 2 , com- In our experiments, we always used the subset of standard RDF entailment rules shown in Table 1.2 (Chapter 1), which fully allows exploiting RDFS ontological constraints.

Test RDF Graphs Our experiments with RDF graphs rely on 9 subgraphs of G DBpedia which contain 397 triples from O DBpedia , related to the selected subgraphs. Their characteristics are shown in Table 5. 1 (top) and are further detailed in Appendix A, page 85. The 397 triples from O DBpedia are listed in Appendix D, page 93. We distinguish two subsets of RDF graphs: G 1 -G 4 , Table 5. 1 (left), are heterogeneous in the sense that they differ both on their structure and on the kind of information they represent, hence use distinct classes, properties and URI values, while G 5 -G 9 , Table 5.1 (right), are more homogeneous and only differ in some properties and URI values.

Table 5.1 shows some properties of our test RDF graphs. Line 2 of Table 5.1 gives the number of triples which are not ontological constraints as all contain 397 ontological constraints. Line 3 of Table 5.1 provides the number of triples in the saturated RDF graphs that are not ontological constraints (whose size is precisely 1067 triples). The size of our RDF graph tests varies from 4 + 397 to 6 + 397 (line 3, Table 5.1) while their saturations (line 4, Table 5.1) vary from 16 + 1067 to 25 + 1067 triples. The size increase due to saturation is ×2.7 on average; the size increase of the non ontological subsets varies from ×3.4 (G 2 ) to ×4.8 (G 9 ). The saturation of a test RDF graphs requires 75.44 ms on average. Test Queries We used queries for the two datasets previously presented, which were executed on the entire saturations of G LUBM and G DBpedia respectively.

DBpedia graph G 1≤i≤9 : G 1 G 2 G 3 G 4 G 5 G 6 G 7 G 8 G 9 |G i |'s shape Graph Graph Tree Graph Graph Graph Graph Graph Graph |G i \ O DBpedia | 4 5 4 6 6 4 6 5 5 |G i ∞ \ O ∞ DBpedia | 16
LUBM query DBpedia query LUBM queries: we borrowed from [START_REF] Bursztyn | Optimizing reformulation-based query answering in RDF[END_REF]] a set of 9 BGPQs which are described in Appendix B, page 89. Their characteristics are displayed in Table 5.2 (top): queries have a variety of structural aspects (lines 1 and 3) and body size (line 2) and differs in the answer numbers (line 4).

Q 1≤i≤9 : Q 1 Q 2 Q 3 Q 4 Q 5 Q 6 Q 7 Q 8 Q 9 Q i '
Q 1≤i≤8 : Q 1 Q 2 Q 3 Q 4 Q 5 Q 6 Q 7 Q 8 Q i '
DBpedia queries: we defined 42 test BGPQs among which we picked 8 representative ones. These 8 queries are described in Appendix C, page 91. Their characteristics are displayed in Table 5. 3 (top). Similarly to our selected LUBM queries, DBpedia queries have a variety of structural aspects (lines 1 and 3) and body size (line 2) and differs in the answer numbers (line 4).

We consider two subsets of DBpedia queries: Q 1 -Q 4 ,Table 5. 3 (left), are heterogeneous, while Q 4 -Q 8 , in Table 5. 3 (right), are homogeneous.

The Saturations of our test queries w.r.t. background knowledge, O LUBM and O DBpedia respectively, are presented Tables 5.2 (bottom) and 5. 3 (bottom). They show the size of the saturated test queries and the time to compute them. Enriching our test queries using the LUBM and DBpedia ontological constraints augments their size: from ×2 for Q 6 up to ×5 for Q 8 in the LUBM case; from ×3.16 for Q 2 up to ×4.75 for Q 3 in the DBpedia case. The query saturation time is rather fast with LUBM, 23 ms on average, while it is 692 ms on average with DBpedia. Saturation times have been multiplied by 30 from LUBM to DBPedia, since the latter has ×125 more constraints than the former.

lggs of RDF graphs

We report now on the experiments we made with our test RDF graphs. Table 5.4 (lines 1 and2) shows that cover graph-based lggs of test RDF graphs are computed quickly whether or not they are saturated: 4 to 6 ms when they are not saturated, and 8 to 15 ms when they are saturated. Line 3, Table 5.4, shows the gain brought by considering standard entailment w.r.t. simple entailment. To fully assess this gain, as the number of own triples of each test graph is low compared to those of the size of their ontological part, we slightly modify our metric defined in section 5.2.1 so that the ontological constraints are not considered: as all input test RDF graphs, hence their lgg share these constraints. Thus, line 3 Table 5.4 points out that using standard entailment when computing an lgg offers a significant precision gain for heterogenous graphs (from 42.46% to 61.12%), and a more limited but notable precision gain for homogeneous graphs (from 0% to 19.89%).

The gain of 0% for graphs G 6 and G 8 is explained by the fact their structures are the same. They differ only on subject and object URIs and the 4 distinct triples of G 6 have the same property URIs as 4 triples among 5 from G 8 .

For heterogenous test RDF graphs, the gain is considerable for G 3 and G 4 (61.12%): they have only one common property; nevertheles almost all the remaining properties of G 3 have a common super-property with one of G 4 , which are made explicit through saturation.

lgg of 2 DBpedia graphs: We have also computed lggs of k test RDF graphs, with 2 < k ≤ 4. Table 5.5 and Table 5.6 show the time to compute them, and the gain in precision of using standard entailment instead of simple entailment.

G 1 G 2 G 1 G 3 G 1 G 4 G 2 G 4 G 3 G 4 G 5 G 6 G 5 G 9 G 6 G 7 G 6 G 8 G 7 G 8 G 8 G 9
G 1 G 2 G 3 G 1 G 2 G 4 G 1 G 3 G 4 G 2 G 3 G 4 G 5 G 6 G 7 G 5 G 6 G 8 G 5 G 6 G 9 G 6 G 7 G 8 G 7 G 8 G 9
As defined in Proposition 1, Chapter 2, lgg of k test RDF graphs are computed as a sequence of k -1 cover graph-based lggs of two RDF graphs. For example, the lgg G 1 G 2 G 4 (Table 5.5) is the cover graph-based lgg of the cover graph-based lgg G 1 G 2 (Table 5.4) and the test RDF graphs graph G 4 . lgg of 4 DBpedia graphs: Table 5.5 and Table 5.6 (lines 1 and 2) outline that the computation of a cover graphbased lggs of k test RDF graphs is rather fast when simple entailment is used (10 to 18 ms), and a little slower when standard entailment is applied (30 to 240 ms). These latter measures represent the time required to compute the entire sequence of k -1 cover graph-based lggs. Table 5.5 and Table 5.6 (line 3) hightlight that using standard entailment also significantly increases the precision of some lggs, from a small gain of 1.44% for G 5 G 6 G 8 up to an important gain of 51.65% for G 2 G 3 G 4 . Therefore, even for lgg of more than 2 graphs, using standard entailment instead of simple entailment enables to get more precise lgg.

G 1 G 2 G 3 G 4 G 5 G 6 G 7 G 9 G 5 G 6 G 8 G 9 G 6 G 7 G 8 G 9

lggs of BGPQs

We report now on the experiments we made with our test BGPQs. LUBM. Table 5.7 (lines 1 and 3) shows that cover query-based lggs of test queries are always computed fast whether or not we consider the LUBM ontological constraints: 1 to 4 ms when they are ignored, and 5 to 10 ms when they are considered. In the latter case, overall, it takes between 50 and 59 ms to compute an lgg in the worst case (i.e., when the two saturated test queries are computed in sequence before computing their cover query). Table 5.7 (lines 2 and 4) shows that ignoring background knowledge significantly increases the number of answers for some lggs, from a small ×1.32 for Q 2 Q 8 up to a striking ×73.39 for Q 2 Q 4 , with a significant average of ×16.45. This translates into the precision gains shown at line 5 (Table 5.7): 74.80% overall, 98.63% for queries Q 2 and Q 4 , and 24.49% for Q 2 and Q 8 . lggs with same number of answers in Table 5.7 were found either equivalent or almost equivalent so that their semantic difference is not visible on the LUBM dataset, e.g., the lggs of

Q 2 Q 4 , Q 1 Q 8 , Q 5 Q 8 and Q 8 Q 9 with
1 048 360 answers (i.e., ignoring ontological constraints) are asking for all the (distinct) subject/object pairs in triples in the LUBM RDF graph; the lggs of Q 8 Q 9 , Q 2 Q 8 with 56 358 answers (i.e., considering ontological constraints) ask respectively for faculties with some degree from some university and for employees with some doctoral degree from some university: they have the same number of answers in our LUBM RDF graph because all faculties have some doctoral degree and all employees with some doctoral degree are faculties.

We have also computed lggs of k test queries where 2 < k ≤ 4. Table 5.8 and Table 5.9 show the obtained cover query-based lggs. As defined in Proposition 3, chapter 3, lgg of k test queries are computed as a sequence of k -1 cover query-based lggs of two queries. Table 5.8 and Table 5.9 (lines 1 and 3) point out that the lgg of 2 LUBM queries: lgg of 3 LUBM queries: computation of a cover query-based lggs of k test queries is rather fast whether or not we consider the LUBM ontological constraints: 3 to 10 ms when they are ignored, and 11 to 23 ms when they are considered. These latter times represent the time required to compute the entire sequence of k -1 cover query-based lggs. Table 5.8 and Table 5.9 (lines 2 and 4) hightlight that ignoring background knowledge also significantly increases the number of answers for some lggs, from a small ×8.71 for

Q 1 Q 4 Q 2 Q 4 Q 1 Q 8 Q 2 Q 8 Q 5 Q 8 Q 1 Q 9 Q 8 Q 9 Q 3 Q 6 Q 3 Q 7 Time to compute q lgg 1 2
Q 1 Q 2 Q 4 Q 1 Q 8 Q 9 Q 2 Q 8 Q 9 Q 1 Q 4 Q 8 Q 1 Q 4 Q 9 Q 2 Q 4 Q 8 Q 1 Q 5 Q 8 Q 5 Q 8 Q 9
Q 1 Q 2 Q 8 Q 9 up to a striking ×73.36 for Q 1 Q 2 Q 4 .
This is reflected by the precision gains shown at line 5 (Table 5.8 and Table 5.9): 92.35% overall for lgg of 3 test queries, 91.09% overall for lgg of 4 test queries. Thus, even for lgg of more than 2 queries, taking into account LUBM ontological constraints enables to get more precise lgg. We remark that lggs of k queries ignoring background knowledge yield to an equivalent cover query-based lgg as soon as k is 3 (see Table 5.8, line 2, lgg of 3 test queries having 1 048 060 answers), while lggs of k queries taking into account LUBM ontological constraints begin to become almost all equivalent when k reaches 4 (see Table 5.9, line 4, lgg of 4 test queries having 120 225 answers).

lgg of 4 LUBM queries: lgg of 3 DBpedia queries: lgg of 4 DBpedia queries: DBpedia. First, as Table 5.10 (lines 1 and 3) shows, the cover query-based lggs of test queries are always computed fast whether or not the DBpedia ontological constraints are considered: from 3 to 6 ms when ignored, to 13 to 18 ms when considered.

Q 1 Q 2 Q 4 Q 8 Q 1 Q 2 Q 4 Q 9 Q 1 Q 2 Q 8 Q 9 Q 1 Q 4 Q 5 Q 8 Q 1 Q 5 Q 8 Q 9 Q 2 Q 4 Q 8 Q 9 Q 2 Q 5 Q 8 Q 9
Q 1 Q 2 Q 1 Q 3 Q 1 Q 4 Q 2 Q 3 Q 4 Q 7 Q 4 Q 8 Q 5 Q 6 Q 5 Q 7 Q 7 Q 8 Time to
Q 1 Q 2 Q 3 Q 1 Q 2 Q 4 Q 1 Q 3 Q 4 Q 2 Q 3 Q 4 Q 4 Q 7 Q 8 Q 5 Q 7 Q 8
Q 1 Q 2 Q 3 Q 4 Q 4 Q 5 Q 7 Q 8
Table 5.10 (lines 2 and 4) also shows that the answer set of an lgg is significantly larger when DBpedia ontological constraints are not taken into account: the size difference goes from a small ×1 for the homogeneous queries Q 4 , Q 7 up to a striking ×76.42 for the heterogeneous queries Q 1 , Q 4 , with a significant average of ×17.50 (×33.34 for the heterogeneous queries and ×1.65 for the homogeneous ones). This translates into the precision gains shown at line 5: 55.57% overall, 90.18% for the heterogeneous queries, and 27.88% for the homogeneous ones.

Then, we have also computed lggs of k DBpedia test queries where 2 < k ≤ 4. Table 5.11 and Table 5.12 display the obtained cover query-based lggs. Table 5.11 and Table 5.12 (lines 1 and 3) point out that the computation of a cover query-based lggs of k test graphs is fast whether simple entailment or standard entailment endowed with background knowledge is using (from 5 to 14 ms and from 22 to 36 ms respectively).

These measures denote the time required to compute the entire sequence of k -1 cover query-based lggs. Table 5.11 andTable 5.12 (line 5) outline that using entailment w.r.t. background knowledge also significantly increases the precision of some lggs, from a small gain of 13.96% for Q 5 Q 7 Q 8 up to a considerable gain of 98.23 for Q 1 Q 2 Q 4 . Therefore, even for DBpedia test queries, lgg of more than 2 queries which relies on entailment between BGPQs w.r.t. background knowledge lead to more precise lgg.

Conclusion

Our results confirm our claim that using general entailment beween RDF graphs (|= R ) and entailment between BGPQs w.r.t. background knowledge (|= R,O ) instead of simple entailment (|=) yield more precise lggs. Indeed, exploiting ontological constraints help finding common super-classes and properties to be used in lggs in place of the different ones used in input graphs and queries. When simple entailment is used during graph lgg computation, some generalizations are missing while in the case of query lgg computation, properties and classes are generalized using variables. Therefore, the more heterogeneous input graphs and queries are, the more such common super-classes and properties may be used in their lgg computation and the more the gain in precision of their lgg is high. For homogeneous input graphs and queries, while less striking, the gain in precision is significant in general, as our experiments show.

Introduction

The problem of computing some least general generalization of a set of descriptions has been introduced by G. Plotkin in the early 70's [Plotkin, 1970, Plotkin, 1971]. Since then, this problem has been investigated within the Inductive Logic Programming (ILP), the Knowledge Representation (KR) and the Semantic Web (SW) fields.

In this chapter, we survey the related works from these research fields, and relate them to the contributions of this thesis.

Inductive Logic Programming

G. Plotkin introduced the problem of computing an lgg in a First Order Logic setting.

He first considered clauses as descriptions and θ-subsumption, a restricted form of logical implication now typical of the ILP field, as generalization/specialization relation [Plotkin, 1970]. Then, he also considered finding an lgg of clauses in presence of background knowledge formalized as a set of ground literals (positive or negative facts) [Plotkin, 1971]. These two foundational works and extensions to standard implication [Buntine, 1988, Nienhuys-Cheng and de Wolf, 1996, Nienhuys-Cheng and de Wolf, 1997], constitute the basis of many ILP systems [Raedt, 2008]; recent ILP works build on them [Lisi, 2007, Raedt, 2008, Kuzelka et al., 2012].

The main idea of [Plotkin, 1970, Plotkin, 1971, Buntine, 1988, Nienhuys-Cheng and de Wolf, 1996, Nienhuys-Cheng and de Wolf, 1997] is to compute an lgg of two clauses as the clause made of all the possible anti-unifications between the literals of the two clauses; across these anti-unifications, a same pair of literal terms is anti-unified to a same value by assuming given a injective naming function. Further, to take into account background knowledge formalized as ground literals, their lgg can to be computed as described above, not from the input clauses themselves, but from their saturation with these literals obtained through resolution.

Our cover graph-based lgg of RDF graphs and cover query-based lgg of BGPQs can be seen as the adaptation of the above techniques for clauses and θ-subsumption or standard implication to our Semantic Web setting. To this aim, we first defined the notion of anti-unification for triples and for triple patterns. Then, we established that the cover graph of two RDF graphs (resp. cover query of two BGPQs), defined as the result of all the possible anti-unifications between the triples of the input RDF graphs (resp. the triple patterns of the input BGPQs), is an lgg of these input RDF graphs (resp. BGPQs) w.r.t. simple entailment between RDF graphs (resp. BGPQs). Further, when the input RDF graphs (resp. BGPQs) are saturated using a set of entailment rules R (resp. a set of entailment rules R and a set of RDFS ontological constraints O), the cover graph is an lgg of the input RDF graphs w.r.t. standard entailment between RDF graphs |= R (resp. an lgg of the input BGPQs w.r.t. entailment between BGPQs endowed with background knowledge |= R,O ).

Knowledge Representation

Computing an lgg has started receiving consideration in the Knowledge Representation field in the early 90's, where the notion of lgg was rebaptized least common subsumer (lcs) [START_REF] Cohen | Computing least common subsumers in description logics[END_REF]. This problem has been mainly studied for Description Logics (DLs), and also for Conceptual Graphs (CGs).

Description logics

Computing an lgg of DL formulae, called concepts, has been studied for many DLs, in particular the EL DL and extensions thereof [Küsters, 2001, Baader et al., 2007, Zarrieß and Turhan, 2013] that shares some expressivity with RDF.

The EL setting translates into particular tree-shaped RDF graphs, which may feature RDFS subclass and domain constraints, and for which RDF entailment is limited to the use of these two constraints only. An

G(C 1 C 2 , b) = G(C 1 , b) ∪ G(C 2 , b) for an EL conjunction C 1 C 2 .
Further, the EL constraints A 1 A 2 and ∃r.

A correspond to (A 1 , sc , A 2 ) and (r, ← d , A) respectively. In these equivalent RDF and EL fragments, the EL technique that computes an lgg of EL concepts, which is an EL concept, exploits the underlying tree structure of EL concepts: the output concept is built by a simultaneous root-to-leaves traversal of the input concepts. We remark that it provides only a (non least general) generalization of their corresponding tree-shaped RDF graphs w.r.t. the problem we study, since clearly the (minimal) lgg of tree-shaped RDF graphs is a forest-shaped RDF graph in general as detailed in Example 2 .

Conceptual graphs

Computing the lgg of CGs is briefly discussed in [START_REF] Chein | Graph-based Knowledge Representation -Computational Foundations of Conceptual Graphs[END_REF] for the so-called simple CGs. In particular, simple CGs with unary and binary relations correspond to particular RDF graphs (e.g., a property URI in a triple cannot be the subject or object of another triple, a class -URI or blank node -in a τ triple cannot be the subject of another τ triple nor the subject or object of another non-τ triple, etc.), which may feature the four RDFS constraints expressed as the support of the simple CGs (lattices of inclusion between unary relations and between typed binary relations), and for which entailment rules are just those exploiting these RDFS contraints [START_REF] Baget | Translations between RDF(S) and conceptual graphs[END_REF].

The CG technique for computing an lgg of two simple CGs, which is a simple CG, relies on a categorial product [START_REF] Imrich | Topics in Graph Theory: Graphs and Their Cartesian Product[END_REF] between the input graph nodes [START_REF] Chein | Graph-based Knowledge Representation -Computational Foundations of Conceptual Graphs[END_REF]. This product is the CG counterparts to all the possible anti-unifications of triples of our RDF graphs (resp. of triple patterns of our BGPQs). In contrast to our approach, and due to the simplicity of entailment in simple GCs, the input GCs do not need to be saturated w.r.t. their support; instead, required entailment are computed from the support while computing the categorial product of the input CGs.

In these equivalent RDF and CG fragments, we may interchangeably compute lggs with the CG technique in [START_REF] Chein | Graph-based Knowledge Representation -Computational Foundations of Conceptual Graphs[END_REF] or our for RDF graphs.

Semantic Web

Recently, the problem of computing an lgg has started gaining interest of the Semantic Web field with the aim of finding commonalities between RDF graphs [START_REF] Colucci | Common subsumbers in RDF[END_REF], Colucci et al., 2016, El Hassad et al., 2017a] and between SPARQL queries [START_REF] Lehmann | Autosparql: Let users query your knowledge base[END_REF], Bühmann et al., 2016, El Hassad et al., 2017e, El Hassad et al., 2017c].

RDF

In RDF, computing an lgg has been first studied for particular RDF graphs, called r-graphs [START_REF] Colucci | Common subsumbers in RDF[END_REF], Colucci et al., 2016]. In this setting, entailment rules are ignored: r-graphs are only compared through simple entailment (|=).

An r-graph is an extracted subgraph of an RDF graph G, rooted in the G value r and comprising the G triples reachable from r through directed paths of length at most n. Such a rooted and directed r-graph can be defined recursively as S(G, r, n), with:

-S(G, r, 0) = ∅ -S(G, r, n) = (r,p,r )∈G {(r, p, r )} ∪ S(G, r , n -1) ∪ S(G, p, n -1) Intuitively, this purely structural definition of r-graph attempts carrying G's knowledge about r. lggs of r-graphs allow finding the commonalities between single root entities, while with the general RDF graphs we further allow finding the commonalities between sets of multiple interrelated entities [El Hassad et al., 2017a].

The technique for computing an lgg of two r-graphs, which is an r-graph, exploits their rooted and directed structure: it starts from their respective root and traverses them simultaneously considering triples reachable through directed paths of increasing size, while incrementally constructing an r-graph lgg. In contrast, the general RDF graphs we consider in [El Hassad et al., 2017a] have no topological constraints. Our technique blindly traverses the input RDF graphs to anti-unify their triples with same property, and captures their common structure across these anti-unifications thanks to the consistent naming scheme we devised for the blank nodes they generate. Further, when we ignore RDF entailment, computing lggs of r-graphs or of RDF graphs have the same worst-case time complexity (O(|G 1 |×|G 2 |), with G 1 , G 2 the input RDF graphs). This is for instance the case for the following star-shaped RDF graphs, which are trees, r-graphs and RDF graphs, G 1 = {(r 1 , p, s

G lgg = {(b r 1 r 2 , p, b s 1 1 s 1 2 ), . . . , (b r 1 r 2 , p, b s m 1 s n 2 )}.
Moreover, as noted in [START_REF] Colucci | Defining and computing least common subsumers in RDF[END_REF], the computed r-graphs lggs are only (non least general) generalizations of r-graphs w.r.t. the standard semantics of RDF graphs defined upon entailment between RDF graphs using entailment rules (|= R ). For instance, recall Example 2 above, in which tree-shaped RDF graphs have a forestshaped RDF graph lgg. Tree-shaped RDF graphs are particular r-graphs, while their forest-shaped lgg is not.

Therefore, our contribution in Chapter 2 significantly advance the state of the art by considering (i) general RDF graphs (i.e., without imposing structural restrictions) and (ii) the standard semantics of RDF graphs based on entailment (i.e., we take into account any set of entailment rules from the RDF standard).

SPARQL

Computing an lgg has been investigated in SPARQL for particular Basic Graph Pattern queries (BGPQs), called unary tree-shaped BGPQ (UT-BGPQ) [Lehmann andBühmann, 2011, Bühmann et al., 2016], whose single answer variable is the root of its tree-shaped body.

For example, let us consider the graphs G 1 and G 2 in Figure 6.1. Clearly they are tree-shaped graphs and can be considered as graph representations of the two UTBGP Further, in this setting, entailment rules are ignored: query are only compared through simple entailment (|=).

An lgg of UTBGPQs, which is a UTBGPQ, is computed by a simultaneous root-toleaves traversal of the input queries and returns a UTBGPQ. This technique yields only a (non least general) generalization of their corresponding tree-shaped queries w.r.t. the problem we study in [El Hassad et al., 2017c]. The minimal cover query-based lgg of UTBGPQ is clearly a forest-shaped BGPQ. Similarly as for the EL description logic above, it can be shown that our technique for computing lgg of BGPQ can be used to compute the UTCQ lgg of UTCQs as shown in Example 3.

Example 3. Let us consider the two queries whose bodies are the tree-shaped RDF graphs G 1 and G 2 of Example 1. Q 1 (x 1 ) ← {(x 1 , w, x 11 ), (x 1 , s, x 12 )} and Q 2 (x 2 ) ← {(x 2 , w, x 21 ), (x 21 , s, x 211 )}. Their lgg is the forest-shaped BGPQ Q lgg (x) ← {(x, w, y), (z, s, t)} while their UTBGPQ lgg is the strictly more general tree-shaped RDF graph: Q (x) ← {(x, w, y)}.

Therefore, our contribution in Chapter 3 significantly advances the state of the art on computing an lgg of BGP queries, by considering (i) general BGPQs and (ii) any set of entailment rules and possibly extra background knowledge.

Conclusion

In this chapter, we pointed out that the contributions of this thesis build on old ideas developed in ILP to compute then lgg of first order clause [Plotkin, 1970, Plotkin, 1971, Buntine, 1988, Nienhuys-Cheng and de Wolf, 1996, Nienhuys-Cheng and de Wolf, 1997].

Also, we highlighted that in the Semantic Web field, the contributions of this thesis significantly advance the state of the art by considering RDF graphs and BGPQs in all their generality, i.e., we do not impose structural restrictions on them, nor on their semantics: we use standard entailment between RDF graphs (|= R ) to compute an lgg of RDF graphs and a well-founded extension of standard entailment between BGPQs endowed with background knowledge (|= R,O ) to compute an lgg of BGPQs.

Conclusion

The goal of this thesis was to investigate the problem of finding the commonalities between descriptions of data and knowledge, formalized as their least general generalization (lgg), a well-known reasoning task in Machine Learning, in the setting of the popular W3C Semantic Web standards: the RDF data model and its associated SPARQL query language (Chapter 1).

The main contributions of this thesis involve the definition, characterization and computation of an lgg of RDF graphs (Chapter 2) and of conjunctive SPARQL queries (Chapter 3), a.k.a. Basic Graph Pattern queries (BGPQs). Crucially, our results are faithful to the RDF and SPARQL standards: by contrast to the literature, we do not restrict the structure nor semantics of RDF graphs and BGPQs (Chapter 6). Further, for BGPQs which do not carry background knowledge, we devised a well-founded generalization of standard entailment between BGPQs, in order to compute more precise lggs when background knowledge is available as RDFS ontological constraints, i.e., as it is expressed within RDF graphs.

Other contributions of the thesis include a set of algorithms that allows computing an lgg of RDF graphs and of BGPQs based on our main technical contributions (Chapter 4). In particular, in constrast to BGPQs, RDF graphs may not fit in memory. We therefore provide algorithms for small-to-huge RDF graphs, i.e., that fit in memory, in a data management systems, and in a MapReduce cluster.

Finally, this thesis provides an experimental assessment of our technical and algorithmic contributions using synthetic LUBM data and real DBpedia data (Chapter 5).

Our experiments rely on the definition of two metrics in order to measure the gain in precision that taking into account entailment rules yields when learning an lgg of RDF graphs, and both entailment rules and background knowledge yield when learning an lgg of BGPQs.

Perspectives

Redundancy elimination

As a short-term perspective, we plan defining heuristics in order to efficiently prune out as much as possible redundant triples from our cover graph/query-based lggs, while computing them. Indeed, as for instance Figure 2.2 (Chapter 2, page 33) and Figures 3.5 (Chapter 3,pages 46) show, our technique produces many redundant triples. Such practical redundancy elimination may limit the a posteriori effort using techniques from the literature, e.g., [START_REF] Pichler | Complexity of redundancy detection on RDF graphs in the presence of rules, constraints, and queries[END_REF], Pichler et al., 2010, Meier, 2008].

Removing redundancy within lggs of RDF graphs would allow having more compact and readable lggs; removing redundancy within lggs of BGPQs may also significantly improve their evaluation time.

Learning commonalities in DL-Lite

As a midterm perspective, we plan to study the problem of learning lggs in the setting of the DL-Lite R Descriptions Logics (DLs) [START_REF] Calvanese | Tractable reasoning and efficient query answering in description logics: The dl-lite family[END_REF], a first order language which underpins the OWL2 QL profile of the Web Ontology Language, the other Semantic Web data model by W3C, which can also be queried using SPARQL.

In this setting, we want to define, characterize and compute the commonalities between DL-Lite R knowledge bases (KBs), i.e., an lgg of them, as well as of BGPQs when background knowledge is available as DL-Lite R ontological constraints.

However, adapting the cover graph and cover query-based techniques devised in this thesis from our RDF/SPARQL setting to the DL-Lite R /SPARQL setting is not obvious (at least to us), and currently open. Indeed, in this thesis, the semantics of input RDF graphs and of BGPQs is taken into account through their saturations that materializes their finite semantics. Unfortunately, the saturation (a.k.a. chase) of a DL-Lite R KB, as well as that of a BGPQ w.r.t. DL-Lite R ontological constraints, in infinite in general as the next example shows.

Example 4. Consider the DL-Lite R KB made of the single fact stating that a is a person P erson(a)

and the constraints (here written in first order logic to facilitate the understanding to the non-expert) stating that a person has a parent, and that a parent is a person: ∀x(P erson(x) ⇒ ∃y parent(x, y)) ∀x(∃y parent(y, x) ⇒ P erson(x))

Clearly, the saturation of this KB is infinite because it admits as logical consequences:

P erson(a), parent(a, y 1 ), P erson(y 1 ), parent(y 1 , y 2 ), P arent(y 2 ), . . . where the y 1≤i≤∞ 's are existential variables.

G 1 : "http : //dbpedia.org/resource/Airbus" "http : //www.w3.org/1999/02/22-rdf -syntax-ns#type" "http : //dbpedia.org/ontology/Organisation", "http : //dbpedia.org/resource/Airbus Group" "http : //www.w3.org/1999/02/22-rdf -syntax-ns#type" "http : //dbpedia.org/ontology/Organisation", "http : //dbpedia.org/resource/Airbus" "http : //dbpedia.org/ontology/locationCountry" "http : //dbpedia.org/resource/F rance", "http : //dbpedia.org/resource/Airbus" "http : //dbpedia.org/ontology/parentCompany" "http : //dbpedia.org/resource/Airbus Group". G 2 : "http : //dbpedia.org/resource/Hoover F ield" "http : //www.w3.org/1999/02/22-rdf -syntax-ns#type" "http : //dbpedia.org/ontology/Airport", "http : //dbpedia.org/resource/Hoover F ield" "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation" "http : //dbpedia.org/resource/W ashington metropolitan area", "http : //dbpedia.org/resource/Hoover F ield" "http : //dbpedia.org/ontology/city" "http : //dbpedia.org/resource/W ashington metropolitan area", "http : //dbpedia.org/resource/Hoover F ield" "http : //dbpedia.org/ontology/owner" "http : //dbpedia.org/resource/Henry Berliner", "http : //dbpedia.org/resource/Henry Berliner" "http : //www.w3.org/1999/02/22-rdf -syntax-ns#type" "http : //dbpedia.org/ontology/P erson". G 3 : "http : //dbpedia.org/resource/Help! (song)" "http : //www.w3.org/1999/02/22-rdf -syntax-ns#type" "http : //dbpedia.org/ontology/Single", "http : //dbpedia.org/resource/Help! (song)" "http : //dbpedia.org/ontology/musicalArtist" "http : //dbpedia.org/resource/T he Beatles", "http : //dbpedia.org/resource/T he Beatles" "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation" "http : //dbpedia.org/resource/Liverpool", "http : //dbpedia.org/resource/T he Beatles" "http : //dbpedia.org/ontology/genre" "http : //dbpedia.org/resource/Rock music". G 4 : "http : //dbpedia.org/resource/T he Skeleton Dance" "http : //www.w3.org/1999/02/22-rdf -syntax-ns#type" "http : //dbpedia.org/ontology/Cartoon", "http : //dbpedia.org/resource/T he Skeleton Dance" "http : //dbpedia.org/ontology/animator" "http : //dbpedia.org/resource/Roy O. Disney", "http : //dbpedia.org/resource/T he Skeleton Dance" "http : //dbpedia.org/ontology/director" "http : //dbpedia.org/resource/W alt Disney", "http : //dbpedia.org/resource/Roy O. Disney" "http : //dbpedia.org/ontology/birthP lace" "http : //dbpedia.org/resource/Chicago", "http : //dbpedia.org/resource/W alt Disney" "http : //dbpedia.org/ontology/birthP lace" "http : //dbpedia.org/resource/Chicago", "http : //dbpedia.org/resource/Roy O. Disney" "http : //dbpedia.org/ontology/predecessor" "http : //dbpedia.org/resource/W alt Disney". G 5 : "http : //dbpedia.org/resource/W innie the P ooh and the Honey T ree" "http : //www.w3.org/1999/02/22-rdf -syntax-ns#type" "http : //dbpedia.org/ontology/F ilm", "http : //dbpedia.org/resource/W innie the P ooh and the Honey T ree" "http : //dbpedia.org/ontology/starring" "http : //dbpedia.org/resource/Bruce Reitherman", "http : //dbpedia.org/resource/W innie the P ooh and the Honey T ree" "http : //dbpedia.org/ontology/director" "http : //dbpedia.org/resource/W olf gang Reitherman", "http : //dbpedia.org/resource/Bruce Reitherman" "http : //dbpedia.org/ontology/birthP lace" "http : //dbpedia.org/resource/Burbank, Calif ornia", "http : //dbpedia.org/resource/W olf gang Reitherman" "http : //dbpedia.org/ontology/deathP lace" "http : //dbpedia.org/resource/Burbank, Calif ornia", "http : //dbpedia.org/resource/Bruce Reitherman" "http : //dbpedia.org/ontology/parent" "http : //dbpedia.org/resource/W olf gang Reitherman". G 6 : "http : //dbpedia.org/resource/T he P ink Diamond" "http : //www.w3.org/1999/02/22-rdf -syntax-ns#type" "http : //dbpedia.org/ontology/F ilm", "http : //dbpedia.org/resource/T he P ink Diamond" "http : //dbpedia.org/ontology/starring" "http : //dbpedia.org/resource/Xenia Desni", "http : //dbpedia.org/resource/T amara Desni" "http : //dbpedia.org/ontology/deathP lace" "http : //dbpedia.org/resource/F rance", "http : //dbpedia.org/resource/T amara Desni" "http : //dbpedia.org/ontology/parent" "http : //dbpedia.org/resource/Xenia Desni". G 7 : "http : //dbpedia.org/resource/T oo M uch Sun" "http : //www.w3.org/1999/02/22-rdf -syntax-ns#type" "http : //dbpedia.org/ontology/F ilm", "http : //dbpedia.org/resource/T oo M uch Sun" "http : //dbpedia.org/ontology/starring" "http : //dbpedia.org/resource/Robert Downey, Jr.", "http : //dbpedia.org/resource/T oo M uch Sun" "http : //dbpedia.org/ontology/director" "http : //dbpedia.org/resource/Robert Downey, Sr.", "http : //dbpedia.org/resource/Robert Downey, Jr." "http : //dbpedia.org/ontology/birthP lace" "http : //dbpedia.org/resource/M anhattan", "http : //dbpedia.org/resource/Robert Downey, Sr." "http : //dbpedia.org/ontology/birthP lace" "http : //dbpedia.org/resource/N ew Y ork City", "http : //dbpedia.org/resource/Robert Downey, Jr." "http : //dbpedia.org/ontology/parent" "http : //dbpedia.org/resource/Robert Downey, Sr.". G 8 : "http : //dbpedia.org/resource/T he Boy and the P irates" "http : //www.w3.org/1999/02/22-rdf -syntax-ns#type" "http : //dbpedia.org/ontology/F ilm", "http : //dbpedia.org/resource/T he Boy and the P irates" "http : //dbpedia.org/ontology/starring" "http : //dbpedia.org/resource/Susan Gordon", "http : //dbpedia.org/resource/T he Boy and the P irates" "http : //dbpedia.org/ontology/director" "http : //dbpedia.org/resource/Bert I. Gordon", "http : //dbpedia.org/resource/Susan Gordon" "http : //dbpedia.org/ontology/deathP lace" "http : //dbpedia.org/resource/T eaneck, N ew Jersey", "http : //dbpedia.org/resource/Susan Gordon" "http : //dbpedia.org/ontology/parent" "http : //dbpedia.org/resource/Bert I. Gordon". G 9 : "http : //dbpedia.org/resource/Alexandra Cousteau" "http : //dbpedia.org/ontology/parent" "http : //dbpedia.org/resource/P hilippe Cousteau", "http : //dbpedia.org/resource/P hilippe Cousteau" "http : //dbpedia.org/ontology/birthP lace" "http : //dbpedia.org/resource/F rance", "http : //dbpedia.org/resource/V oyage to the Edge of the W orld" "http : //dbpedia.org/ontology/director" "http : //dbpedia.org/resource/M arshall F laum", "http : //dbpedia.org/resource/V oyage to the Edge of the W orld" "http : //dbpedia.org/ontology/starring" "http : //dbpedia.org/resource/P hilippe Cousteau", "http : //dbpedia.org/resource/V oyage to the Edge of the W orld" "http : //www.w3.org/1999/02/22-rdf -syntax-ns#type" "http : //dbpedia.org/ontology/F ilm".

Figure 1 . 2 -

 12 Figure 1.1 -Sample RDF graph G.

Figure 1 .

 1 Figure 1.1 displays the usual representation of the RDF graph G made of the seven above-mentioned triples, which are called the explicit triples of G. A triple (s, p, o) corresponds to a p-labeled directed edge from the s node to the o node: s p -→ o. Explicit triples are shown as solid edges, while the implicit ones, which are derived using ontological constraints (see below), are shown as dashed edges. Importantly, it is worth noticing the deductive nature of ontological constraints, which begets implicit triples within an RDF graph. For instance, in Figure 1.1, the constraint (hasContactAuthor, sp , hasAuthor) together with the triple (b, hasContactAuthor, b 1 ) imply the implicit triple (b, hasAuthor, b 1 ), which, further, with the constraint (hasAuthor, → r , Researcher) yields another implicit triple (b 1 , τ, Researcher).

  that allows comparing RDF graphs based on their explicit triples only. More formally, given two RDF graphs G and G , G simply entails G , denoted G |= G , if there exists a homomorphism φ from the blank nodes of G to G values (URIs, blank nodes and literals), i.e., from Bl(G ) to Val(G), such that [G ] φ ⊆ G, where [G ] φ is the RDF graph obtained from G by replacing every blank node b with its image φ(b).

Figure 1 .

 1 Figure 1.2 shows an RDF graph G entailed by the RDF graph G in Figure 1.1 w.r.t. the entailment rules displayed in Table1.2. In particular, G |= R G holds for the homomorphism φ such that: φ(b) = b and φ(b 2 ) = "LGG in SPARQL". By contrast, when R is empty, this is not the case (i.e., G |= R G ), as the dashed edges in G are not materialized by saturation, hence the G triple (b, τ, Publication) cannot have an image in G through some homomorphism.

Figure 1 .

 1 1 is: -{ b, ConfPaper } for R = ∅, i.e., considering only the explicit triples in Figure 1.1; -{ b, ConfPaper , b, Publication , b 1 , Researcher } for R the set of entailment

Figure 2 . 1 -

 21 Sample RDF graphs G 1 , G 2 and G lgg , with G lgg the minimal lgg of G 1 and G 2 ; their implicit triples (i.e., derived by the rules in Table1.2) are shown as dashed edges.

Figure 2 .

 2 Figure 2.1 displays two RDF graphsG 1 and G 2, as well as their minimal lgg G lgg (with lowest number of triples), when we consider the RDF entailment rules shown in Table1.2. G 1 describes a conference paper i 1 with title "Disaggregations in Databases" and author Serge Abiteboul, who is a researcher; also conference papers are publications. G 2 describes a journal paper i 2 with title "Computing with First-Order Logic", contact author Serge Abiteboul and author Victor Vianu, who are researchers; moreover, journal papers are publications and having a contact author is having an author. G lgg states that their common information comprises the existence of a resource (b i 1 i 2 ) having some type (b C(onf)P(aper)J(our)P(aper) ), which is a particular case of publication, with some title (b D(iD)C(wFOL) ) and author Serge Abiteboul, who is a researcher.

Figure 2 . 2 (

 22 top). The first above-mentioned G triple results from anti-unifying i 1 and i 2 into b i 1 i 2 , and, ConfPaper and JourPaper into b CPJP .

Figure 2 .

 2 Figure 2.2 (bottom) displays a cover graph-based lgg of the RDF graphs G 1 and G 2 in Figure 2.1 w.r.t. the entailment rules shown in Table 1.2. In contrast to Figure 2.2 (top), which shows an lgg of the same RDF graphs when RDF entailment rules are

  . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.2 Comparing Queries w.r.t. Ontological Constraints . . . . . . 39 3.3 Learning the lgg of Queries w.r.t. Ontological Contraints . 42 3.4 Computing an lgg of Queries w.r.t. ontological constraints 44 3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

Figure 3 . 3 -

 33 Figure 3.3 -Saturations of the BGPQs q 1 and q 2 from Figure 3.1 w.r.t. O from Figure 3.2. Triples shown in green are added by saturation.

Figure 3 .

 3 Figure 3.3 illustrates the above notion of saturation using the BGPQs and RDFS contraints from Figure 3.2.

Figure 3 .

 3 Figure 3.4 -Characterization of the body of a saturated BGPQ q w.r.t. a set O of RDFS constraints

Figure 3 . 1 ∞ 3 . 3 .

 3133 Figure 3.5 (bottom) displays the cover query of the BGPQs q 1 ∞ O and q 2 ∞ O shown in Figure 3.3. It is therefore (Theorem 10) an lgg of the BGPQs q 1 and q 2 , shown in Figure 3.1 w.r.t. the set O of RDFS constraints, shown in Figure 3.2, using the RDF entailment rules shown in Table 1.2.Figure3.5 exemplifies the benefits of taking into account extra ontological constraints modeling background knowledge when identifying the commonalities between queries, thus of endowing the RDF relation of generalization/specialization between

  . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.2 Least general anti-unification . . . . . . . . . . . . . . . . . . 51 4.3 lggs of RDF graphs . . . . . . . . . . . . . . . . . . . . . . . . 52 4.3.1 Handling large RDF graphs using DMSs . . . . . . . . . . . . 53 4.3.2 Handling huge RDF graphs using MapReduce . . . . . . . . . 55 4.4 lggs of BGPQs . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 4.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

Algorithm 2

 2 Cover graph of two RDF graphs: lgg4g In: RDF graphs G 1 and G 2 Out: G is the cover graph of G 1 and G 2 1: G ← ∅ 2: for all T 1 = (s 1 , p 1 , o 1 ) ∈ G 1 do 3:

Algorithm 3

 3 Cover graph of two RDF graphs: lgg4g-dms In: cursor c 1 on RDF graph G 1 , cursor c 2 on RDF graph G 2 , write access to an empty RDF graph G, integer n Out: G is the cover graph of G 1 and G 2 1: c 1 .init() c 1 at beginning of G 1 2: while B 1 = c 1 .next(n) do fetch next n G 1 triples

  . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 5.2 Gain in precision metrics . . . . . . . . . . . . . . . . . . . . . 60 5.2.1 The case of RDF graphs . . . . . . . . . . . . . . . . . . . . . 60 5.2.2 The case of BGPQs . . . . . . . . . . . . . . . . . . . . . . . 61 5.3 Experimental setting . . . . . . . . . . . . . . . . . . . . . . . 62 5.3.1 Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 5.3.2 Hardware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 5.3.3 Datasets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 5.4 lggs of RDF graphs . . . . . . . . . . . . . . . . . . . . . . . . 65 5.5 lggs of BGPQs . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 5.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

  EL concept C recursively translates into the RDF graph rooted in the blank node b r returned by the call G(C, b r ), with: -G( , b r ) = ∅ for the universal EL concept , -G(A, b r ) = {(b r , τ, A)} for an atomic EL concept A, -G(∃r.C, b r ) = {(b r , r, b )} ∪ G(C, b ), with b a fresh blank node, for an EL existential restriction ∃r.C, and -

Example 1 .

 1 Let us consider the two EL concepts C 1 ≡ ∃w. ∃s. and C 2 ≡ ∃w.∃s. where w and s are shorthands for the worksWith and hasPhdStudent roles, respectively. C 1 represents resources/individuals working with somebody and supervising a PhD student, while C 2 denotes resources working with somebody who supervises a PhD student. The corresponding tree RDF graphs rooted in b 1 and b 2 respectively are G 1 = G(C 1 , b 1 ) = {(b 1 , w, b 11 ), (b 1 , s, b 12 )} and G 2 = G(C 2 , b 2 ) = {(b 2 , w, b 21 ), (b 21 , s, b 211 )} (see Figure 6.1).

2 Figure 6 . 1 -

 261 Figure 6.1 -RDF graph representation of EL concepts.

Example 2 .

 2 Let us consider the two tree-shaped RDF graphs G 1 and G 2 of Example 1. Their RDF graph lgg is the general forest-shaped RDF graph G = {(b b 1 b 2 , w, b b 11 b 21 ), (b b 1 b 21 , s, b b 12 b 211 )} (see its graphical representation displayed in Figure 6.2) while the RDF graph corresponding to their EL lgg is the strictly more general tree-shaped RDF graph: G = {(b b 1 b 2 , w, b b 11 b 21 )}. The latter corresponds to the G subgraph rooted in b b 1 b 2 , see Figure 6.2 (left), that generalizes the roots b 1 of G 1 and b 2 of G 2 . Further, it can be shown that our technique for general RDF graph can be used to compute the lgg of EL concepts as shown in Example 2 above. Roughly speaking, given two EL concepts C 1 , C 2 and their corresponding tree-shaped RDF graphs G(C 1 , b 1 ), G(C 2 , b 2 ), the EL lgg corresponds to the tree-shaped RDF graph rooted in b b 1 ,b 2 within the forest-shaped cover graph of G(C 1 , b 1 ) and G(C 2 , b 2 ).

Figure 6 . 2 -

 62 Figure 6.2 -G lgg : an lgg of RDF graphs.

queries q 1

 1 (b 1 ) ← (b 1 , w, b 11 ), (b 1 , s, b 12 ) and q 2 (b 2 ) ← (b 2 , w, b 21 ), (b 21 , s, b 211 ) whose answer variables are b 1 and b 2 respectively.

  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 7.2 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 7.2.1 Redundancy elimination . . . . . . . . . . . . . . . . . . . . . 80 7.2.2 Learning commonalities in DL-Lite . . . . . . . . . . . . . . . 80

Figure A. 1 -

 1 Figure A.1 -DBPEDIA graphs \ O (A).

Figure A. 2 -

 2 Figure A.2 -DBPEDIA graphs \ O (B).

Table 1 .

 1 1 -RDF & RDFS statements.

	Rule	Entailment rule
	rdfs2

Table 1 .

 1

	2 -Sample RDF entailment
	rules [W3C-RDFS, 2014].

specification [W3C-RDF, 2014], belong to (U ∪ B) × U × (U ∪ L ∪ B); we only consider such triples hereafter.

  Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.2 Defining the lgg of RDF graphs . . . . . . . . . . . . . . . . . 28 2.3 Computing an lgg of RDF graphs . . . . . . . . . . . . . . . 31 2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

	Chapter 2
	Finding Commonalities between
	RDF graphs
	Contents
	2.1

  Cover graphs of G 1 and G 2 in Figure2.1 (top) and of their saturations w.r.t. the entailment rules in Table 1.2. Triples shown in gray are part of the graph but are redundant w.r.t. those shown in pink.and are met when all the triples of the two input graphs use the same property URI (i.e., every pair of G 1 and G 2 triples begets a G triple).The main theorem below generalizes Theorem 2 in order to take into account any set of entailment rules from the RDF standard. It states that it is sufficient to compute the cover graph of the saturations of the input RDF graphs, instead of the input RDF graphs themselves.Theorem 3. Let G 1 and G 2 be two RDF graphs, and R a set of RDF entailment rules. The cover graph G of G ∞ 1 and G ∞ 2 exists and is an lgg of G 1 and G 2 .Proof. Clearly, by definition, a cover graph G of G ∞ 1 and G ∞ 2 always exists; it may be empty when the triples in G ∞ 1 and those in G ∞ 2 have no property URI in common. Now, we show that G is a generalization of G 1 and G 2

Proposition 2. The cover graph of two RDF graphs G 1 and G 2 can be computed in O(|G 1 | × |G 2 |); its size is bounded by |G 1 | × |G 2 |.

  Least general anti-unification: lgau In: T 1 = (t 1 , . . . , t n ) and T 2 = (t 1 , . . . , t n ), boolean bnodes Out: least general anti-unification T of T 1 and T 2 1: for i = 1 to n do for each pair of ith attributes

	2: 3:	if t i = t i and t i ∈ U ∪ L then t T i ← t i	generalization of a constant by itself
	4:	else if bnodes then	cover graph case
	5: 6:	t T i ← b t i t i else	generalization by a blank node cover query case
	7: 8: return (t T t T i ← v t i t i 1 , . . . , t T n )	generalization by a variable

T 1 , . . . , t T n ) of two n-ary tuples of RDF values (t 1 , . . . , t n ) and (t 1 , . . . , t n ), made of constants (URIs and 51 Algorithm 1

  prises 884k triples before saturation, including a subset O LUBM of 242 RDFS constraints. The saturation of G LUBM comprises 1.08M triples. The total time for the generation of G LUBM , its saturation and its loading into the PostgreSQL TripleLUBM(s,p,o) table is about 1 hour. To build the RDF graph G DBpedia , we picked four complementary DBpedia files 3 . The RDF graph G DBpedia comprises 41.18M triples, including a subset O DBpedia of 30.31k RDFS constraints. The saturation of G DBpedia comprises 78.14M triples. The total time of the saturation of G DBpedia and its loading into the PostgreSQL Triple(s,p,o) table is about 24 hours.

2. http://swat.cse.lehigh.edu/projects/lubm/

Table 5 .

 5 2 -Characteristics of our test BGPQs (top) and of their saturations w.r.t. LUBM constraints (bottom); times are in ms.

	s shape		star star graph graph star	tree	graph	star	star
	|body(Q i )|		3	3	4	3	2	4	6	2	3
	number of URI/variable occurrence in Q	5/4 5/4	5/7	4/5	3/3	6/6	7/11	2/4	5/4
	|Q i (G LUBM )|		123	41	869	0	269 41 751	79	14 252 16
	|body(Q i	∞ OLUBM )|		8	9	11	7	6	8	14	10	8
	Time to compute Q i	∞ OLUBM	24	23	23	21	22	22	21	27	22

Table 5 .

 5

	s shape		tree tree	tree	graph graph graph graph graph
	|body(Q i )|		4	6	4	6	4	6	6	6
	Number of URI/variable occurrence in Q i	7/5 9/9	5/7	7/11	5/7	9/9	9/9	9/9
	|Q i (G DBpedia )|		77	0	41 695	13	6	0	1	0
	|body(Q i	∞ ODBpedia )|		16	19	19	23	16	23	23	23
	Time to compute Q i	∞ ODBpedia	666 643	677	734	681	706	697	736

3 -Characteristics of our test BGPQs (top) and of their saturations w.r.t. DBpedia constraints (bottom); times are in ms.

Table 5 .

 5 8 -Characteristics of cover query-based lggs of 3 test queries, w or w/o using the LUBM RDFS constraints; times are in ms.

	Time to compute q lgg	6	6	5	4	7	5	4	3
	|q lgg (G LUBM )|	1 048 060 1 048 060 1 048 060 1 048 060 253 443 1 048 060 1 048 060 1 048 060
	Time to compute q OLUBM lgg	11	13	11	11	12	13	15	14
	|q OLUBM lgg (G LUBM )|	14 285	120 225	120 225	33 305	19 053	33 305	120 225	120 225
	Gain in precision	98.63	88.52	88.52	96.82	92.48	96.82	88.52	88.52

Table 5 .

 5 9 -Characteristics of cover query-based lggs of 4 test queries, w or w/o using the LUBM RDFS constraints; times are in ms.

	Time to compute q lgg	7	10	8	5	7	6	6
	|q lgg (G LUBM )|	1 048 060 1 048 060 1 048 060 1 048 060 1 048 060 1 048 060 1 048 060
	Time to compute q OLUBM lgg	17	19	18	23	18	18	20
	|q OLUBM lgg (G LUBM )|	33 305	19 053	120 225	120 225	120 225	120 225	120 225
	Gain in precision	96.82	98.18	88.52	88.52	88.52	88.52	88.52

Table 5 .

 5 10 -Characteristics of cover query-based lggs of test queries, w/ or w/o using the DBpedia RDFS constraints; times are in ms.

		compute q lgg	3	3	5	4	5	6	5	6	5
	|q lgg (G DBpedia )|		477 455 34 747 102 34 901 117 60 356 807	34	27	1221	35	70
	Time to compute q	ODBpedia lgg	13	14	14	15	15	14	14	17	18
	|q lgg ODBpedia	(G DBpedia )|		10 637	7 874 768	456 690	7 874 768	34	13	780	34	36
	Gain in precision		97.77	77.33	98.69	86.95	0	51.85 36.11	2.85	48.57

Table 5 .

 5 11 -Characteristics of cover query-based lggs of 3 test queries, w/ or w/o using the DBpedia RDFS constraints; times are in ms.

	Time to compute q lgg	5	6	6	6	10	9
	|q lgg (G DBpedia )|		34 747 102 34 901 117 34 901 117 34 901 117	70	1 977
	Time to compute q	ODBpedia lgg	22	23	23	25	27	29
	|q lgg ODBpedia	(G DBpedia )|		7 874 768	615 339	7 874 779	4 537 824	36	1 701
	Gain in precision		77.33	98.23	77.43	86.99	48.57	13.96

  Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 6.2 Inductive Logic Programming . . . . . . . . . . . . . . . . . . 71 6.3 Knowledge Representation . . . . . . . . . . . . . . . . . . . . 72 6.3.1 Description logics . . . . . . . . . . . . . . . . . . . . . . . . . 72 6.3.2 Conceptual graphs . . . . . . . . . . . . . . . . . . . . . . . . 74 6.4 Semantic Web . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 6.4.1 RDF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 6.4.2 SPARQL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 6.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

	Chapter 6
	Related Work
	Contents
	6.1

Nous utilisons l'implication standard entre les graphes RDF (|= R ) pour calculer un lgg des graphes RDF et une extension de l'implication standard entre les BGPQs dotée d'un ensemble des contraintes ontologiques (|= R,O ) pour calculer un lgg des BGPQs. Pour calculer le lgg de graphes, nous proposons trois algorithmes pour gérer des graphes de petite taille, de grande taille, ou de très grande taille avec une approche dans laquelle les graphes tiennent (i) en mémoire, (ii) dans des systèmes de gestion de bases de données ou (iii) dans uncluster MapReduce. Les requêtes et leurs lggs tenant en mémoire, l'approche considérée pour le calcul des lggs entre des requêtes étend le premier algorithme (i). Pour valider nos approches, nous avons effectué des expérimentations pour montrer le gain de précision qu'apporte une ontologie dans le calcul des lggs.En termes de perspectives, nous envisageons d'étudier des techniques pour éliminer la redondance des lggs que nous calculons, il s'agirait de définir des heuristiques afin de calculer des lggs plus compactes. Par ailleurs, nous souhaitons étudier le problème de la recherche des points communs dans OWL2 QL, le deuxième standard du web sémantique recommandé par W3C qui correspond à la logique de description DL-Lite R .

The merge of RDF graphs, performed with the RDF specific merge operator , is an RDF graph comprising the union of the input RDF graph after renaming their blank nodes with fresh ones, so that these RDF graphs do not share (thus join on) such values. Indeed, blank nodes are used to characterize the incompleteness of an RDF graph, hence are local to it (Chapter 1).

For simplicity, we assume that input and output data of an MR job is stored on disk, like in Hadoop, while it may also reside in in-memory shared data structures, like in Spark.

We use the dbpedia 2015-10.nt RDF Schema file and the instance types en.ttl, mappingbased literals en.ttl and mappingbased objects en.ttl RDF data files.

Related Work

Acknowledgements

Résumé en Français

Introduction

Acknowledgements

Acknowledgements

Résumé en Français

"http : //dbpedia.org/ontology/Language" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //www.w3.org/2002/07/owl#T hing", "http : //dbpedia.org/ontology/BusinessP erson" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/sourceConf luenceState" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/P opulatedP lace", "http : //dbpedia.org/ontology/sourceConf luenceState" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/River", "http : //dbpedia.org/ontology/sourceConf luenceState" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/SportsClub" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/Organisation", "http : //dbpedia.org/ontology/Criminal" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/Journalist" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/M ilitaryU nit" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/Organisation", "http : //dbpedia.org/ontology/map" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/P lace", "http : //dbpedia.org/ontology/map" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/Group" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //schema.org/Organization", "http : //dbpedia.org/ontology/Group" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/Organisation", "http : //dbpedia.org/ontology/GovernmentAgency" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/Organisation", "http : //dbpedia.org/ontology/N aturalP lace" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P lace", "http : //dbpedia.org/ontology/Orphan" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/Artwork" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/W ork", "http : //dbpedia.org/ontology/chief P lace" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/P opulatedP lace", "http : //dbpedia.org/ontology/chief P lace" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/P lace" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //www.w3.org/2002/07/owl#T hing", "http : //dbpedia.org/ontology/Engineer" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/P olitician" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/sourceConf luenceP osition" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //www.w3.org/2003/01/geo/wgs84 p os#SpatialT hing", "http : //dbpedia.org/ontology/sourceConf luenceP osition" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/River", "http : //dbpedia.org/ontology/sourceConf luenceP osition" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/Coach" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/mouthState" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/P opulatedP lace", "http : //dbpedia.org/ontology/mouthState" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/River", "http : //dbpedia.org/ontology/mouthState" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/spokenIn" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/P opulatedP lace", "http : //dbpedia.org/ontology/spokenIn" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/Language", "http : //dbpedia.org/ontology/spokenIn" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/homeport" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/P lace", "http : //dbpedia.org/ontology/homeport" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/Ship", "http : //dbpedia.org/ontology/homeport" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/parent" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#sameSettingAs", "http : //dbpedia.org/ontology/parent" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/parent" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/W riter" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/genre" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#isClassif iedBy", "http : //dbpedia.org/ontology/genre" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/Genre", "http : //dbpedia.org/ontology/N on-P rof itOrganisation" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/Organisation", "http : //dbpedia.org/ontology/HorseT rainer" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/Spacecraf t" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/M eanOf T ransportation", "http : //dbpedia.org/ontology/Athlete" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/Biomolecule" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //www.w3.org/2002/07/owl#T hing", "http : //dbpedia.org/ontology/T opicalConcept" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //www.w3.org/2002/07/owl#T hing", "http : //dbpedia.org/ontology/county" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/P opulatedP lace", "http : //dbpedia.org/ontology/county" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/massif " "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/P lace", "http : //dbpedia.org/ontology/massif " "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/SkiResort", "http : //dbpedia.org/ontology/massif " "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/P roducer" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/P ublicT ransitSystem" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/Organisation", "http : //dbpedia.org/ontology/EducationalInstitution" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/Organisation", "http : //dbpedia.org/ontology/SkiArea" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/SportF acility", "http : //dbpedia.org/ontology/P resenter" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/Island" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P opulatedP lace", "http : //dbpedia.org/ontology/capitalDistrict" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/P opulatedP lace", "http : //dbpedia.org/ontology/capitalDistrict" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/Island", "http : //dbpedia.org/ontology/capitalDistrict" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/mouthP lace" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/P opulatedP lace", "http : //dbpedia.org/ontology/mouthP lace" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/River", "http : //dbpedia.org/ontology/mouthP lace" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/animator" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#coparticipatesW ith", "http : //dbpedia.org/ontology/animator" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/Agent", "http : //dbpedia.org/ontology/animator" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/Cartoon", "http : //dbpedia.org/ontology/SiteOf SpecialScientif icInterest" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P lace", "http : //dbpedia.org/ontology/BodyOf W ater" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/N aturalP lace", "http : //dbpedia.org/ontology/arrondissement" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/P opulatedP lace", "http : //dbpedia.org/ontology/arrondissement" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/P opulatedP lace", "http : //dbpedia.org/ontology/arrondissement" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/ArchitecturalStructure" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P lace", "http : //dbpedia.org/ontology/sourceM ountain" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/M ountain", "http : //dbpedia.org/ontology/sourceM ountain" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/hubAirport" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/Airport", "http : //dbpedia.org/ontology/hubAirport" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/Airline", "http : //dbpedia.org/ontology/hubAirport" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/ruralM unicipality" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/P opulatedP lace", "http : //dbpedia.org/ontology/ruralM unicipality" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/Road", "http : //dbpedia.org/ontology/ruralM unicipality" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/areaOf Search" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/P opulatedP lace", "http : //dbpedia.org/ontology/areaOf Search" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/SiteOf SpecialScientif icInterest", "http : //dbpedia.org/ontology/areaOf Search" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/Aristocrat" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/T elevisionDirector" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/M useum" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/Building", "http : //dbpedia.org/ontology/capitalCountry" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/Country", "http : //dbpedia.org/ontology/capitalCountry" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/Island", "http : //dbpedia.org/ontology/capitalCountry" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/EthnicGroup" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //www.w3.org/2002/07/owl#T hing", "http : //dbpedia.org/ontology/City" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/Settlement", "http : //dbpedia.org/ontology/canton" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/Settlement", "http : //dbpedia.org/ontology/canton" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/Settlement", "http : //dbpedia.org/ontology/canton" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/Eukaryote" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/Species", "http : //dbpedia.org/ontology/campus" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/U niversity", "http : //dbpedia.org/ontology/campus" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/placeOf Burial" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/P lace", "http : //dbpedia.org/ontology/placeOf Burial" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/placeOf Burial" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/sourceCountry" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/Country", "http : //dbpedia.org/ontology/sourceCountry" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/Stream", "http : //dbpedia.org/ontology/sourceCountry" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/Organisation" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/Agent", "http : //dbpedia.org/ontology/Road" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/RouteOf T ransportation", "http : //dbpedia.org/ontology/owningOrganisation" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/Organisation", "http : //dbpedia.org/ontology/owningOrganisation" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //dbpedia.org/ontology/owner", "http : //dbpedia.org/ontology/Bridge" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/RouteOf T ransportation", "http : //dbpedia.org/ontology/mouthDistrict" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/P opulatedP lace", "http : //dbpedia.org/ontology/mouthDistrict" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/River", "http : //dbpedia.org/ontology/mouthDistrict" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/place" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/P opulatedP lace", "http : //dbpedia.org/ontology/place" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/M ilitaryConf lict", "http : //dbpedia.org/ontology/place" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/T heatreDirector" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/Country" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P opulatedP lace", "http : //dbpedia.org/ontology/geneLocation" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/GeneLocation", "http : //dbpedia.org/ontology/geneLocation" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/Gene", "http : //dbpedia.org/ontology/geneLocation" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/broadcastArea" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/P opulatedP lace", "http : //dbpedia.org/ontology/broadcastArea" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/Broadcaster", "http : //dbpedia.org/ontology/broadcastArea" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/P oliticianSpouse" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/alpsSupergroup" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/M ountainRange", "http : //dbpedia.org/ontology/alpsSupergroup" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/M ountain", "http : //dbpedia.org/ontology/alpsSupergroup" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/Species" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //www.w3.org/2002/07/owl#T hing", "http : //dbpedia.org/ontology/sourceP osition" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //www.w3.org/2003/01/geo/wgs84 p os#SpatialT hing", "http : //dbpedia.org/ontology/sourceP osition" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/alpsSection" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/M ountainRange", "http : //dbpedia.org/ontology/alpsSection" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/M ountain", "http : //dbpedia.org/ontology/alpsSection" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/settlement" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/P opulatedP lace", "http : //dbpedia.org/ontology/settlement" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/P lace", "http : //dbpedia.org/ontology/settlement" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/SkiResort" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/SkiArea", "http : //dbpedia.org/ontology/P arliament" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/Organisation", "http : //dbpedia.org/ontology/sourceP lace" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/P opulatedP lace", "http : //dbpedia.org/ontology/sourceP lace" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/T radeU nion" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/Organisation", "http : //dbpedia.org/ontology/Economist" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/predecessor" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#sameSettingAs", "http : //dbpedia.org/ontology/sourceDistrict" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/P opulatedP lace", "http : //dbpedia.org/ontology/sourceDistrict" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/nationality" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/Country", "http : //dbpedia.org/ontology/nationality" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/nationality" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/W ork" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //www.w3.org/2002/07/owl#T hing", "http : //dbpedia.org/ontology/M eanOf T ransportation" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //www.w3.org/2002/07/owl#T hing", "http : //dbpedia.org/ontology/P sychologist" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/M ountainRange" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/N aturalP lace", "http : //dbpedia.org/ontology/birthP lace" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/P lace", "http : //dbpedia.org/ontology/birthP lace" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/birthP lace" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/linkedT o" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/P lace", "http : //dbpedia.org/ontology/linkedT o" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/SkiResort", "http : //dbpedia.org/ontology/linkedT o" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/headquarter" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/P opulatedP lace", "http : //dbpedia.org/ontology/headquarter" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/Organisation", "http : //dbpedia.org/ontology/headquarter" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/M ilitaryP erson" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/W ineRegion" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P lace", "http : //dbpedia.org/ontology/M odel" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/T ermOf Of f ice" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/Organisation", "http : //dbpedia.org/ontology/borough" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/P opulatedP lace", "http : //dbpedia.org/ontology/borough" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/P opulatedP lace", "http : //dbpedia.org/ontology/borough" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/bodyDiscovered" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/P lace", "http : //dbpedia.org/ontology/bodyDiscovered" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/bodyDiscovered" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/M onarch" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/targetAirport" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/Airport", "http : //dbpedia.org/ontology/targetAirport" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/Airline", "http : //dbpedia.org/ontology/targetAirport" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/museum" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/M useum", "http : //dbpedia.org/ontology/museum" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/Artwork", "http : //dbpedia.org/ontology/museum" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/Airline" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/Company", "http : //dbpedia.org/ontology/populationP lace" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/P opulatedP lace", "http : //dbpedia.org/ontology/populationP lace" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/EthnicGroup", "http : //dbpedia.org/ontology/populationP lace" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/OrganisationM ember" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/P opulatedP lace" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P lace", "http : //dbpedia.org/ontology/Royalty" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/alpsSubgroup" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/M ountainRange", "http : //dbpedia.org/ontology/alpsSubgroup" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/M ountain", "http : //dbpedia.org/ontology/alpsSubgroup" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/garrison" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/P opulatedP lace", "http : //dbpedia.org/ontology/garrison" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/M ilitaryU nit", "http : //dbpedia.org/ontology/garrison" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/hometown" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/Settlement", "http : //dbpedia.org/ontology/hometown" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/Agent", "http : //dbpedia.org/ontology/hometown" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/director" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#coparticipatesW ith", "http : //dbpedia.org/ontology/director" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/director" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/F ilm", "http : //dbpedia.org/ontology/SportsT eam" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/Organisation", "http : //dbpedia.org/ontology/SocietalEvent" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/Event", "http : //dbpedia.org/ontology/europeanAf f iliation" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/P oliticalP arty", "http : //dbpedia.org/ontology/europeanAf f iliation" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/meetingBuilding" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/Building", "http : //dbpedia.org/ontology/meetingBuilding" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/Legislature", "http : //dbpedia.org/ontology/meetingBuilding" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/M usicalArtist" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#N aturalP erson", "http : //dbpedia.org/ontology/M usicalArtist" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //schema.org/M usicGroup", "http : //dbpedia.org/ontology/M usicalArtist" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/Artist", "http : //dbpedia.org/ontology/Event" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //www.w3.org/2002/07/owl#T hing", "http : //dbpedia.org/ontology/Of f iceHolder" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/EmployersOrganisation" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/Organisation", "http : //dbpedia.org/ontology/N oble" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/sourceRegion" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/P opulatedP lace", "http : //dbpedia.org/ontology/sourceRegion" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/literaryGenre" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#isClassif iedBy", "http : //dbpedia.org/ontology/literaryGenre" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/W rittenW ork", "http : //dbpedia.org/ontology/literaryGenre" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //dbpedia.org/ontology/genre", "http : //dbpedia.org/ontology/P oliticalP arty" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/Organisation", "http : //dbpedia.org/ontology/Building" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/ArchitecturalStructure", "http : //dbpedia.org/ontology/InternationalOrganisation" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/Organisation", "http : //dbpedia.org/ontology/sourceConf luenceCountry" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/Country", "http : //dbpedia.org/ontology/sourceConf luenceCountry" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/River", "http : //dbpedia.org/ontology/sourceConf luenceCountry" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/locationCity" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //dbpedia.org/ontology/location", "http : //dbpedia.org/ontology/locationCity" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/City", "http : //dbpedia.org/ontology/locationCity" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/Organisation", "http : //dbpedia.org/ontology/locationCity" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/Grape" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/F loweringP lant", "http : //dbpedia.org/ontology/SpaceStation" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/M eanOf T ransportation", "http : //dbpedia.org/ontology/capitalM ountain" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/M ountain", "http : //dbpedia.org/ontology/capitalM ountain" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/Island", "http : //dbpedia.org/ontology/capitalM ountain" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/wineRegion" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/W ineRegion", "http : //dbpedia.org/ontology/wineRegion" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/Grape", "http : //dbpedia.org/ontology/wineRegion" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/beltwayCity" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/City", "http : //dbpedia.org/ontology/beltwayCity" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/Road", "http : //dbpedia.org/ontology/beltwayCity" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/capitalRegion" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/P opulatedP lace", "http : //dbpedia.org/ontology/capitalRegion" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/Island", "http : //dbpedia.org/ontology/capitalRegion" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/Airport" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/Inf rastructure", "http : //dbpedia.org/ontology/Agent" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //www.w3.org/2002/07/owl#T hing", "http : //dbpedia.org/ontology/SportsLeague" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/Organisation", "http : //dbpedia.org/ontology/wilaya" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/P lace", "http : //dbpedia.org/ontology/wilaya" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/Settlement", "http : //dbpedia.org/ontology/wilaya" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/owner" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#sameSettingAs", "http : //dbpedia.org/ontology/owner" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/Agent", "http : //dbpedia.org/ontology/F ilm" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/W ork", "http : //dbpedia.org/ontology/ReligiousOrganisation" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/Organisation", "http : //dbpedia.org/ontology/Broadcaster" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/Organisation", "http : //dbpedia.org/ontology/starring" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#sameSettingAs", "http : //dbpedia.org/ontology/starring" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/Actor", "http : //dbpedia.org/ontology/starring" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/W ork", "http : //dbpedia.org/ontology/P hilosopher" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/locatedInArea" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/P lace", "http : //dbpedia.org/ontology/locatedInArea" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/P lace", "http : //dbpedia.org/ontology/locatedInArea" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/alpsSubsection" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/M ountainRange", "http : //dbpedia.org/ontology/alpsSubsection" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/M ountain", "http : //dbpedia.org/ontology/alpsSubsection" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/capitalP osition" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //www.w3.org/2003/01/geo/wgs84 p os#SpatialT hing", "http : //dbpedia.org/ontology/capitalP osition" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/Island", "http : //dbpedia.org/ontology/capitalP osition" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/sourceConf luenceP lace" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/P lace", "http : //dbpedia.org/ontology/sourceConf luenceP lace" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/River", "http : //dbpedia.org/ontology/sourceConf luenceP lace" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/SportsM anager" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/Archeologist" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/state" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/P opulatedP lace", "http : //dbpedia.org/ontology/state" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/Inf rastructure" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/ArchitecturalStructure", "http : //dbpedia.org/ontology/mouthM ountain" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/M ountain", "http : //dbpedia.org/ontology/mouthM ountain" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/River", "http : //dbpedia.org/ontology/mouthM ountain" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/Company" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/Organisation", "http : //dbpedia.org/ontology/BeautyQueen" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/P lant" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/Eukaryote", "http : //dbpedia.org/ontology/mouthRegion" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/P opulatedP lace", "http : //dbpedia.org/ontology/mouthRegion" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/River", "http : //dbpedia.org/ontology/mouthRegion" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/Settlement" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P opulatedP lace", "http : //dbpedia.org/ontology/Celebrity" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/sourceState" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/P opulatedP lace", "http : //dbpedia.org/ontology/sourceState" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/M ilitaryConf lict" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/SocietalEvent", "http : //dbpedia.org/ontology/musicalArtist" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#coparticipatesW ith", "http : //dbpedia.org/ontology/musicalArtist" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/M usicalArtist", "http : //dbpedia.org/ontology/musicalArtist" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/Single", "http : //dbpedia.org/ontology/M ountain" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/N aturalP lace", "http : //dbpedia.org/ontology/SambaSchool" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/Organisation", "http : //dbpedia.org/ontology/Legislature" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/Organisation", "http : //dbpedia.org/ontology/region" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/P lace", "http : //dbpedia.org/ontology/region" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/Judge" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/Gene" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/Biomolecule", "http : //dbpedia.org/ontology/meetingCity" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/Settlement", "http : //dbpedia.org/ontology/meetingCity" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/Legislature", "http : //dbpedia.org/ontology/meetingCity" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/restingP lace" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/P lace", "http : //dbpedia.org/ontology/restingP lace" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/restingP lace" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/residence" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/P lace", "http : //dbpedia.org/ontology/residence" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/residence" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/mouthP osition" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //www.w3.org/2003/01/geo/wgs84 p os#SpatialT hing", "http : //dbpedia.org/ontology/mouthP osition" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/River", "http : //dbpedia.org/ontology/mouthP osition" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/countySeat" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/P opulatedP lace", "http : //dbpedia.org/ontology/countySeat" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/T elevisionP ersonality" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/W rittenW ork" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/W ork", "http : //dbpedia.org/ontology/alpsM ainP art" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/M ountainRange", "http : //dbpedia.org/ontology/alpsM ainP art" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/M ountain", "http : //dbpedia.org/ontology/alpsM ainP art" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/F loweringP lant" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P lant", "http : //dbpedia.org/ontology/Ship" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/M eanOf T ransportation", "http : //dbpedia.org/ontology/Scientist" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/Stream" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/BodyOf W ater", "http : //dbpedia.org/ontology/nationalAf f iliation" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/P oliticalP arty", "http : //dbpedia.org/ontology/nationalAf f iliation" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/Single" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/M usicalW ork", "http : //dbpedia.org/ontology/Ref eree" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/country" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/Country", "http : //dbpedia.org/ontology/country" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/GeneLocation" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //www.w3.org/2002/07/owl#T hing", "http : //dbpedia.org/ontology/F ictionalCharacter" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/P erson" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/Agent", "http : //dbpedia.org/ontology/Religious" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/Chef " "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/crosses" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/River", "http : //dbpedia.org/ontology/crosses" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/Bridge", "http : //dbpedia.org/ontology/crosses" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/Cleric" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/Actor" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/Artist", "http : //dbpedia.org/ontology/M usicalW ork" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/W ork", "http : //dbpedia.org/ontology/deathP lace" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/P lace", "http : //dbpedia.org/ontology/deathP lace" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/deathP lace" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/RouteOf T ransportation" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/Inf rastructure", "http : //dbpedia.org/ontology/location" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/location" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/P lace", "http : //dbpedia.org/ontology/stateOf Origin" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/Country", "http : //dbpedia.org/ontology/stateOf Origin" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/stateOf Origin" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/daira" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/P lace", "http : //dbpedia.org/ontology/daira" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/Settlement", "http : //dbpedia.org/ontology/daira" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/Astronaut" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/Cartoon" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/W ork", "http : //dbpedia.org/ontology/F armer" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/parentCompany" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#sameSettingAs", "http : //dbpedia.org/ontology/parentCompany" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/Company", "http : //dbpedia.org/ontology/U niversity" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/EducationalInstitution", "http : //dbpedia.org/ontology/GeopoliticalOrganisation" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/Organisation", "http : //dbpedia.org/ontology/SportF acility" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/ArchitecturalStructure", "http : //dbpedia.org/ontology/Artist" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/RomanEmperor" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/Genre" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/T opicalConcept", "http : //dbpedia.org/ontology/restingP laceP osition" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //www.w3.org/2003/01/geo/wgs84 p os#SpatialT hing", "http : //dbpedia.org/ontology/restingP laceP osition" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/restingP laceP osition" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/capitalP lace" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/P opulatedP lace", "http : //dbpedia.org/ontology/capitalP lace" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/Island", "http : //dbpedia.org/ontology/capitalP lace" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/Ambassador" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/f oundationP lace" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/City", "http : //dbpedia.org/ontology/f oundationP lace" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/Organisation", "http : //dbpedia.org/ontology/f oundationP lace" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/Linguist" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/alpsM ajorSector" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/M ountainRange", "http : //dbpedia.org/ontology/alpsM ajorSector" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/M ountain", "http : //dbpedia.org/ontology/alpsM ajorSector" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/M ovieDirector" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/mouthCountry" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/Country", "http : //dbpedia.org/ontology/mouthCountry" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/River", "http : //dbpedia.org/ontology/mouthCountry" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/targetSpaceStation" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/SpaceStation", "http : //dbpedia.org/ontology/targetSpaceStation" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/Spacecraf t", "http : //dbpedia.org/ontology/targetSpaceStation" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/Lawyer" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/River" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/Stream", "http : //dbpedia.org/ontology/locationCountry" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/locationCountry" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //dbpedia.org/ontology/location", "http : //dbpedia.org/ontology/locationCountry" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/Country", "http : //dbpedia.org/ontology/M emberResistanceM ovement" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/Architect" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/sourceConf luenceRegion" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/P lace", "http : //dbpedia.org/ontology/sourceConf luenceRegion" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/River", "http : //dbpedia.org/ontology/sourceConf luenceRegion" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/alpsGroup" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/M ountainRange", "http : //dbpedia.org/ontology/alpsGroup" "http : //www.w3.org/2000/01/rdf -schema#domain" "http : //dbpedia.org/ontology/M ountain", "http : //dbpedia.org/ontology/alpsGroup" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation", "http : //dbpedia.org/ontology/P layboyP laymate" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/Egyptologist" "http : //www.w3.org/2000/01/rdf -schema#subClassOf " "http : //dbpedia.org/ontology/P erson", "http : //dbpedia.org/ontology/city" "http : //www.w3.org/2000/01/rdf -schema#range" "http : //dbpedia.org/ontology/City", "http : //dbpedia.org/ontology/city" "http : //www.w3.org/2000/01/rdf -schema#subP ropertyOf " "http : //www.ontologydesignpatterns.org/ont/dul/DU L.owl#hasLocation".

LUBM queries Q 1 (?X, ?Y ) : -?X "http : //www.w3.org/1999/02/22-rdf -syntax-ns#type" "http : //swat.cse.lehigh.edu/onto/univ-bench.owl#Employee", ?X "http : //swat.cse.lehigh.edu/onto/univ-bench.owl#worksF or" "http : //www.Department0.U niversity0.edu", ?X "http : //swat.cse.lehigh.edu/onto/univ-bench.owl#degreeF rom" ?Y Q 2 (?X, ?Y ) : -?X "http : //www.w3.org/1999/02/22-rdf -syntax-ns#type" "http : //swat.cse.lehigh.edu/onto/univ-bench.owl#Employee", ?X "http : //swat.cse.lehigh.edu/onto/univ-bench.owl#worksF or" "http : //www.Department0.U niversity0.edu", ?X "http : //swat.cse.lehigh.edu/onto/univ-bench.owl#doctoralDegreeF rom" ?Y Q 3 (?X, ?Y, ?Z) : -?X "http : //www.w3.org/1999/02/22-rdf -syntax-ns#type" "http : //swat.cse.lehigh.edu/onto/univ-bench.owl#Student", ?X "http : //swat.cse.lehigh.edu/onto/univ-bench.owl#advisor" ?Y, ?Y "http : //swat.cse.lehigh.edu/onto/univ-bench.owl#teacherOf " ?Z, ?X "http : //swat.cse.lehigh.edu/onto/univ-bench.owl#takesCourse" ?Z Q 4 (?X, ?Y ) : -?X "http : //www.w3.org/1999/02/22-rdf -syntax-ns#type" "http : //swat.cse.lehigh.edu/onto/univ-bench.owl#F aculty", ?X "http : //swat.cse.lehigh.edu/onto/univ-bench.owl#degreeF rom" ?Y, ?X "http : //swat.cse.lehigh.edu/onto/univ-bench.owl#memberOf " ?Y Q 5 (?X, ?Y ) : -?X "http : //swat.cse.lehigh.edu/onto/univ-bench.owl#degreeF rom" ?Y, ?X "http : //swat.cse.lehigh.edu/onto/univ-bench.owl#memberOf " "http : //www.Department0.U niversity0.edu", Q 6 (?W, ?X, ?Y ) : -?X "http : //www.

Résumé

La recherche de points communs entre des descriptions de données ou de connaissances est un problème de raisonnement fondamental en Machine Learning, qui a été formalisé par G. Plotkin dans les années 70s sous la forme du calcul du plus petit généralisant de ces descriptions.

L'identification des plus petits généralisants a un large panel d'applications qui vont de l'optimisation de requêtes (e.g., pour matérialiser les points communs entre des requêtes lors de la sélection de vues ou pour factoriser leur exécution dans un contexte d'accès concurrentiel), à la recommandation dans le contexte des réseaux sociaux (e.g. pour créer de liens entre des utilisateurs basées sur leurs points communs selon leur profil ou leurs recherches).

Dans cette thèse nous avons revisité la notion du plus petit généralisant dans le contexte de Resource Description Framework (RDF) et le fragment conjonctif de son langage de requêtes associé SPARQL, alias Basic Graph Pattern (BGP) queries. Contrairement à l'état de l'art, nous ne considérons aucune restriction, ni structurelle ni sémantique, sur les graphes et les requêtes. Nos contributions incluent la définition et le calcul des plus petits généralisants dans ces deux formalismes ce qui revient à trouver le plus grand ensemble de points communs entre des bases de données incomplètes et des requêtes conjonctives en présence de contraintes déductives. Nous proposons également une évaluation expérimentale de nos contributions.

Abstract

Finding commonalities between descriptions of data or knowledge is a fundamental task in Machine Learning. The formal notion characterizing precisely such commonalities is known as least general generalization of descriptions and was introduced by G. Plotkin in the early 70's, in First Order Logic.

Identifying least general generalizations has a large scope of database applications ranging from query optimization (e.g., to share commonalities between queries in view selection or multi-query optimization), to recommendation in social networks (e.g., to establish connections between users based on their commonalities between profiles or searches), through exploration (e.g., to classify/categorize datasets and to identify common social graph patterns between organizations (e.g., criminal ones)).

In this thesis we revisit the notion of least general generalizations in the entire Resource Description Framework (RDF) and popular conjunctive fragment of SPARQL, a.k.a. Basic Graph Pattern (BGP) queries. By contrast to the literature, we do not restrict the structure nor semantics of RDF graphs and BGPQs. Our contributions include the definition and the computation of least general generalizations in these two settings, which amounts to finding the largest set of commonalities between incomplete databases and conjunctive queries, under deductive constraints. We also provide an experimental assessment of our technical contributions.