Intension graphs are introduced as an intensional variant of Wille's concept graphs. Windowed intension graphs are then introduced as formalizations of conjunctive queries. Realizations describe pattern matching over power context families, which have been introduced with concept graphs as representations of relational data using a sequence of formal contexts. Using windowed intension graphs as patterns within pattern structures, we can de ne concept lattices, where power context families take the role of formal contexts. Relational Context Families, used in Relational Concept Analysis (RCA), correspond to power context families using sorts and only binary relations, and the lattices generated by the RCA algorithm (using wide scaling) can be represented using rooted trees as intents, which are introduced as a subclass of windowed intension graphs. Consequently, projections of the previously introduced pattern structure can be used as an alternative to the RCA algorithm.
In the terminology of philosophers and linguists, a concept has an extension and an intension. We may say that "extension" refers to the things belonging to a concept, whereas \intension" refers to the meaning of a concept. Formal Concept Analysis [6] (FCA) provides a mathematical formalization of concepts which represents the extension by a set of formal objects (the extent ) and the intension by a set of formal attributes (the intent ). The notion of intension is however a vague one and di erent representations can be thought of.
Many real-world concepts describe objects in terms of their relations to other objects (e.g. visitor, grandfather, ticket), and this may suggest a di erent representation of intensions using graphs. It turns out that conjunctive queries o er a rich notational framework to support this kind of representation. In [8], concepts have been de ned in terms of family relations, and windowed relational structures have been used to represent conjunctive queries. The quali er \windowed" is used here to express that a number of designated elements have been chosen from the underlying structure. These are the elements being described. The current paper introduces intension graphs (IGs), which are attribute-labeled graphs, and uses them in place of relational structures. In contrast to relational structures, IGs formally represent information in the same way it is drawn (i.e. centered around objects) and are supposed to be more intuitive to work with. Conjunctive queries are accordingly represented by windowed IGs. Section 2 denes IGs, describes pattern matching over power context families [12] (PCFs) and shows that IGs can be represented by PCFs and vice versa.
Sections 3 and 4 de ne the sum and product of IGs and windowed IGs, respectively. In both cases, sum and product realize the supremum and in mum operations. These operations are called sum and product because they realize certain universal properties (coproduct and product) de ned in category theory. Also, Sect. 4 brie y states connections of windowed IGs to primitive positive formulas and relational algebra operations, which are known to exist because windowed IGs model conjunctive queries.
The concept lattice depends not only on the PCF (which plays the role of a formal context), but also depends on the chosen formalization of intension. Section 5.1 states the pattern structure (see [5]) for building the lattice of windowed IGs over a PCF, which contains the formalization of intension in its de nition. From there, any general algorithm for pattern structures can be used to build the lattice. Section 5.2 provides an example and illustrations.
Finally, Sect. 6.1 shows that the Relational Concept Analysis (RCA) algorithm, used with the wide scaling operator, generates lattices of rooted trees, which form a subclass of conjunctive queries. It is shown that essentially the same lattices can be generated from projections [5] of the pattern structure of Sect. 5.1. 2 2.1
A simple relational graph is a pair (V; E) consisting of a set V of vertices and a set E Sk 1 V k of edges. The edges in E(k) := E \ V k are said to have arity k (k 1).
De nition 1. An intension graph over a family (Mk)k2N of attribute sets is a triple (V; E; ), where (V; E) is a simple relational graph and is a map de ned on V [ E with (V ) P(M0) and (E(k)) P(Mk) n f;g for k 1.
A homomorphism ' : (VG; EG; G) ! (VH ; EH ; H ) of intension graphs over the same family M of intents is a map ' : VG ! VH , extended to V k, k 1, by setting
'((v1; : : : ; vk)) := ('(v1); : : : ; '(vk)); which preserves edges and intents, i.e.
'(e) 2 EH ; G(u)
H ('(u))
must hold for all e 2 EG and u 2 VG [ EG. We de ne IGM as the category of
intension graphs over M .
(
De nition 2. A power context family is a sequence (Ki)i2N of formal contexts Ki =: (Gi; Mi; Ii) such that Gi (G0)i for all i 1. We say that (Ki)i2N is a power context family over the family (Mi)i2N of attribute sets if, in addition, gIk 6= ; for all g 2 Gk, k 1.
A homomorphism ' : ((Gi; Mi; Ii))i2N ! ((Hi; Mi; Ji))i2N of power context families over the same family (Mi)i2N of attribute sets is a map ' : G0 ! H0, extended to (G0)k, k 1, by setting
'((g1; : : : ; gk)) := ('(g1); : : : ; '(gk)); which preserves incidences, i.e.
gIkm ) '(g)Jkm
must hold for all k 2 N, g 2 Gk and m 2 Mk. We de ne PCFM as the category
of power context families over M .
(
Let (Mi)i2N =: M be a family of attribute sets. We may represent a power context family (Ki)i2I in PCFM by an intension graph igM ((K)i2N) := (G0; [ k 1
Gk; fu 7! uIk j (k; u) 2 [ fkg
Gkg): k2N in IGM . Conversely, each intension graph G in IGM is represented in PCFM by the power context family pcfM (G) := ((EG(k); Mk; 3(Gk)))k2N;
(k) m :, m 2 where u 3G (u): It is easy to see that pcf M (igM (K~)) = K~ and igM (pcfM (G)) = G for all K~ 2 PCFM and G 2 IGM . Moreover, every homomorphism ' : G ! H of intension graphs is also a homomorphism ' : pcfM (G) ! pcfM (H) and vice versa. This means that the categories IGM and PCFM are essentially the same. 2.4
Power context families can be used to model factual knowledge about objects and their relations to each other. The objects are collected in a set G0, and the formal contexts (G0; M0; I0) and (G1; M1; I1) describe the objects by attributes. Finally, the contexts (Gk; Mk; Ik), k 2, describe how the objects are related to each other.
Intension graphs can be used to model patterns. The nodes describe some unspeci ed objects, and the map describes them in terms of attributes. An edge is used to indicate that the objects involved are related in some way, and the map speci es the relation(s) between the objects. A pattern match is formalized by the following de nition: De nition 3. Let G 2 IGM and K~ 2 PCFM . A realization map : VG ! G0 with (u) 2 (u)Ik for all u 2 EG(k) and k 2 N. : G ! K~ is a Since IGM and PCFM are isomorphic, we may represent patterns and data in the same category. A realization then becomes a homomorphism: Proposition 1. Let G 2 IGM and K~ =: (Gi; Mi; Ii)i2I 2 PCFM . A map ' : VG ! G0 is a realization ' : G ! K~ i it is a homomorphism ' : G ! ig(K~). Some remarks are in order why intension graphs and power context families were de ned the way they are. First, if edge labels of intension graphs were permitted, we could create more speci c patterns by adding edges with empty labels. This could be justi ed by saying that an edge with an empty label means that the incident vertices are related in some unspeci ed way. However, it seems better to model this explicitly by adding \is related" attributes. Adding empty rows to a context (Gk; Mk; Ik), k 1, of a power context family K~, on the other hand, results in an equivalent power context family (as per the homomorphism de nition). To make PCFM and IGM isomorphic, empty rows are not permitted in contexts (Gk; Mk; Ik), k 1. 3
The main result of Sections 3 and 4 is the de nition of the product and the sum for IGs and windowed IGs. These operations de ne in ma and suprema in the respective morphism preorders. Moreover, in category theoretical terms, the stated operations realize (categorical) products and coproducts[1]. This means that, given graphs G1 and G2, there are morphisms 1 : G1 G2 ! G1, 2 : G1 G2 ! G2 such that for any other graph X and morphisms '1 : X ! G1, '2 : X ! G2 there is a unique ' : X ! G1 G2 with '1 = 1 ' and '2 = 2 ' (Fig. 1), and likewise for the coproduct (Fig. 2). In nite (co-)products are de ned accordingly. Every product is an in mum in the morphism preorder, but the opposite does not hold: products are unique up to isomorphism[1], but in ma are only unique up to hom-equivalence (i.e. equivalence in the morphism preorder). The stronger product property is not needed in this paper, but when looking for in ma of patterns compared by morphisms, one may check for categorical products as they can often be derived from well-known products. It may seem unfortunate that in Fig. 1 the in mum G1 G2 is drawn above G1 and G2, but this arrangement seems to be prevalent in drawings of categorical products and is also in line with how patterns are arranged in the concept lattice.
'1 G1 wooo1oooo
G1 '
X/'//W//W//W//WW'W0WWWcW+K
G and \ i((v1(i); : : : ; vk(i))) 6= ;; (u) := \ i2I i2I i(u) for u 2 V [ E and v1; : : : ; vk 2 V , k 1. Given a set X, an intension graph G and a bijection ' : VG ! X, we call the graph '
G := ('
VG; '
EG; G
' 1)
a renaming of G (cf. (
G1 [ G2 := (VG1 [ VG2 ; EG1 [ EG2 ; G1 [ G2 ); and the disjoint union or sum of two arbitrary graphs G1 and G2 is given by G1 t G2 := ('1
G1) [ ('2
G2); where 'i(v) := (i; v) for i 2 f1; 2g and v 2 VGi . The disjoint union is the coproduct in IGM . Now let G 2 IGM and VG VG an equivalence relation. The quotient of G w.r.t. is the graph
G n := (VG n ; EG n ; ); where E n := f([v1]; : : : ; [vn]) j (v1; : : : ; vn) 2 EGg; and ([u] ) := [ (x) for u 2 VG. The operation can be visualized as a merging of nodes within the same graph. For an arbitrary relation VG VG, we de ne V n := V n , where is the smallest equivalence relation with . Finally, for graphs G; H 2 IGM and VG VH , we de ne the amalgam
G1 + G2 := (G1 t G2) n f('1(x); '2(y)) j (x; y) 2 g; (17) where '1 and '2 are given as in (13). The amalgam can be visualized as a merging of two graphs by their nodes. 3.2
An intension graph G 2 IGM with jVGj < 1 is called nite. For attribute sets B M0 and R Mk,k 1, we de ne the following structurally minimal graphs. (18) (19) (20) (21) (22)
EB(x) := (fxg; ;; fx 7! Bg) SR(x1; : : : ; xn) := (fx1; : : : ; xng; f(x1; : : : ; xn)g; R);
where R := f(x1; : : : ; xn) 7! R; x1 7! ;; : : : ; xn 7! ;g) Every nite G 2 IGM can be constructed from these graphs in a nite number of steps, using the amalgam and renaming operations. 4
De nition 4. A windowed intension graph is a pair ( ; G) consisting of an intension graph G and a partial map : N 9 VG.
A homomorphism ' : ( 1; G1) ! ( 2; G2) of windowed intension graphs is a homomorphism ' : G1 ! G2 with ' 1 2.
While a pattern match for an intension graph G in a power context family K~ has been de ned by a realization : G ! K~, the set ( ; G) := f
~
' j ' : G ! Kg
de nes the set of all pattern matches for the windowed intension graph ( ; G).
A nite windowed intension graph corresponds to a primitive positive formula
(pp formula), i.e. a predicate logical formula which is built from atoms using
conjunction (^) and existence quanti cation (
(idf0g; EB(0)) = BI0 ; (idf1;:::;ng; SR(1; : : : ; n)) = RIn ;
B R
M0; Mk; k 1; which correspond to the select operation on databases, and proceeding with similar rules for the join and project operations.
When viewing a windowed intension graph ( ; G) as a pp formula, the set 1(VG) corresponds to the free variables, and the set VG n (N) corresponds to the existentially quanti ed variables.
Let us denote by CnS the set of all primitive positive formulas in the free variables x0; : : : ; xn 1 for a given signature S. The lattice of all n-ary relations which can be de ned in a given S-structure by formulas in CnS can be de ned as the concept lattice of the context ((G0)n; CnS; j=), where j= is the satisfaction relation. In Sect. 5.1, an equivalent construction is done using windowed intension graphs as patterns over a power context family. 4.1
The product of a family of windowed intension graphs is given by The sum of windowed intension graphs is given by i2I ( i; Gi) := (h~ i; i2I
Gi); h~ i(n) := ( ( i)i2I if i(n) is de ned for all i 2 I; unde ned otherwise : ( 1; G1) + ( 2; G2) := ([ 1; 2]; G1 + ( 1; 2)
G2);
Let K~ 2 PCFM and n 2 N. We want to create the lattice which has as its extents all n-ary relations de nable by windowed intension graphs ( ; G), where is de ned on n := f0; : : : ; n 1g (i.e., is an n-tuple). The most speci c description for an n-tuple is the windowed intension graph n ~ ( ) := ( ; );
K where 5 5.1 (23) (24) (25) (27) ( 1; 2) := f( 1(k); 2(k)) j k 2 N ^ 1(k) de ned ^ 2(k) de ned g; (26) [ 1; 2](k) := >:unde ned 8>[(1; 1(k))] ( 1; 2) if 1(k) is de ned; < [(2; 2(k))] ( 1; 2) if 2(k) is de ned; :
otherwise The sum can also be de ned for arbitrary families ( i; Gi)i2I , but this is even more tedious and not needed in the following. We denote by IGXM the category of all windowed intension graphs where the rst component has domain of de nition X. where := ig(K~). We state the pattern structure as a triple ((G0)n; IGnM ; K~n), where the second component is a category instead of, as usual, a semilattice. As noted before, the in mum operation in the morphism preorder is realized - up to pattern equivalence - by the categorical product (Sect. 4.1).
The Galois connection which arises from the pattern structure can be stated as follows:
A :=
( ; ); 2A (29) (30) ( ; G) := f 2 (G0)n j 9' ' : ( ; G) ! ( ; )g: The de nitions in (20) and (30) coincide. The pattern concepts are the pairs (( ; G) ; ( ; G) ) for G 2 IGM and 2 (G0)n: The same concepts arise as the pairs (A ; A ) for A (G0)n; the patterns A and A are hom-equivalent, but generally not identical. 5.2
We de ne a family M := (fa; bg; ;; fr; sg; ;; : : : ) of attribute sets. Figure 4 shows a power context family K~ over M. The intension graph ig(K~) is shown in Fig. 5. It has three components, which are individually listed in Fig. 6 as components C1, C2 and C3.
Let us construct the concept lattice for patterns in IG1M (Fig. 7). First of all, a pattern in IG1M can be stated as (x; G) with x 2 VG (by writing ( (0); G) instead of ( ; G)), and we may alternatively state this as (x; C), where C is the component of x. The object intents, given by K~1, are the patterns (1; C1),(2; C3),(3; C3),(4; C3),(5; C2) and (6; C2). In Fig. 7, they can be found directly on top of the pattern ((); C0) for the bottom concept, which is generated by the empty product. The product C1 C3 has a single component, which is denoted C5 (Fig. 6). This yields (1; C1) (j; C3) = ((1; j); C5) for j = 2; 3; 4. As we can see, when we multiply intension graphs, several products of windowed intension graphs are obtained at once. In this case, all three products are homequivalent, and yield the topmost circle pattern in Fig.7.
Let us generate all 2-generated concepts in lectic order. The next concept would be (f1; 5g ; f1; 5g ) up to hom-equivalence. Formally, Sect. 5.1 states the intent as f1; 5g , but this is not practically relevant. The product C1 C2 provides f1; 5g and f1; 6g , which are di erent patterns (the co-atoms in Fig. 7) with the same underlying component C7. To obtain f2; 3g , we compute C3 C3, which is disconnected (C3 C3 = C3 tC4 tC4). The new component C4 yields the three remaining circle patterns in Fig. 7. Computing f2; 5g leads to C3 C2 = C6 t C8, which gives six new pattern concepts, and nally f5; 6g (the only missing combination) yields the top concept. There are two more patterns, which are 3-generated and have undelying component C10.
All patterns produced were minimal (i.e. they have no proper hom-equivalent
subpattern). The reason for this is that the nodes in the generating patterns
(
Relational Concept Analysis uses relational scaling to express relations between objects by means of formal attributes. A number of scaling operators are de ned, but only the wide scaling operator is covered here. The RCA algorithm builds a lattice from a Relational Context Family (RCF), which can be seen as a manysorted PCF with binary relations only. We only deal with the one-sorted case, because the general case is implied. In this case, an RCF can be likened to a PCF with two contexts K0 and K2. The RCA algorithm de nies an iterative procedure which incrementally adds new attributes to K0. The sequence of contexts can be described as follows: (31) (32) (33)
K(0) := K0; K(i+1) := K0 j (G0; M2
B(K(i)); J (i+1));
where gJ (i+1)(r; C) :, 9h : h 2 ext(C) ^ (g; h) 2 r:
Consider the PCF from Fig. 2. To obtain K(
a b :>:Ta :Tb :?:>:Ta :Tb :? r r r r s s s s 9 9 9 9 9 9 9 9 Fig. 9. Equivalent Object Patterns A rooted tree is called thin if it can be constructed by rules (RT1) and (RT20), where (RT20) is obtained from (RT2) by adding the additional requirement that jRij = 1 for all i 2 I.
We denote by ItM;n the subcategory of IGM that consists of the thin rooted trees of depth at most n.
Proposition 2. Let n 2 N. The concept extents of B(K(n)) are precisely the sets (x; T ) described by thin rooted trees (x; T ) of depth n.
Proof. This is proved by induction over n 2 N. For n = 0, the claim follows from (21). If T is a thin rooted tree with depth(T ) = n + 1, there is a family (xi; Ti)i2I of thin rooted trees of depth n and a family (ri)i2I of attributes in M2, such that (x; T ) = (0; EB(0)) + Pi2I (0; Sfrig(0; 1) + Ti). By the f(1;xi)g induction hypothesis, there exists a family (Ci)i2I of concepts Ci 2 B(K(n)) with (xi; Ti) = ext(Ci). Then (x; T ) =((0; EB(0)) +
X(0; Sfrig(0; 1) i2I This shows that (x; T ) is a concept extent in B(K(n+1)). Conversely, a concept extent in B(K(n+1)) is de ned by an attribute set as in (40), and the induction hypothesis is used in (39) to obtain the family (xi; Ti)i2I for given (Ci)i2I . tu A graph G 2 IGM can be unfolded into a (possibly in nite) tree, starting at any given vertex which becomes the root of the tree. It is easy to see that, among all trees more general than G, the unfolding is the most speci c one. In other words, the unfolding is a kernel operation (the dual of a closure operation). This implies that an V-sublattice is obtained if patterns are restricted to trees. A similar operation constructs a thin rooted tree from a graph: In addition to unfolding, every edge carrying multiple relation attributes is spliced into several edges, each carrying exactly one of the relation attributes. The operation is formalized by the following inductive de nition, where G 2 IGM and x 2 VG: splice(0)(x; G) := (x; E (x)(x)); splice(i+1)(x; G) := (x; E (x)(x)) + where (y~; Ty(i)) := splice(i)(y; G)
X (x; Sfrg(x; y) The following proposition states, in category theoretical terms, that the splice operation maps each (x; G) 2 IG1M to its core ection in ItM (cf. Fig. 3). As can be seem from Fig. 3, this implies that splicing is a kernel operation (or pattern projection). This means that the pattern structure (G0; ItM ; splice K~1) creates the concepts of the RCA algorithm.
Proposition 3. For each (x; G) 2 IG1M , there exists a morphism '(x;G) : splice((x; G)) ! (x; G) such that for every (y; T ) 2 ItM and ' : (y; T ) ! (x; G) there exists a unique morphism : (y; T ) ! splice((x; G)) such that ' = '(x;G) .
Proof sketch: We inductively prove a unique morphism (i) : splice(i)((y; T )) ! splice((x; G)). In the induction step, the image of each neighbor of the root node is uniquely determined. The union of the := (i) is well-de ned (because of the uniqueness). Since splice((x; T )) = (x; T ) holds, ' is the required morphism. tu
From a given graph G 2 IG1M , we can determine for each x 2 VG the extent ext (x) in splice((x; G)) without actually splicing the graph. Let us denote this as the tree extent tex (x) of x in G. The tree extent can be computed as follows: tex(0)(x) :=
G(x)Ik for x 2 EG(k); tex(i+1)(x) := tex(0)(x) \
\ This can be proven by inductively showing splice(i)((x; G)) = tex(i)(x). 7
Power context families and concept graphs have been introduced by Rudolf Wille in [11]. Concept graphs have been presented as a mathematical formalization of Conceptual Graphs [10]. Di erent kinds of concept graphs are presented in [12] but, to the knowledge of the author, abstract concept graphs mentioned in introductory paper [11] are the only kind of concept graphs de ned without a realization. Abstract concept graphs use symbols as node labels rather than sets of attributes.
In [8], windowed structures have been introduced as triples (X; ; G), and a Galois connection into a complete lattice of data tables (where the in mum is realized by the join for database tables) has been presented. A follow-up paper [9] addresses the connection to logic, features sorts, uses a \relational structure with concept labels" hybrid and shows the connection to pattern structures by representing extensions as sets of partial interpretations. Pattern structures were introduced in [5], and the use of Conceptual Graphs as patterns is suggested in there. The representation of conjunctive queries (and thus pp formulas) by graphs, and of entailment by graph homomorphism, is credited to [2]. In [3], these relationships are stated for -BGs, which are Basic Conceptual Graphs with distinguished concepts given by a mapping , and this representation directly corresponds to the windowed abstract concept graphs (and their homomorphisms) in the paper at hand. Moreover, in [3, Chapter 8], the categorical product is used to describe the least generalization of Conceptual Graphs. The Projected Graph Patterns (PGPs) in [4], their inclusion and intersection, corresponds to -BGs and windowed abstract concept graphs and their respective notions of homomorphism and product. In [4], as in [8], concept lattices are generated, with intents realized using the respective formalizations.
Relational Context Families and the construction algorithm are described in [7], and the RCA algorithm has been described for di erent kinds of interobject relations which are not covered here.
The paper has introduced windowed intension graphs as a formalization of conjunctive queries. Intension graphs correspond to concept graphs without the realization component. Some notation has been introduced which establishes connections to logic and database theory. The lattices generated by the RCA algorithm have been characterized as V-sublattices of conjunctive queries. The results concerning rooted trees still have to be implemented and compared with the RCA algorithm. While a bound for the maximum number of iterations of the RCA algorithm can be given by jGj, the pattern structures algorithms might bene t from a better bound computed in advance from the context family.