In traditional databases and information systems the number of users is more or less known and their background is to a great extent homogeneous. In distributed and heterogeneous environments however such as the Web, users do not apply the same conventions when interpreting data due to di®erent backgrounds, knowledge or culture. Interpreting and managing data according to the context is a topic not explored in its full potential in these new environments. In this work we present the Context Relational model (CR model), a model that extends the relational model to argue also about context. The interesting part of this approach is that context is treated as ¯rst-class citizen at the level of database models and query languages. This is due to the fact that an attribute may not exist under some contexts or that the attribute may have di®erent values under di®erent contexts. Apart from the model description this work presents also a set of basic operations which extend relational algebra so as to take context into account.
Information today is accessed and used in a global environment, where assumptions about data become less evident. Users with di®erent backgrounds or viewpoints may interpret the same data in a di®erent way. Moreover, the interpretation and suitability of data may depend on unpredictably changing conditions, like for example the current position of the user or the media he is using (laptop, mobile, PDA). To avoid such ambiguous situations the information provider needs to specify the context under which information becomes relevant. Conversely, information users can specify their own current context when requesting for data in order to denote the part that is relevant to their speci¯c situation.
For instance imagine a product whose speci¯cation changes according to the country it is being exported. Or a Web page that is to be displayed on devices with di®erent capabilities, like mobile phones, PDAs, and personal computers. Another example is a report that must be represented at various degrees of detail and in various languages. In those situations, context can be used as a viewpoint mechanism that takes into account implicit background knowledge.
In previous work [SG02,Sta03] we argued that the management of context should take place at the level of database systems in a uniform way and that consequently context should be treated as a ¯rst-class citizen in data models and query languages. In particular, relational databases (R-DBs) can no longer be seen as isolated data sources, where users are familiar with the implied assumptions necessary for interpreting the data they retrieve. Today R-DBs are widely used in Web applications for dynamically constructing Web pages that are globally available. They are also used as back-ends in systems where context information is constantly provided by sensors. It is therefore interesting to examine how the notion of context can be incorporated in a R-DBMS.
In [Sta03], it has been shown that direct incorporation of context in database management systems would have the following positive results: a) management of data according to the interpretation frame, b) ability to pose cross-world queries that have no counterpart in context-unaware systems, c) personalization in a °exible and uniform manner and d) direct support for managing data and schema histories.
In this work we study the problem of incorporating context in the relational database model, which has a strong formal background, and propose a novel infrastructure. We present the Context Relational model (CR model) that can be viewed as an extended relational model able to argue about context as well. The proposed model is able to accommodate information entities that manifest di®erent facets, whose contents can vary in structure and value. Each facet of such a multi-faceted information entity is associated with a context, stating the conditions under which this facet holds. We then discuss some operations through example queries that demonstrate the potential of this model.
The rest of the paper is organized as follows. Section 1.1 presents related work. In Section 2 the notion of context is revised. In Section 3.1 we give a motivating example to facilitate the understanding of our model. In Section 3.2 we discuss the technical challenges of our work and the advantages of our framework. In Section 3.3 we describe in detail the CR model. Section 4 presents the basic operations of an extended algebra that incorporates context through example queries. In Section 5 we state the di®erences of the CR model relatively to the relational model. Finally Section 6 discusses possible future research directions. 1.1
The notion of context was originally introduced in Frege's proposal of a principle of contextuality [Fre84]. Since then, context has been called to account for a variety of problems in di®erent areas. Context has been used in diverse areas of computer science as a tool for reasoning with viewpoints and background beliefs, and as an abstraction mechanism for dealing with complexity, heterogeneity, and partial knowledge. A formal framework for reasoning upon a subset of a global knowledge base can be found in [GG01], which is extended in Local Relational Model [SGMB03,BGK+02] to allow for inconsistent databases and to support semantic interoperability in the absence of a global schema. Examples of how context can be used for partitioning an information base into manageable fragments of related objects can be found in [MMP95,TACS98].
In Web information systems context is often de¯ned by giving values to a number of user-de¯ned variables called dimensions or characteristics. By assigning values to such variables, users can constraint the information that is relevant to them by explicitly specifying the way they interpret data. In [Bro98,Yil97], Intensional HTML is introduced to address the problem of constructing and maintaining Web sites that must exist in many versions, for example depending on the language, user expertise, subscription level, screen resolution.
In multidimensional semistructured data [Sta03,SG02] similar principles are applied to represent semistructured information entities that assume di®erent facets, with varying content (value and/or structure), under di®erent contexts. This approach sees context as a set of constraints, which are combined through context operations to specify environments under which information obtains an unambiguous meaning. Such an environment is called a world, while constraints are expressed by assigning values to dimension variables. The work in [SGDZ04] shows how context can be used to represent and query valid time of data and histories of semistructured databases.
This perception of context has also been used in OMSwe, a Web-publishing platform described in [NP03b,NP03a]. OMSwe is based on an Object DBMS, which has been extended to support a °exible, domain-independent model for information delivery where context plays a pivotal role.
New mobile-aware applications are more e®ective and adaptive to user information needs without consuming too much of a users attention, by taking advantage of the dynamic environmental characteristics, such as the user's location, time, people nearby, etc. A detailed survey about exploiting context-aware computing in mobile environments is presented in [CK00]. In [DVV03], the authors propose a context-aware service discovery, describing a context-based index to support e±cient retrieval of Web services whereas in [VVV+03] a platform is presented for sharing context dependent data and services for mobile sources, called MobiShare. 2
In our approach, a world represents an environment under which data obtain a substance. The set of parameters used to specify the world are called dimensions. A context speci¯er is a syntactic construct used to qualify pieces of data and specify sets of worlds (or contexts) under which these pieces hold. In this way, it is possible to have at the same time variants of the same information entity, each holding under a di®erent set of worlds, or equally under a di®erent context. The variants of an information entity are called facets of the entity and they may di®er in value and/or structure.
De¯nition 1. Let D be a nonempty set of dimension names and for each d 2 D, let Vd be the domain of d, with Vd 6= ;. A world w with respect to D is a set of pairs (d; v), where d 2 D and v 2 Vd, such that for every d 2 D exactly one (d; v) belongs to w.
In the model we present in Section 3, sets of worlds are represented by context speci¯ers, which can be seen as constraints on dimension values. Example 1. Some context speci¯ers might be the following: (a) [device=PC] (b) [device=PDA, payment in {credit card, cash}]
In Example 1, context speci¯er (a) represents the worlds for which the dimension device has the value PC, while (b) represents the worlds for which device is PDA and payment is either credit card or cash. It is not necessary for a context speci¯er to contain values for every dimension in D. Omitting a dimension implies that its value may range over the whole dimension domain.
The context speci¯er [] is a universal context and represents the set of all possible worlds, while the context speci¯er [-] is an empty context and represents the empty set of worlds. In [SG02,Sta03] operations on context speci¯ers are de¯ned and it is presented how a context speci¯er can be transformed to the set of worlds it represents with respect to a set of dimensions D. In the case where two context speci¯ers represent disjoint sets of worlds the context speci¯ers are called mutually exclusive. 3
In this section we start with an example used throughout this paper and we continue with stating some of the challenges we had to face. Then we present in detail a Context Relational Model (CR model) for the representation and manipulation of information under di®erent worlds. 3.1
Example 2. Consider a Web site about digital cameras. The information provided for each camera includes the brand name, the model of the camera, a picture, the size in megapixels and the price. Customers connect to this Web site using a variety of devices ranging over desktop computer (PC), PDA and cell phone. Moreover, they can select the method of payment between Credit Card and Cash.
The data about a digital camera returned to customers depends on the browsing device and payment method. That is, a customer using a PDA receives a picture of lower resolution than when using a PC. When using a cell phone no picture exists and only textual information is provided. Moreover, the price of a digital camera varies according to the payment method. Evidently, digital camera is an information entity whose contents and structure in this particular example vary according to the browsing device and the method of payment.
In database terms there is a main relation dcamera, with attributes: Brand, Model, MPix, Photo, Price (see Table 1b). Customer requests are expressed as queries and the data returned correspond to the evaluation of the queries over this relation. The context of the example relation is expressed through the following dimensions: device ranging over fPC, PDA, CELLg, payment ranging over fCredit Card, Cashg.
The schema of relation dcamera and the data for a particular entity may di®er between di®erent worlds. This is due to the fact that an attribute may not exist in some worlds and that the same attribute may have di®erent values under di®erent worlds. Table 1a presents all the possible worlds, while Table 1b presents the worlds under which each attribute is de¯ned.
World Device Payment
The relational model does not treat context and entities as ¯rst class citizens. As a result, the de¯nition and manipulation of information that exists in multiple worlds is done at application level. This has a series of disadvantages: 1. Redundancy, as the logic and the di®erent basic operations must be reimplemented in each application. 2. Implementations that are strictly connected to speci¯c design decisions and the nature of each application. 3. Maintenance overhead.
There are two other approaches for dealing with context. In the ¯rst approach context is managed by the application logic at a separate level from data management leading to an in°exible and hard to maintain architecture, whereas ad-hoc solutions must be developed from scratch for every new case. In the second approach, context is managed in a mediator, at an intermediate layer between the data source(s) and the application(s). In this approach the mediator contains context metadata that are "linked" to the information parts they annotate at the sources. Queries are addressed to the mediator, which uses context metadata to navigate to the relevant data.
Handling context at the level of information sources (ie. database systems) has the following advantages: 1. Comprehensive data design: context and its relation to data are taken into account at the stage of schema design. This introduces an additional complexity to schema design, however the incorporation of context conditions into the DB schema enables also the consistency checking of insertions and updates of context-dependent data. 2. Wider spectrum of queries: data models and query languages that directly incorporate context can be more expressive, leading to new sorts of queries (cross-world queries [Sta03]), like "show the pictures of cameras that are more expensive when paying in cash than when paying using credit card", or data management queries like "under which contexts there is no picture". 3. E±cient access: by pushing context management at the level of information sources, the database systems have complete control and can use their context-aware schema information as well as potentially especially designed access methods to improve e±ciency. 3.3
In the previous section we argued that context should be incorporated in database engines. In this next section we present in detail the proposed CR model. The basic notion of our model is the multi-facet entity. A multi-facet entity is an information entity which assumes di®erent facets as de¯ned under di®erent worlds. In the remaining of the paper, when we write entity we mean a multifacet entity. A facet fi;j is the variant of an entity ei de¯ned under a speci¯c world wj . A set of entities are grouped to form a context relation.
For a context-relation R, a number of attributes are de¯ned in each world. The sets of attributes de¯ned for R in two di®erent worlds can (i) be the same, (ii) have a common subset or (iii) have no common attributes at all. Moreover, the same attribute Ai of a single entity can have di®erent values in di®erent worlds. We refer to the value of an attribute Ai in world wj as Aifwj g.
Entity <e1> <e2> <e3>
In Figure 1 we present the context-relation dcamera of Example 2. In order to show the basic parts of our model, we highlight the entity e4, the attribute Photo and the world w2.
Entities belonging to context-relation dcamera have values for the six worlds of Table 1a. As stated in Table 1b, attribute Photo is not de¯ned for worlds w3 and w6 (device = CELL PHONE), it stores a high resolution photo for worlds w1 and w4 (device = PC) and a low resolution one for worlds w2 and w5 (device = PDA). Also the value of attribute Price depends on the payment dimension. For example, entity e4 has Pricefw1g = 154 and Pricefw4g = 142.
A context-relation can be viewed as a cube. Each entity of the relation is an horizontal slice spanning across all the worlds. Each entity slice has jaj ¤ jwj cells, where jaj is the total number of attributes of the entity and jwj is the total number of worlds in the system. A cell fi,jg in this slice represents the attribute Aifwj g. In Figure 1, we highlight entity e4, which is a two-dimensional 5*6 horizontal slice, as context-relation dcamera has ¯ve attributes and is de¯ned for six worlds. Attribute Model is the second attribute of context-relation dcamera and f Cell Phone ,Credit Cardg is the third world, so cell f2,3g represents attribute Modelfw3g for entity e4.
An attribute is a two-dimensional jej ¤ jwj vertical slice, where jej is the total number of entities in the context dependent relation. A cell fi,jg in the slice corresponding to attribute Ak represents the value of Ak for entity ei in world wj . Proportionally, a world is a two-dimensional jej ¤ jaj vertical slice. Each facet of an entity ei is represented by the intersection of the slice entity for ei and the world slice for the corresponding world.
Modeling entities and attributes as two-dimensional slices allows us to exhibit these relations and interpret queries over di®erent worlds in a more meaningful way. For example, in Figure 1, we highlight attribute Photo. The response to a query that asks for the photos of entity e4 is represented by the intersection of the vertical attribute slice for attribute Photo and the horizontal entity slice for e4. The response to a query that asks for all the photos in world w2 is represented by the intersection of the two vertical slices for attribute Photo and world w2. Finally, the intersection of the three slices corresponds to the value of attribute Photo for entity e4 in world w2. 4
In this section we present the basic operations (projection, selection, cartesian product, join and set operations ) of the relational algebra extended to incorporate context. To distinguish them from the classical operations, we use the term context in front of them, as for instance context-project. We keep the relational symbols, e.g. ¼ for context-project.
Given an input context-relation, the objective is to output only the attributes speci¯ed in the condition of the context-project operator. The result is a new context-relation that has only the vertical slices that correspond to the projected attributes. The resulting context relation will still include slices for all possible worlds, however will only contain actual values for the projected part (highlighted cells in ¯gures of this section).
For example, in Figure 2(a) we see the result of projecting attributes Model, MPix and Price:
¼Model[ ]; MP ix[ ]; P rice[ ]dcamera
Note that a context speci¯er follows each attribute. Specifying the context of the projected attributes is crucial when we are interested in the values of attributes only for some worlds. For each attribute, the context speci¯er denotes the set of worlds that will be projected.
Figure 2(b) illustrates the following query, which projects attributes Model and MPix for world w1 and attribute Price for worlds w2 and w4: ¼Model[Device=P C;P ayment=CreditCard];MP ix[Device=P C;P ayment=CreditCard];
P rice[Device=P DA;P ayment in fCreditCard;Cashg]dcamera
This operation retains only those facets of entities that hold under speci¯ed worlds. For example, for a customer using a PC the relevant worlds are w1 and w4. We use the letter · to represent the world-project operator: ·[w1;w4]dcamera
The entity context-select operation uses context in order to express conditions that involve attribute values under di®erent worlds. The following queries illustrate this point. Note that we use the symbol ¾entity to denote the entity context-selection. Figure 3(a) highlights digital cameras created by Kodak, with more than three megapixels.
¾(eBntRitAyND[ ]=0Kodak0 AND MP ix[ ]>3)dcamera
A simpler case where selection criteria is restricted to the values in speci¯c worlds is illustrated by the following example query, which selects only entities where the price is less than 250 when the customer is paying in cash: ¾(eBntRitAyND[ ]=0Kodak0 AND P rice[Device=P C;P ayment=Cash] < 250)dcamera Notice that an attribute may appear more than once in the same condition with di®erent context speci¯er. The following query is a cross-world query that compares the values of the same attribute in di®erent worlds, asking for cameras that have lower price if the customer pays in cash than using a credit card: ¾(ePntriitcye[Device=P C;P ayment=Cash] < P rice[Device=P C;P ayment=CreditCard])dcamera
In the previous queries each attribute in the select condition is evaluated in the set of worlds indicated by the respective context speci¯er. In case there is no context speci¯er for an attribute, we evaluate the condition to true if there exists at least one world where the condition holds. For instance, the following query requests for entities where at least one facet has Price less than 250 Euros: ¾(eBntRitAyND[ ] = Kodak AND P rice < 250)dcamera
Users should be able to pose queries that involve selection of facets or, in other words, to select parts of an entity. This can be done using the facet context{select operator, denoted ¾facet. The ¾facet operator selects only the facets of an entity that satisfy the condition, instead of the whole entity as the ¾entity operator.
In Figure 3(b) we present the result of selecting facets with Price less than 500 euros. Note that the select facet operation is a basic operation in our algebra as it cannot be constructed by any combination of the other operations.
In a way similar to the relational model, context cartesian product creates new context-relations from existing ones. For the needs of our example Figure 4(a) presents a new context-relation named accessories. The attributes de¯ned for accessories are the accessory name, the model of the corresponding digital camera that the accessory ¯ts in, a description of the accessory and its price. Attribute model serves as a foreign key to the dcamera context-relation.
Name Model Desc Price
Brand ... Price Name Model ... Price
The cartesian product of context-relations dcamera and accessories is presented in Figure 4(b). The attributes of the resulting context-relation are the attributes of dcamera and accessories. Entities of the new relation are constructed by combining each entity of dcamera with all the entities of accessories.
A context-join is de¯ned as the composition of the context cartesian product and the entity context-select operations, as in the relational model. As an example, consider a query that asks for Kodak digital cameras with cheap 200mm lens (e.g. where accessories:P rice < 0:2 ¤ dcamera:P rice). Apart from the contextjoin, which adds no new complexities in our algebra, there is a need for a more restrictive join operation, named context natural join. This operation is necessary for selecting entities where (dcamera.Model = accessories.Model) for all worlds.
Set operations like union, intersection, di®erence and division are de¯ned only for context-relations that are union compatible. In order for two context relations to be union compatible, they must have exactly the same attributes de¯ned under each world. The semantics is the same as in set theory, but with entities as the basic set elements.
The following example brings together many of the operations presented in this section. Consider a customer who uses a PC and wants to buy a Kodak camera costing less than 400 Euros. He/she also wants to buy accessories for this camera, so for all selected cameras he/she then requests to see all available accessories. Finally, he/she asks the price using cash for camera and credit card for accessories. In database terms he/she requests dcamera.Price for cash and accessories.Price for credit card: Ctx-Rel1 Ã context cartesian product(dcamera; accessories) In this section we discuss the di®erences of the CR model relatively to the relational model. Although relational model can be in principle used to represent context dependent information, context as such cannot be handled in database level but through the use of application logic. In the CR model context is treated as a ¯rst class citizen added at the level of databases, enabling a uniform approach to context and the de¯nition of context aware structures and operations.
In the CR model, a world slice wi is a classical relation as in the relational model. The tuples of this relation would correspond to the facets of the entities for this world. One can argue that instead of a context-relation that is de¯ned in k worlds we could have a set of k relations (as de¯ned in the relational model). Another approach would be to create a single denormalized relation with as many attributes as the sum of the number of attributes de¯ned in each world.
The main inconvenience of the relational model is that there is no way to de¯ne the relation between the same attribute under di®erent worlds. Regardless of whether a context-relation is de¯ned by k di®erent relations or a single denormalized relation, the fact that two attributes represent the same attribute of an information entity under di®erent worlds cannot be modelled.
If we decompose a context-relation to a series of relations, the link between facets that consist a single information entity is lost. This link is used in the CR model to formulate cross-world queries. Similarly, in the case of a single denormalized relation there is no way to specify the attributes that belong to a speci¯c world and ask intra-world or cross-world queries. Moreover, maintaining a large number of relations (normalized approach) or relations with hundreds of attributes (denormalized approach) adds a great deal of complexity in the process of designing or altering the schema representing a context aware database. 6
In this work we studied the incorporation of context into relational database systems and we presented the CR model that can argue about context as well. Our primarily aim was to allow the management of context to take place at the level of database systems. The proposed framework should also model heterogenous environments where users may receive di®erent responses for the same query depending on the context. This is a consequence of our view of the model, where an attribute may not exist in some worlds or the same attribute may have di®erent values under di®erent worlds. The challenging part of this work consisted on how to extend the classical operations of relational algebra to include context and enable users to pose cross world queries. As future work we plan to: - Extend the relational calculus and algebra to incorporate context. - Propose a context-aware query language for the CR model. - Demonstrate possible uses of our approach through example applications. In previous work, context has been used to represent time [SGDZ04]. In this case it could be possible to use the CR model for representing and querying histories of data. Moreover, in [GSK+01] the authors have shown how context can be used to achieve personalization in a uniform way at the database level. - Design e±cient access methods to take context into account.