The concept lattice of an RDF graph is defined. The intents are described by graph patterns rather than sets of attributes, a view that is supported by the fact that RDF data is essentially a graph. A simple formalization by triple graphs defines pattern closures as connected components of graph products. The patterns correspond to conjunctive queries, generalization of properties is supported. The relevance of the notion of connectedness is discussed, showing the impact of ontological considerations on the process of concept formation. Finally, definitions are given which allow the construction of pattern closures of concept graphs, which formalize Conceptual Graphs.
The Resource Description Framework (RDF) is an extensible standard for
knowledge representation which relies on the use of simple sentences, each consisting
of a subject, a predicate and an object. In RDF terminology, such a sentence
is called a triple; a collection of triples is called an RDF graph, and the entities
which occur as subjects, predicates or objects of triples (i.e.,the things being
talked about) are called resources. Figure 1 shows an RDF graph in the
textbased Turtle notation [
Conjunctive queries can be represented as graphs, and entailment is described
by graph homomorphisms [
rdf:obj ex:Lobscouse . ex:Liam ex:loves ex:Aideen ex:loves ex:Rowan ex:loves ex:Rowan ex:hates ex:Aideen ex:said ex:S3 rdf:subj ex:S3 rdf:pred ex:S3 rdf:obj ex:Aideen . ex:Liam . ex:Aideen . ex:Liam . ex:S3 . ex:Rowan . ex:likes .
ex:Aideen . described by homomorphisms, as well. But there are some differences to RDF graphs. Firstly, all nodes (and all arcs) represent variables. The subject(s) of the query are distinguished in some way (in Fig. 3, a black node represents the single subject), whereas all other variables are implicitly understood as being existentially quantified. Finally, the labels are attributes of a formal context K (for the example, see Fig. 4), and thus represent formal concepts of its concept lattice B(K). In practice, the formal context may encode background knowledge from an RDF Schema file like the one in Fig. 5. The query vocabulary is restricted to the attributes of K, the name Frank e.g. may not be used in a query for the given example.
rdf:type
For the rest of the paper, we shall refer to queries as patterns. Sect. 2
introduces triple graphs as formalizations of queries without distinguished variables
(they correspond to SPARQL WHERE-clauses), and a query in one distinguished
variable is then represented by the pair (x, G) consisting of a triple graph G
and a vertex x of G. The case of queries in several variables is not treated in
this paper, but has been treated in [
Lattices of pattern concepts were introduced in [
The situation changes if graphs have a distinguished element. The supremum is a graph product, again with a distinguished element, and although the product of connected graphs is generally not connected, it makes sense to identify the supremum with the connected component which holds the distinguished variable. The relevance of connectedness is discussed in Sect. 4. In Sect. 5, the approach is applied to concept graphs. 2
A triple graph over K is a triple (V, T, κ), where V is a set of vertices, T ⊆ V × V × V and κ : V → B(K).
A morphism ϕ : (V1, T1, κ1) → (V2, T2, κ2) of triple graphs is a map ϕ : V1 → V2 with
Y(vi, Hi) := ((vi)i∈I , Y Hi). i∈I i∈I
The definitions above follow a category theoretical approach. Queries (minus
distinguished variable(s)) and the data source have representations in the same
category (using Δ for the data source), and morphisms λ : G → Δ can be
understood as solutions of the respective query. Query entailment is then described
by morphisms, and if the category has products, then so has the category of
structured arrows (these are the pairs (ν, G), cf. [
The product of a family of triple graphs Gi = (Vi, Ti, κi), i ∈ I, is the triple graph
Y Gi := ( i∈I × Vi, { tT | t ∈ × Ti}, _ κi), i∈I i∈I i∈I where tT := ((ti0)i∈I , (ti1)i∈I , (ti2)i∈I ) and (Wi∈I κi)(v) := Wi∈I κi(vi).
Finally, an RDF graph with the set T of triples is represented by the triple graph (R, T, γ∗), where R is the set of resources (properties and classes are duplicated so that they appear in only one triple) and γ∗(g) := ((g00, g0) if g ∈ G, > := (G, G0) otherwise .
A pattern is a pair (v, H), where H =: (V, T, κ) is a triple graph and v ∈ V . A pattern morphism ϕ : (v1, H1) → (v2, H2) is a morphism ϕ : H1 → H2 with ϕ(v1) = v2. A solution is a pattern in the data graph. Pattern morphisms can thus describe solutions as well as entailment.
The product of a family of patterns is given by (1) (2) (3) (4) (5)
In this section, we will walk through the process of generating a concept lattice for the RDF graph in Fig. 1. To keep the example small (and perhaps meaningful), only person concepts will be created, i.e. concepts with extents in the set {Tom, Frank, Mary, Rowan, Liam, Aideen}.
As a first step, we determine the object intent for each person, i.e. its most complete description. For each person, its connected component in Fig. 2 doubles as a most complete description if we reinterpret the nodes and arcs as (distinct) variables, reinterpret the labels beside them as concept names (rather than resource names), and mark the variable corresponding to that person as distinguished. Let G1 and G2 denote, top to bottom, the components in Fig. 2 after reinterpretation, and let T , F , M , R, L and A denote the variables which replace Tom, Frank, Mary, Rowan, Liam and Aideen. Then the pairs (T, G1), (F, G1), (M, G1), (R, G2), (L, G2) and (A, G2) formalize the object intents. These pairs are considered patterns; each pattern consists of a distinguished variable and a triple graph (formalized in Sect. 2).
The person concepts are obtained from graph products of the six base patterns. Many concept intents have the same underlying triple graph (consider e.g. the base patterns), so there would be a lot of redundancy in the concept lattice if we were to draw intents next to each concept. A different kind of diagram avoids this redundancy while still showing all concepts and their intents : Fig. 6 shows all triple graphs which occur in the intents of person concepts, ordered by homomorphism. Choosing any of the nodes as a distinguished variable gives rise to a pattern intent, and this way concepts can be identified with triple graph nodes. The gray nodes in Fig. 6 are the person concepts (the white nodes are non-person concepts which occur in the descriptions of person concepts). The concept extents for the person concepts are drawn next to the gray nodes. The person concept lattice itself can be easily obtained from the diagram in Fig. 6 by connecting the gray nodes according to their extents.
Note however that some concepts have multiple representations in Fig. 6. These may occur in the same triple graph, which indicates symmetry (i.e., a triple graph automorphism). An example is the pair of lovers on the right side of Fig. 6. The other case is where the same concept occurs in different triple graphs. An example would be the Mary concept, which occurs in the lower left triple graph as well as in the triple graph above it on the left side of Fig. 6. In such cases, there is always a most specific triple graph containing that concept; it describes that concept’s pattern intent. Other triple graphs containing the same concept can be folded onto the most specific triple graph (which is contained as a subgraph). But the fact that triple graphs may reappear as subgraphs of other triple graphs translates into another redundancy problem when drawing the hierarchy of triple graph product components. In Fig. 6, this kind of redundancy has been avoided by cutting those subgraphs out and indicate the glue nodes (for the gluing operation which inverts the cutting operation) with an asterisk. The glue nodes are only marked in the upper triple graph, not in the lower triple graph, because the lower triple graph can be considered self-contained (a glue node’s counterpart in the lower graph can be identified by its extent). To put this differently: in every triple graph, the asterisk concepts are part of the description of the non-asterisk concepts, but not vice versa.
The extent of a concept reveals how its pattern intent can be obtained.
Consider for example the concept with extension {R, F, T }, which is part of the
top left triple graph. The extension tells us that the pattern intent is the (core
graph of the) component of the pattern product (R, G2)×(F, G1)×(T, G1), which
contains the vertex (R, F, T ), and (R, F, T ) becomes the designated variable. The
diagram also shows that {R, T } is a generating set for this extent, because it
is not contained in a concept extent of the triple graph’s lower neighbors, and
so (R, G2) × (T, G1) already produces the same pattern. As was described in
[
Product patterns could also be computed directly from the triples in Turtle notation (Fig. 1), by combining triples with each other. Informally, we could write triple graphs as sets of triples (x : κ(x), p : κ(p), y : κ(y)) (borrowing from RDF and CG notation), and compute the product triples by taking suprema componentwise, like so: ∨ = (F : >, p : type, y1 : Englishman) (T : >, p : type, y2 : Gentleman) ([ FT ] : >, [ pp ] : type, [ yy12 ] : Man).
However, one would still have to identify and minimize connected components.
Note that the property and class hierarchies in our example are trees. So the attribute concepts of K are closed under suprema, and each concept label can be expressed by a single attribute. The suprema of properties may be of type ”Resource”. Such arcs are removed from the patterns; it can be shown (using the product property) that the resulting patterns can still be considered MSQs. 4
We have identified two components of the RDF graph in Fig. 1, and this corresponds to our understanding that objects are ”connected” if they contribute to the same instance of a situation. The notion of connectedness deserves closer examination, however. Let us first observe that the notion of strong connectivity is not the right one, because the second to top concepts in Fig. 6 (we might name them ”Lover” and ”Beloved”) would not have been created under this notion. But also, we can in general not rely on weak connectivity alone. If it had been stated explicitly that all persons are of type ”Person”, all persons would be connected through that class node.
Clearly, objects do not contribute to the same situation just on the basis of belonging to the same class, or having equal property values, like being of the same age. So connectedness of patterns should not rely on properties, classes or values. In this paper, no further requirements have been made, but if Liam liked lobscouse (a traditional sailors’ dish), this would have not been sufficient because all objects would be connected through the lobscouse node. From a machine perspective, there is no indication in the RDF data (or the schema) that ”ex:lobscouse” is of a different quality than ”ex:Tom” or ”ex:Mary”. A system that generates patterns from automatically acquired data without proper preprocessing would possibly generate a large number of meaningless (and unnecessarily large) concepts because of such insubstantial connections, unless it can be guaranteed that some standard for making such distinctions is applied on the level of the ontology language.
Further questions may include if and how real-world objects should be connected through objects of spoken language; on what basis we could allow a pattern like the one describing the set of all wifes older than their husband, and at the same time keep meaningless comparison of values from having an impact on concept formation; or if pattern connection should be described in terms of edges rather than nodes, and if we can classify or characterize the kind of relations which contribute to pattern formation. It seems that, when dealing with pattern concepts, questions of philosophical ontology may have (at least subjectively) measurable impact through the notion of connectedness. 5
In Sect. 2, the category theoretical framework for lattices of pattern concepts has
been applied to triple graphs, and we will now show how it is applied to simple
concept graphs. In [
In [
A datasource for the schema K~ is a power context family D~ = (D0, D1, D2, . . . ) for which the attribute implications described by Ki =: (Hi, Ni, Ji) are satisfied in Di =: (Gi, Mi, Ii), i = 0, 1, 2, . . . , and Ni ⊆ Mi holds. We can represent D~ by an abstract concept graph D = (G0, Si≥1 Gi, id, γD) with γD(u) := ((uIk ∩ Nk)Jk , uIk ∩ Nk) ∈ B(Kk) for u ∈ Gk. Let us furthermore define ExtD(κ(u)) := Ext(κ(u))JkIk for u ∈ V ∪ E. If we define a realization of G =: (V, E, κ, ν) over D as a map with ρ(u) ∈ ExtΔ(κ(u)) for all u ∈ V ∪ E and ρ(e) = (ρ(v1), . . . , ρ(vk)), we obtain that the realizations ρ of G over D are precisely the morphisms ρ : G → D. This means that product patterns for abstract concept graphs can be interpreted as MSQs, as was mentioned at the end of Sect. 1.
Triple graphs are now obtained as a special case of concept graphs: We define a power context family D~ where D0 is a supercontext of K0 which in addition contains all objects (having only the ”Resource” attribute), and where D3 = (T, ∅, ∅) represents the set of triples.
In Relational Concept Analysis, concept lattices for different kinds of
interrelated objects are generated by an iterative algorithm and, as in Fig. 6,
illustrations displaying graphs of concepts have been given [
In [
In the section on connectedness, we have seen that ontological considerations stand in a direct relation to the quality of computed concepts. As a first consequence, although the idea of treating all kinds of resources in a homogeneous way seemed appealing, triple graphs must be replaced by some other formalization which reflects the importance of the distinction between instances and classes/properties. While such questions naturally arise in the setting of pattern concepts, they seem to have no obvious analogy for standard FCA, where intents are sets of attributes. Pattern concepts have thus the potential to further and substantiate a perspective on FCA as a branch of mathematical modeling, where the entities to be modeled are not ”real world” systems but rather systems of concepts. Future work may be concerned with extensions of RDF/RDFS which support this perspective.