The Web of Data uses the World Wide Web (WWW) infrastructure to represent and interrelate data sources. These sources are referred to as knowledge graphs (KGs) and correspond to huge collections of facts in the form of RDF triples. The analysis of data contained in a KG is propaedeutic to several crucial KG curation tasks, notably the automated completion of the graph, which pose several challenges due to the open and distributed environment of the WWW infrastructure. However, KG mining could take advantage of some useful meta-information about the data to be analyzed, for instance, the schema of the KG when available. In this paper, we resort to the notion of a metaquery, proposed in the 90s as a template for patterns one is interested to discover in a relational database. We propose to extend this notion to the novel context of the Web of Data, in particular to the case of KG mining. A distinguishing feature of metaquerying problems is the use of a second-order logic language. In this paper, we present a metaquery language based on second-order Description Logics but implementable with standard technologies underlying the Web of Data, and briefly describe mechanisms for answering such metaqueries in the context of interest.
The current vision of the World Wide Web (WWW) is that of a Web of Data (WoD), which highlights the central role of data in the WWW. More precisely, the WoD builds upon the WWW infrastructure to represent and interrelate data (aka Linked Data), with the aim of transforming the Web from a distributed file system into a distributed database system. The foundational standards of the WoD include the Uniform Resource Identifier (URI) and the Resource Description Framework (RDF)1. The former is used to identify resources whereas the latter is used to relate resources. In particular, RDF can be considered as a data model according to which data is represented in the form of triples hsubject predicate objecti. Huge collections of these triples can be then organized into directed, labeled graphs known as knowledge graphs (KGs). A
typical case of a large KG is DBPedia,2 which, essentially, makes the content
of Wikipedia3 available in RDF and incorporates links to other datasets on the
Web, e.g., to Geonames4. An interesting point for the ILP community is that
RDF triples can be straightforwardly represented by means of unary and
binary first-order logic (FOL) predicates. More precisely, the unary predicates are
the objects of the RDF type predicate, while the binary ones correspond to all
other RDF predicates, e.g., halice type researcheri and hbob isM arriedT o alicei
from the KG in Fig. 1 refer to researcher(alice) and isM arriedT o(bob, alice)
respectively. KGs can be accessed by posing queries with the RDF query
language SPARQL5. Several entailment regimes are available for query answering
in SPARQL which are based on the existing link between RDF and the family
of Description Logics (DLs) [
A distinguishing feature of KGs is their inherent incompleteness. Indeed, they are constructed by automatically extracting available information from existing Web information sources (see, e.g., the above mentioned case of DBPedia). The curation of KGs is cumbersome due to their huge size. In particular, a major activity aims at the completion of the KG in hand, in order to address the issue of incompleteness. For instance, in link prediction, relational data mining algorithms can be exploited to automatically build rules able to make predictions on missing links. For example, the following rule isM arriedT o(X, Y ), livesIn(X, Z) ⇒ livesIn(Y, Z) (1) can be mined from the KG in Fig. 1 and applied to derive new facts such as livesIn(alice, berlin), livesIn(dave, chicago) and livesIn(lucy, amsterdam) to be used for completing the graph. However, the extension of relational data
mining to the WoD context is not straightforward. Indeed, being intrinsically
incomplete, KGs are naturally treated under the Open World Assumption (OWA)
as opposed to databases for which the Closed World Assumption (CWA) holds.
Nevertheless, KG mining algorithms could take advantage of some useful
metainformation about the KG in hand, e.g., domains, ranges and confidence values
of relations inside the KG (i.e., its schema). In this paper we resort to the notion
of a metaquery which was proposed in the 90s as a template that describes the
type of pattern one is interested to discover in a relational database [
The rest of the paper is structured as follows. Section 2 presents syntax and semantics of the metaquery language. Section 3 briefly describes mechanisms for answering metaqueries. Section 4 concludes the paper with final remarks and directions of future work. 2
In our proposal for the WoD context, a metaquery is a second-order DL conjunctive query. In the following we gently introduce the reader to this notion. Syntax Let L be a DL language with syntax (NC, NR, NO) where NC, NR, and NO are the alphabet of concept, role, and individual names, respectively. Note that concepts and roles in the DL terminology correspond to classes and properties in RDF.
First, we consider the extension of L so that we can enable the formulation of conjunctive queries (which go beyond the standard way of querying a DL knowledge base). For this purpose, let VO be a countably infinite set of individual variables disjoint from NC, NR, and NO. A term t is an element from VO ∪ NO. Let c be a concept, r a role, and t, t′ terms.6 An atom is an expression which can take three different forms: c(t), r(t, t′), or t ≈ t′. We refer to these three kinds of atoms as concept atoms, role atoms, and equality atoms respectively. A conjunctive query (CQ) of arity n is an expression of the form q(X1, . . . , Xn) ← a1, . . . , am (2) where q, called the query predicate, does not belong to NC ∪ NR ∪ NO ∪ VO, every Xi belongs to VO, every aj is a (possibly non-ground) atom, and all variables Xi occur in some aj . The variables Xi are called the free variables (aka distinguished variables) of the query, whereas the other variables appearing in a1, . . . , am are 6 In DLs concept and role names are usually capitalized. However, for the sake of clarity, here we shall use capital letters only for variables. called existential variables. A CQ is called Boolean if it has no free variable. An example of CQ is the following q(Y, Z) ← isM arriedT o(X, Y ), livesIn(X, Z), livesIn(Y, Z) (3) where Y and Z are the free variables, X is the existential one, and isM arriedT o(X, Y ), livesIn(X, Z), livesIn(Y, Z) are role atoms.
Since we are interested in second-order CQs, we need to introduce two further sets of variables (of second-order this time): VC of so-called concept variables, i.e. variables that can be quantified over NC, and VR of so-called role variables, i.e. variables that can be quantified over NR. Let then MQ(L) be the second-order DL language obtained by extending L with VC and VR. For the purpose of this work, we can restrict MQ(L) to particular (second-order) CQs, e.g., involving only role variables and individual variables. An example of one such metaquery is the following
M Q1 : mq(Q, Y, Z) ← P (X, Y ), Q(X, Z) (4) which looks for the properties (Q) holding for the individuals Y . Note that P, Q ∈ VR whereas X, Y, Z ∈ VO Metaqueries are the starting point for the definition of so-called metaquery extensions, i.e., implications of the form (5) (6) (7) (8)
M Q1 → M Q2
M Q1 ⇒ (M Q2 \ M Q1) which are actually a compact representation of two metaqueries, M Q1 and M Q2, where M Q2 is longer than - we say extends - M Q1. A shorter notation for (5) is the following which stresses how M Q2 extends M Q1 The left-hand side and the right-hand side of (6) are called the body and the head of the metaquery extension, respectively. Note that in the case of query extensions, the head does not correspond to the conclusion (as with clauses). Following the standard terminology, one should rather bear in mind the unshortened notation, and call M Q2 the conclusion of the metaquery extension. For instance, let us consider the following metaquery
M Q2 : mq(Q, Y, Z) ← P (X, Y ), Q(X, Z), Q(Y, Z) which looks for the properties (Q) holding for the individuals Y and shared with the individuals X to which Y is related by some P . From (4) and (7) we can build a metaquery extension as shown below
P (X, Y ), Q(X, Z) ⇒ Q(Y, Z)
Metaquery extensions serve as a template for rules we are interested in when
applying rule mining algorithms to a given KG.
Semantics As for the semantics of MQ(L), we plan to follow the Henkin style
[
A few remarks are necessary here about the use of the symbol ⇒ in (1) and (8). Differently from ←, it does not represent the logical implication. However, as discussed in Sect. 3, it can be treated as such in contexts like the aforementioned link prediction problem, provided that an appropriate choice of rule evaluation measures is done. 3
As said in the previous section, metaquery extensions are nothing but a compact representation of two metaqueries. Therefore in this section we limit our discussion to metaqueries.
The process of answering a metaquery can be divided into two stages. In the first stage, which we call the instantiation stage, we look for sets of concepts and roles that match the pattern determined by the metaquery. In the second stage, which we call the filtration stage, we filter out all the rules that match the pattern of the metaquery but do not satisfy some predefined evaluation criteria. Instantiation Instantiating a metaquery is similar to solving a Constraint Satisfaction Problem (CSP) where one is interested in finding all solutions of the CSP problem. The instantiation step is practically possible when the schema of the KG in hand is available, which is not the case for every KG. Indeed the schema provides the signature of the relations occuring in the KG, thus making this step an informed search rather than a blind search. For instance, with reference to the KG depicted in Fig. 1, (1) is an instantiation of (8) obtained by substituting the role variables P and Q with the role names isM arriedT o and livesIn, respectively.
Filtration At this stage the rules like (1) obtained by instantiating the given metaquery extension are evaluated according to some interestingness measures. For instance, we could aim at filtering out rules with low support and confidence values. In this case it is reasonable to compute confidence only for rules with sufficient support.
Following [
#(X, Y ) : h(X, Y ) ∈ G
(#X : ∃Y h(X, Y ) ∈ G) ∗ (#Y : ∃X h(X, Y ) ∈ G)
(9)
The confidence of a rule w.r.t. G can be defined starting from (9). However, in
order to estimate the actual implication of the rule at hand, we could exploit
the rule evaluation measure called conviction [
In this paper we have briefly presented a new approach to mining the Web of
Data. The approach adapts the notion of metaquery introduced by [
In the KG community approaches for link prediction are divided into
statisticsbased (see [
In the future, several aspects of the proposed approach should be clarified before an implementation. First, we need to better define the semantics for the proposed metaquery language, also concerning the link with SPARQL. Second, we need to design algorithms for the instantiation stage and choose the most appropriate evaluation measures for the intended application.