ions from objects described by both own properties and interobject links, while dealing with several sorts of objects. RCA produces lattices for each category of objects and those lattices are connected via relational attributes that are abstractions of the initial links. Navigating such interrelated lattice family in order to nd concepts of interest is not a trivial task due to the potentially large size of the lattices and the need to move the expert's focus from one lattice to another. In this paper, we investigate the navigation of a concept lattice family based on a query expressed by an expert. The query is de ned in the terms of RCA. Thus it is either included in the contexts (modifying the lattices when feasible), or directly classi ed in the concept lattices. Then a navigation schema can be followed to discover solutions. Di erent navigation possibilities are discussed.
Recently [
We proposed an approach based on Relational Concept Analysis (an iterative version of Formal Concept Analysis) to solve this problem, because of its multi-relational nature. Web services are ltered and grouped by tasks they may satisfy (e. g. the Web services for booking a hotel room). In formal contexts (one for each task), we associate the Web services and their QoS criteria. For example, the service HotelsService by lastminutetravel.com would be described by low response time, medium availability (classical scaling is applied to the QoS values). In relational contexts we encode the composability levels in each directed edge of the work ow. Given an edge of the work ow, the composition quality depends on the way output data of the source task cover input data of the ending task, and the need for data adaptation. A relational context encodes for example the relation Adaptable-Fully-Composable between services for reserve a train ticket and services for book a hotel room. In this relation TravelService by puturist.com is connected to HotelsService by lastminutetravel.com if output data of TravelService can be used, with a slight adaptation, to ll input data of HotelsService.
The concept lattice family we obtain (one Web service lattice for each task of the work ow) makes it possible: (1) to select a Web service for each task based on QoS and composability criteria, (2) to memorize classi ed alternatives for each task.
Due to the nature of our problem, we are interested in classifying
independently the Web services corresponding to the tasks and not classifying the
solutions. By solution, we mean a set of Web services, each of which can instantiate a
task of the work ow. If a particular service fails or is no more available, the goal
is to constitute a new working combination out of the old one, with the smallest
number of service replacements. To the best of our knowledge, this problem area
has not been investigated in-depth prior to our study, especially in the context
of Relational Context Analysis [
In this paper, we put the problem in a more general framework, which assumes an unrestricted relational context family and a query given by an expert. The query can be seen as a DAG, where some nodes are labelled by variables and some others are labelled by objects. The nodes roughly correspond to the formal (object-attribute) contexts and the edges correspond to the relational (objectobject) contexts. A set of lattices is built using Relational Concept Analysis and the existential scaling operator. We assume that an expert gives a total ordering of the edges of the DAG. Then an algorithm navigates the lattices following this ordering. This navigation allows us to determine objects that answer the query. These objects with their position in the lattices are what the expert wants to explore, to extract a solution and store the alternatives.
In the following, Section 2 reminds the main principles of Relational Concept Analysis (RCA). Section 3 de nes the model of queries in the RCA framework that we consider in this paper. Section 4 presents and discusses an algorithm that navigates the concept lattice family using a query. Related work is presented in Section 5 and we conclude in Section 6. 2
For FCA, we use the notations of [
The RCF corresponding to our example contains ve formal contexts and ve relational contexts, illustrated in Table 1 (except the made-in relational context, which is not used in this paper for sake of simplicity). An RCF is used in an iterative process to generate at each step a set of concept lattices. First concept lattices are built using the formal contexts only. Then, in the following steps, a scaling mechanism translates the links between objects into Country Canada England France Lebanon Mexico Spain USA another object ot, then in the scaled relation, this link is encoded in a relational attribute assigned to os. This relational attribute states that os is linked to a concept, which clusters ot with other objects. This is used to form new groups, for example the group (See Concept 84) of restaurants, which serve at least one dish containing sour cream (such dishes are grouped in Concept 75). The steps are repeated until reaching the stability of lattices (when no more new concepts are generated). For mexican dishes, four lattices of the concept lattice family are represented in Figures 3 and 4. The ingredient lattice is presented in Fig. 2. De nition 2. Let rij Oi Oj be a relational context. The exists scaled relation ri9j is de ned as ri9j Oi B(Oj ; A; I), such that for an object oi and a concept c: (oi; c) 2 ri9j () 9 x; x 2 o0i \ Extent(c).
In this de nition, A is any set of attributes maybe including relational attributes, which are de ned below.
De nition 3. A relational attribute (s r c) is composed of a scaling operator s (for example exists), a relation r 2 R, and a concept c. It results from scaling a relation rij 2 R where rij Oi Oj . It expresses a relation between the objects o 2 Oi with the concepts of B(Oj ; A; I). An existential relational attribute is denoted by 9rij c where c 2 B(Oj ; A; I).
For example: the Concept 50 in the Country lattice owns the relational
attribute 9has Concept 60. This expresses that each country in Concept 50
(Canada and USA) has at least a restaurant in Concept 60 extent (El
Sombrero or Mi Casa).
In this section, we de ne the notion of query and answer to a query. First (section
3.1) we recall simple queries that help navigating concept lattices [
For example qjKcountry = (fEngland; F rance; Spaing; fEuropeg) is a query on the country context (in Table 1), asking for countries in Europe. Another example qjKMexicanDish = (fg; frice; corn-tortillag)
When aq is closed, solving the query consists in nding the concept C = (a0q; aq). To ensure that such a concept exists, a virtual query object ovq that satis es ovq0 = aq can be added to the context (as an additional line). Then, three types of answers can be interesting: the more precise answers are in a0q, less constrained (with less attributes) answers are in extents of super-concepts of C, more constrained (with more attributes) answers are in extents of sub-concepts of C. When aq is not closed, and we don't use the virtual query object, searching for answers needs to nd rst the more general concept C whose intent contains aq. Now we will de ne more generally what we mean by relational queries. In this study, a relational query is composed of several simple queries, to which we add relational constraints. The relational constraints are expressed via virtual query objects (variables), one for each formal context, where we want to nd an object. A virtual query object may have relations (according to the relational contexts) with objects of other contexts, as well as with other virtual query objects.
De nition 5. A relational query Q on a relational context family (K; R) is a pair Q = (Aq; Ovq; Rq), where: 1. Aq is a set of simple queries
Aq = fqjKi = (oqjKi ; aqjKi ) j qjKi is a query on Ki 2 Kg 2. There is a one-to-one mapping between Aq and Ovq, where Ovq is the set of virtual query objects. 3. Rq is a set of relational constraints Rq = f(ovqjKi ; rij ; Oq)g, where ovqjKi is the virtual object associated with qjKi , Oq Oj [ fovqjKj g, with ovqjKj is the virtual object associated with Kj .
For example, let us consider the following query: I am searching for a country with the attribute "fr", a restaurant in this country serving Mexican dish containing (chicken, cheese, and corn-tortilla), and a salsa which is "hot" and suitable with the dish. This query can be translated into a relational query Qexample = (Aq; Ovq; Rq) as follows: Aq = fqcountry; qrest:; qdish; qsalsag, aqcountry = ff rg, aqrest: = aqdish = ;, aqsalsa = fhotg.
Ovq = fovqdish ; ovqcountry ; ovqrest: ; ovqsalsa g Rq = f(ovqdish ; contains; fchicken; cheese; corn-tortillag), (ovqcountry ; has; fovqrest: g), (ovqrest: ; serves; fovqdish g), (ovqsalsa ; suitable-with; fovqdish g g ) .
By de nition, a query corresponds to the data model, and must respect the schema of the RCF (see in Fig. 1).
An answer to the relational query is included in the answers of the simple queries. For our example, the answers of the simple queries would be oqcountry = fF ranceg, oqrest: contains all the restaurants, oqdish contains all the dishes, oqsalsa = fT omatillo-Red Chilig. If we consider these objects connected with the relations, this forms what we call the maximal answer graph. In this graph, we are interested in the subgraphs that cover the query (they have at least one object per element of Aq). These subgraphs are included in the graph of Fig. 5. There are various interesting forms of answer: having exactly one object per element of Aq, or having several objects per element of Aq.
De nition 6. An answer to a relational query Q = (Aq; Ovq; Rq) is a set of objects X having a unique object per each context that is involved in the query: X =< oi j oi 2 Oi with 1 i n > These objects satisfy the query Q = (Aq; Ovq; Rq), when they have the requested attributes: 8 qjKi 2 Aq; 9 oi 2 X : o0 i aqjKi and they are connected as expected: 8 (ovqjKi ; r; Oq) 2 Rq with r Oi 8 o 2 Oq; we have :
Oj ; (and thus : Oq
Oj [ fovqjKj g) and
if o 2 Oj ; we have (oi; o) 2 r if o = ovqjKj ; we have (oi; oj ) 2 r with oj 2 X \ Oj { 8 qjKi 2 Aq; 8 oi 2 Si; o0i { when (ovqjKi ; r; Oq) 2 Rq
For our example, the set of answers to the relational query, is: ffF rance; El Sombrero; Enchiladas; T omatillo- Red Chilig; fF rance; El Sombrero; Quesadillas; T omatillo-Red Chilig; fF rance; El Sombrero; T acos; T omatillo-Red Chilig, fF rance; Old el P aso; T acos; T omatillo-Red Chiligg.
Answers can be provided with an aggregated form which can be found in lattices, as we explain below. They allow us to discover sets of equivalent objects relatively to the answer. E.g. fEnchiladas; Quesadillas; T acosg are equivalent objects if we choose F rance and ElSombrero.
De nition 7. An aggregated answer to a query Q = (Aq; Ovq; Rq) is the set AR containing the sets Si, such that: { there is a one-to-one mapping between AR and Aq which maps each qjKi to a set Si
qjKi (objects of Si have the requested attributes) - if ovqjKj 2 Oq; r Oi Oj ; thus : 8 oi 2 Si; 8 oj 2 Sj ; Sj 2
AR; we have (oi; oj ) 2 r (virtual objects are connected if requested) - f or each oj 2 Oq \Oj we have : (oi; oj ) 2 r (connections with particular objects are satis ed).
For example, an aggregated answer for our query is fScountry; Srest:; Sdish; Ssalsag = ffF ranceg; fElSombrerog; fEnchiladas; Quesadillas; T acosg; fT omatilloRedChiligg 4
Navigating a Concept Lattice Family w.r.t. a Query
In this section, we explain how the navigation between the concept lattices can
be guided by a relational query. Following relational attributes that lead us from
one lattice to another, we navigate a graph whose nodes are the concept lattices.
In a rst subsection, we propose an algorithm which gives a general navigation
schema that applies to concept lattices built with the existential scaling. Then
we present several variations of this navigation algorithm.
Our approach for navigating the concept lattices along the relational attributes is
based on the observations made during an experimental use of RCA, for nding
the appropriate Web services to implement an abstract calculation work ow [
The query path is a total ordering of the arcs of the query (the query itself is a DAG in general). For our example, the path is the total ordering for Rq given by f(qcountry; has; fqrestaurantg), (qrestaurant; serves; fqdishg), (qdish; contains; fchicken; cheese; corn-tortillag), (qsalsa; suitable-with; fqdishg)g. Each arc corresponds to a relation used in the query. All the relations involved inside a query are covered by this path. This translation of the expert query determines a composition on the relations. The query path does not always correspond to a directed chain in the object graph (e.g. dishes are the end of two of the considered relations (serves and suitable-with)).
We propose the algorithms 1 to 3 (an additional procedure is needed which combines two others) for navigating through a concept lattice family using queries. During the exploration, we ll a set X by objects that will constitute an answer at the end (at most one object for each formal context). In this section, the algorithm is presented as an automatic procedure. Its use to guide an expert in its manual exploration of the data is discussed afterwards.
Algorithm 1 identi es three main cases: { line 2, the arc connects two query objects, e.g. (qcountry; has; fqrestaurantg); { line 5, the arc connects a query object to original objects e.g. (qdish; contains; fchicken; cheese; corn-tortillag); { line 8, the arc connects a query object to another query object and to original objects e.g. (qdish; contains; fqingredient; chicken; cheese; corn-tortillag). Each of these cases considers, for a given arc a, whether the partial answer X already contains a source object or (inclusively) a target object.
When the arc connects a query object to another query object a = (qjKs ; rst; qjKt ), (Algorithm 2), four cases are possible.
{ X does not contain any object for Ks and any ot for Kt: we identify the highest concept that introduces the attributes of qjKs and we select an object in its extent (lines 3-5). Then the algorithm continues on the next conditional statement (to nd a target). { X contains an object os for Ks and an object ot for Kt selected in previous steps: we just check if os owns the relational attribute pointing at the object concept introducing ot, that is ot (line 8)1. { X contains only an object os for Ks. We should nd a target. We identify, under the meet of the concepts that introduce the attributes of qjKt , one of the lowest concepts to which os points (lines 12-14). We select a target in its extent. { X contains only an object ot for Kt. We should nd a source. We identify the meet of the concepts that introduce the attributes of qjKs and the relational attribute that points to ot (lines 20-23). We select a source in its extent.
When the arc connects a query object to original objects a = (qjKs ; rst; Oq) (Algorithm 3): { Either X contains an object for Ks and we need to check if the relational attributes con rm that this object is connected to all the original objects in Oq) (line 4); { Or we have to select an object for Ks, owning the attributes of the query qjKs and owning the relational attributes ending in the concepts introducing the original objects (line 9-11).
The algorithm for the last case is a combination of the algorithms for the two other cases. Note that whenever a condition is not veri ed, we have to backtrack, this is not speci ed in the algorithm for sake of simplicity. If the query path forms also a directed chain in the entity-relationship diagram, the main algorithm is a depth- rst search. But in the general case, in some steps, when we consider an arc, we assigned to X an object for the end of the arc, and we need to nd a source object.
For example, we start with the arc (qcountry; has; fqrestaurantg) where the query path begins. We have to identify a source object os satisfying the query ff rg (De nition 4). For example, we choose the object France appearing the extent of Concept4, whose intent contains fr.
We extract the relational attributes of os = F rance, having the form 9rst C). They are in practice in the lattices denoted by r : C. For example, we obtain has:Concept 19, has:Concept 15, has:Concept 60, has:Concept 16, etc. We keep the relational attributes with the concepts satisfying the target query in the corresponding lattice and discard the rest. In our example, the qrestaurant is empty. A relational attribute with the smallest concept (Ct) is the one to consider that leads us to nd a solution. We choose Concept 15 among the available smallest concepts. Let 9 rst Ct be the selected relational attribute (if it exists). The object ot must be in the extent of Ct. In our example, we select El Sombrero.
Then we consider the query-to-query arc (qrestaurant; serves; fqdishg). Given that an object is selected for Krestaurant, we look for a possible target object, led by the query qdish = ; and the relational attributes owned by the object 1 We remind that o is the object concept introduced by o. concept Concept 15 which introduces El Sombrero. Suppose we choose (line 13) a relational attribute that targets one of the minimum concepts, namely serves : Concept 23 (but serves : Concept 26 or serves : Concept 25 are also possible). This leads us to Concept 23, in the extent of which we select Enchiladas.
Dealing with the next arc (qdish; contains; fchicken; cheese; corn-tortillag) involves, since we have already selected a dish, to verify (Algorithm 3, line 4) that, the object concept Enchiladas owns all the relational attributes that go to object concepts introducing chicken, cheese, and corn-tortilla. These are contains : chicken = Concept 29, contains : cheese = Concept 36 and contains : corn tortilla = Concept 40 and they are indeed inherited by Enchiladas = Concept 23.
When the arc (qsalsa; suitable-with; fqdishg) is considered, the target (Enchiladas) is in X. Thus we identify a source in the extent of the Concept 47, which satis es the target query fhotg. Its intent contains suitable with : Concept 23 which is Enchiladas. A target object (Tomatillo-Red Chili) is selected in the extent of Concept 47. The answer is now complete.
Algorithm 1: Navigate(RCF; Q; PQ) //PQ = (ak) j ak = rij and rij 2 RQ Data: (K; R): an RCF; Q = (Aq; Ovq; Rq): a query on (K; R); and a query path Result: X: an object set (answer for Q) or fail foreach arc a 2 PQ do if a = (qjKs ; rst; qjKt ) then
Case pure query else if a = (qjKs ; rst; Oq) with Oq
Case pure objects else
Ot then if a = (qjKs ; rst; qjKt ) with qjKt 2 Oq then
Case query and objects Integrating queries into the contexts. One approach that was investigated in the case of simple queries consists of integrating the virtual query object in the context, then building the concept lattice. This can also be done for relational queries. A relational query Q = (Aq; Ovq; Rq) can be integrated into an RCF by adding the virtual query objects ovqjKi into the context Ki. Each virtual query object ovqjKi owns the attributes of the query aqjKi and for each arc (ovqjKi ; rij; ovqjKj ), the relational context of rij is enriched by a line for ovqjKi , Algorithm 2: Case pure query
Let a = (qjKs ; rst; qjKt ) if // X does not contain a source and a target for the current arc a X \ Os = ; and X \ Ot = ; then // select a source in the extent of a concept that veri es the source query Let Cs be the highest concept having Intent (Cs) qjKs select os 2 Extent(Cs)
X X [ fosg if // X contains a source and a target for the current arc a X \ Os = fosg and X \ Ot = fotg then // verify that the source is connected to the target check 9rst ot 2 Intent( os ) else if // X contains a source for the current arc a X \ Os = fosg then // select a target in the extent of a concept that veri es the target query 11 and is connected to the source Let Ct be the highest concept having Intent (Ct) qjKt and Ct 2 min(C j 9 (9rst C) 2 Intent( os)) select ot 2 Extent(Ct)
X X [ fotg else Algorithm 3: Case pure objects
Let a = (qjKs ; rst; Oq) with Oq Ot if // X contains a source for the current arc a X \ Os = fosg then // verify that the source is connected to the objects in Oq check 8o 2 Oq; 9rst o 2 Intent( os ) else // X does not contain a possible source // select a source in the extent of a concept that veri es the source query // and is connected to the target objects Let Cs be the highest concept having Intent (Cs) qjKs and 8o 2 Oq; 9rst o 2 Intent(Cs) select os 2 Extent(Cs) X X [ fosg a column for ovqjKj and the relation (ovqjKi ; ovqjKj )2. We generate the corresponding concept lattice family, considering the existential scaling 3. Locating the highest concept that introduces all the attributes of each query of each concerned context, now is much more easy because it introduces the virtual query object. Then, we can navigate in a similar way as before.
Opportunities of browsing o ered by the exploration. As we explained before, the algorithm described in the previous section can be understood as an automatic procedure to determine a solution to a query. Nevertheless, it is more interesting to use it as a guiding method for the exploration of data by a human expert. Each object selection is a departure point for inspecting the objects of the selected concept, and, explore the neighborhood, going up by relaxing constraints or going down by adding constraints.
A point in favor of the lattices is that they do not only give us a solution, but they also classify the objects of the solutions and provide a navigation structure. They also carry other information about the objects which can be useful for the expert: attributes that objects of the answer set have necessarily, attributes that appear simultaneously as attributes of the answer, etc.
In our Web service application, we preferred the solution which integrates the query in RCF because it was easier to identify the answers. The lattices show how the existing objects match and di er from the query, thanks to the factorization of attributes between the query and the existing objects. Nevertheless, having several queries at the same time would not be e cient. Thus, the solution has been used only for speci c problems. An incremental algorithm can be used to introduce the query, which enlightens the process of modifying the lattice and highlights the structure of the data. We can keep the original lattice (before query integration), and save the query objects together with the resulting concepts in an auxiliary structure. This way, we can always easily go back to the original lattices. 5
ER-compatible data, e.g., relational databases, and concept lattices have a long
history of collaboration. First attempts to apply FCA to that sort of data go
back to the introduction of concept graphs by R. Wille in the mid-90s [
Alternatives to the PCF in the interpretation of concept graphs have been
proposed that involve the notions of nested graphs and cuts [
Existing approaches outside the concept graphs-based paradigm (see [
For instance, in [
Recently, a less expressive language has been proposed in [
The downside of remaining free of the extensive commitments made by the concept graphs formalism both in terms of syntax and of semantics is the lack of uni ed methodological and mathematical framework beneath this second group of approaches. As a result, these diverge on a wide range of aspects which makes their in-depth comparison a hard task.
First, there is an obvious query language expressiveness gap: On that axis, the
two extremes are occupied by the LCA- and the RCA-based approaches,
respectively, the former being the most expressive and the latter, the less expressive
one. Then, the role played by the concept lattices vs. the query resolution is
speci c in each case. While in the LCA-based approach the concepts seem to
be formed on the y, in [
In this paper, we have presented a query-based navigation approach that helps an expert to explore a concept lattice family. The approach was based on an application of Relational Concept Analysis to the selection of suitable Web services for instantiating an abstract service composition. There are many perspectives of this work. In our Web service experience, we tested other scaling operators (like the covers operator) that o ers other results, and helps to nd more easily the aggregate answers. The query language can be made more expressive (including quanti ers). For example, we can request dishes containing only fchicken, cheese, ...g, which means that the universal scaling operator shall be used in the RCA process for this particular relation. Besides, the query path can be calculated, rather than being de ned by the expert, suggesting more e cient exploration paths.