Mobile devices provide a variety of ways to access information resources available on the Web and a high level of adaptability to di®erent aspects (e.g., device capabilities, network QoS, user preferences, location, an so on) is strongly required in this scenario. In this paper we propose a technique for the e±cient adaptation of Web Information Systems. The approach relies on special rules that allows us to specify, in a declarative way, how to generate, in an automatic way, the adaptation speci¯cations that satisfy the requirements of a given context. Rules are classi¯ed in a set of clusters and a matching relation between clusters and context requirements is de¯ned. The technique of rule evaluation and clustering guarantee that di®erent contexts and orthogonal requirements of adaptation, possibly not ¯xed in advance, can be e±ciently organized and taken into account in the adaptation process.
Modern Web Information Systems (WIS) are challenged to generate (automatically) a hypermedia presentation built from information that is gathered from di®erent, possibly heterogeneous, sources that are distributed over the Web. Nowadays, given the spread of mobile devices, a novel and fundamental requirement of these systems is the ability to adapt and personalize content delivery according to the context of the client. An important point that needs to be taken into account is that this scenario is very dynamic: some aspects of the context can dynamically change. For instance new users with new preferences can be enabled to access the information system, possibly unpredicted types of access devices can be used, alternative network connections can be made available, further aspects of the context (like the location or others environmental factors) need to be incorporated. Also, the technology used to implement the adaptation can be changed and this should have a limited impact on the overall application. It follows that the adaptation process should guarantee a high level of °exibility in terms of responsiveness to rapidly changing requirements of adaptation and suitable actions to be undertaken to meet these requirements.
In the literature, some adaptation approaches rely on the de¯nition of rules
to generate suitable adaptation speci¯cations [
The rest of the paper is organized as follows. Section 2 introduces the rulebased approach. In Section 3, we illustrate how to de¯ne the set of clusters and the process to e±ciently activate a rule, using the clusters. In Section 4 we present a practical implementation and experimental results and ¯nally, in Section 5 we draw some conclusions and sketch future works. 2
In this section we present special rules to specify, in a declarative way, how to generate, in an automatic way, adaptation speci¯cations. The rules are based on two basic notions: the generic pro¯le and the abstract con¯guration. 2.1
A (generic) pro¯le is a description of an autonomous aspect of the context in which the Web site is accessed (and that should in°uence the presentation of its contents). Examples of pro¯les are the user, the device, the location, and so on. A dimension is property that characterizes a pro¯le. Each dimension can be conveniently described by means of a set of attributes. Attributes can be simple or composite. A simple attribute has a value associated with it, whereas a complex attribute has a set of (simple or complex) attributes associated with it. In this model, a context is a collection of pro¯les. Figure 1 reports a graphical example of pro¯les. In our model, di®erent pro¯les over the same dimensions can be compared making use of a subsumption relationship C. Intuitively, given two pro¯les P1 and P2, if P1 C P2 then P2 is more detailed than P1 since it includes the attributes of P2 at the same or at coarser level of detail. More precisely, we ¯rst say that an attribute A covers another attribute B if either they are simple and A = B or they are composite and for each sub-attribute Ai of A there is a sub-attribute Bj of B such that Ai covers Bj . The subsumption relationship is then de¯ned as follows.
De¯nition 1 (Subsumption) Given two pro¯les P1 and P2, we say that P1 is subsumed by P2, P1 C P2, if for each dimension d of P1 there is a dimension d' of P2 such that for each attribute A of d there is an attribute A' of d' covered by A.
As an example, given the pro¯les reported in Figure 1 we have that P2 C P1
and P3 C P2.
2.2
We introduce the notion of (abstract) con¯guration as a triple C = (q, h, s)
where:
{ q is a query over the underlying database expressed in relational calculus, a
declarative and abstract language for relational databases ([
An example of con¯guration is reported below. s = h =
It is important to note that a con¯guration is indeed a logical notion that can be represented and implemented in several ways and with di®erent syntaxes. This property guarantees the generality of the approach with respect to actual languages and tools used to implement the adaptive application. For instance, we can implement a con¯guration using SQL at the content level, XHTML at the navigation level and a set of CSS ¯les at the presentation level. 2.3
The matching relationship between con¯gurations and pro¯les is represented by means of a novel notion of adaptation rule. An adaptation rule has the form Pr : Cd ) Cf where: ² Pr is a parametric pro¯le, that is, a pro¯le in which parameters can appear in place of values, ² Cd is a condition, made out of a conjunction of atoms of the form AµB or Aµc, where A and B are parameters occurring in Pr, c is a constant value, and µ is a comparison operator, ² Cf is a parametric con¯guration in which parameters occurring in Pr can appear in place of values.
The intuitive semantics of an adaptation rule is the following: if the client has a pro¯le Pr and the condition Cd is veri¯ed then generate the con¯guration Cf .
An example of adaptation rule for a device pro¯le with the hardware dimension H is the following:
H (ImgCapable : X ; ScreenSize : Y ; ColorCapable : Z ) :
X = false; Y < 1500 ) fq; h; sg where X, Y , and Z are the parameters of H and fq; h; sg is the following parametric con¯guration: s = h = q = f T : x1 ; S : x2 ; D : x3 ; C : x4 j
NewsItems(N : x0 ; T : x1 ; S : x2 ; D : x3 ; G : x5 ; J : x6 ); Details(NK : x0 ; P : x7 ; C : x4 )g Page NewsPage ( units NewsIndex ) Page ContentPage ( units ContentData ) IndexUnit NewsIndex ( source News Items; attributes Title, Date;
orderby Date ) DataUnit ContentData ( selector Item = CurrentItem;
attributes Title, Date, Content) link NewsToDetails ( from NewsIndex to ContentData
parameters CurrentItem = NK) Text( Color: Black, Size: 8pt) Link( Style: Underline, Color: Black)
Image( Size: Y £ 0; 5, Color: Z) Note the use of the parameters Y and Z of H to resize the images and to eliminate/maintain colors.
A pro¯le P activates a rule Pr : Cd ! Cf if Pr C P . Hence, a pro¯le P can activate a rule for a pro¯le that is more general than P . Now, let R be a rule Pr : Cd ! Cf activated by a pro¯le P and let C be the con¯guration obtained from Cf by substituting the parameters of Pr with the actual values occurring in P : we say that C is generated by P using R. 3
We assume to have at disposal an initial set of rules SR. In an adaptability scenario, context changes generate events that produce one or more pro¯les (instances). Each pro¯le (instance) can activate a rule of SR. We should optimize the research to select and activate e±ciently the most appropriate rules and generate the most suitable con¯guration. So we organize SR classifying the rules in a set of clusters. Each cluster represents a class of adaptation that matches the requirements of a class of context. 3.1
We de¯ne a distance that allows to compare pro¯les. We take advantage of the
tree structure of the generic pro¯le. We get inspiration from the Tree Edit
Distance [
So we can intuitively de¯ne the distance between two pro¯les P1 and P2, the minimum cost for a S-derivation between them.
De¯nition 3 (Distance between pro¯les) Given two pro¯les P1 and P2, we de¯ne the distance between them as dted(P1; P2) = minf°(S ¡ derivation) j Sderivation from P1 to P2g 3.2
Let's represent a cluster as a tree where the nodes are pro¯les. The root represents the minimum set of information that nodes of the tree share. Basically a client is identi¯ed by the pro¯le sent to the system. Let's remember that a pro¯le is principally described by dimensions, that characterize the main information, articulated in attributes. So, the root of a cluster is a pro¯le characterized only by dimensions. It will contain the minimum information that several pro¯les has to include to be in the same cluster. Given a pro¯le P, pruned by all attributes, we can build several beginner clusters, rooted with pro¯les generated from P, on the number and type of dimensions. However the designer can decide the detail level for the roots. For instance a designer can decide to articulate some dimensions of a root with attributes, to extend the level of detail of the minimum information to share.
We de¯ne a cluster as follows De¯nition 4 (Cluster Tree) A cluster CL is a couple fNCL; ECLg where NCL is the set of nodes (pro¯les) and ECL is the set of edges (ni; nj ) such that ni / nj We can relate a node Pr of a cluster with the rule Pr : Cd ! Cf in an Hash table using Pr as access key.
Given the set of roots Rt = fRt1 , ... ,Rtn g and the set of rules SR, we initialize a set of clusters CL = fCL1, ... ,CLng as follows: ² we set CLi = ffRti g,;g, ² 8 (Pr : Cd ! Cf ) 2 SR, (i) we search a CLi such that Rti C Pr, and we navigate the cluster in depth until level k where doesn't exist any node subsumed by Pr, (ii) we search at level k ¡ 1 the node N d such that N d C Pr and if there are more nodes N d such that N d C Pr we choose the node with lowest distance, (iii) we add Pr to NCLi and (N d; Pr) to ECLi , (iv) if there are one or more nodes N di such that Pr C N di then we delete any edge of type (N dj ,N di) in ECLi and add to it the edge (Pr, N di), ² for each node of a cluster we add the relative rule to the Hash table. 3.3
Built the set of clusters, now we can perform an optimization strategy to activate a rule in an e±cient way. Given the set of rules SR, the set of clusters CL = fCL1; CL2; :::; CLng, the Hash table Ht and a pro¯le instance PI of a pro¯le schema PS , we produce a set of con¯gurations as follows: 1. we initialize P 0 with PS ; 2. we search the cluster CLi in CL, with a root Rti such that Rti C P 0 and that has the lowest distance from it; 3. (i) we navigate in depth the cluster until level k where any node, that is subsumed by P 0, doesn't exist; (ii) we search at level k ¡ 1 the node N d such that N d C P 0 and if more nodes are subsumed by P 0 we choose the one with lowest distance; (iii) we extract the rule Rl, related in the Ht to N d, and if the condition is satis¯ed, we activate Rl and instance the con¯guration with the value of PI ; (iv) we update P 0 as P 0 - N d; 4. we iterate from step (2.) until P 0 is not empty and a rule that can be activated by P 0 exists; 5. if no rule can be activated in this way, the system will return a default con¯guration. 3.4
Let's assume a client sending a pro¯le PI (see Figure. 2(a)), instance of a pro¯le schema P to the system. Assume also that the system has already initialized its own set of clusters, composed by clusters C1 and C2 (see Figure 3). We easily see that the root of the cluster C2 is the one which subsumes P and has the lowest distance from it. So we navigate that cluster and note that the only child N of the root it is equal to P ; then we extract the rule Rl related in the Ht to N and if the condition is satis¯ed, we activate it and instance the con¯guration with the values of PI . Subsequently, assume that a new pro¯le PI0 (see Figure 2(b)), instance of a pro¯le P 0, is sent by another client to the system. At the same way explained before, we see that the root of the cluster that subsumes P 0 and has the lowest distance from it, is cluster C1 root. Navigating that cluster, we need to confront P 0 with root's two children. We easily see that no one of them is equal to or has a subsumption relation with P 0: being their parent a root, is not possible to activate its rule; so, as we explained before, the system will return a default con¯guration.
Device Hardware
Device Hardware We can easily see that using this clustering algorithm we can reduce the number of accesses to SR. In our system, we have seen that a pro¯le given by a client can activate a rule in the default set. So when a client sends a pro¯le to the system it has to search for the most suitable rule in SR. We can assume that the worst case is when the system has the greatest possible number of default rules, that is when the system has in SR one rule for each possible pro¯le that a client can send. Without using clusters we should execute a number of ordered accesses equal to the total number of possible pro¯les. It is easy to see that the number of possible pro¯les is the number of pro¯les obtained with every possible di®erent combination of dimensions and attributes. Assuming to have a complete schema with n dimensions and m attributes for each dimension, we can see that the number of di®erent combinations of dimensions is Pin=1 ¡ ni¢ while the number of di®erent combinations of attributes for each single dimension is Pjm=1 ¡ mj¢. Combining these two results and looking carefully at our structure, we see that the number of di®erent pro¯les is equal to Pin=1 hPjm=1 ¡ mj¢i(i¡n1) (n ¡ i + 1). If we use the clustering algorithm, in this case we will obtain a number of clusters equal to the number of di®erent combinations of dimensions, seen above. To access the right clusters, the system has to access to all of their roots and then ¯nd the right way on the selected tree. So it can ignore a number of trees equal to Pin=1 £¡ ni¢¤ + 1.
We can see that in this situation the worst case is when the root of the selected cluster has the maximum number n of dimensions, because it would be the tree with the maximum number of nodes. The remaining clusters will contain a num( n ) ber of pro¯les equal to Pin=¡11 hPjm=1 ¡ mj¢i i¡1 (n ¡ i + 1). These pro¯les will be ignored by the system, which has only accessed the roots of their clusters, that are not pro¯les. So, counting also these accesses, we ¯nd that at least we obtain to ( n ) save a number of accesses equal to Pin=¡11 hPjm=1 ¡ mj¢i i¡1 (n ¡ i + 1)¡Pin=1 ¡ni ¢. This number doesn't take count of the fact that the system won't access all the nodes of the selected cluster, but only some of them, depending on its structure. Anyway it gives evidence that, using this clustering algorithm, it is possible to obtain a certain bene¯t in terms of number of accesses. 4.2
We have designed and developed a practical implementation to test the our
approach. The system relies on an RDF database of contents and the selection of
data is done by performing RDF queries expressed in SPARQL [
In this paper we have presented a novel rule-based approach supporting the automatic adaptation of content delivery in Web Information Systems. This problem arises in common scenarios where the information system is accessed, in di®erent contexts, by a variety of mobile devices. The adaptation is achieved automatically by means of special rules that specify, in a declarative way, how a con¯guration can be generated to meet the requirements of adaptation of a
List of Rules Clusters of Rules desktop
pda devices
wap given pro¯le. Finally the organization of rules in a set of clusters guarantees the responsiveness of the system in a dynamic scenario. Di®erent contexts and orthogonal requirements of adaptation, possibly not ¯xed in advance, can be taken into account in this process. The results presented in this paper are subject of further conceptual and practical investigation. From a conceptual point of view, we are currently investigating the expressive power of rules and the generality of clusters. In particular we are improving the distance between pro¯les, using a comparison between common pathes. From a practical point of view we are improving the e±ciency of the system and we are extending its functionality.