In this paper, we examine the special requirements of lifecycle management for entities in the context of an entity management system for the semantic web. We study the requirements with respect to creating and modifying these entities, as well as to managing their evolution over time. Furthermore, we present the issues arising from the access control models needed for the management of a large, distributed repository of entities. Finally, we discuss the research directions that can offer solutions to the above problems, and give a brief overview of techniques and methods relevant to these solution directions.
To date, the natural growth path for computer systems has been in supporting technologies such as data storage density, processing capability, and per-user network bandwidth. The usefulness of internet and intranet networks has fueled the growth of computing applications and in turn the complexity of their administration. The wealth of data that is currently found on the World Wide Web (WWW) is of limited use if it cannot be converted into meaningful information.
The Semantic Web (SW) is an evolving extension of the WWW, in which the meaning
of data and services is defined by attaching semantic concepts to them, making it possible
for applications and machines to make sense of the web content [
One of the major problems that have emerged through the semantic web effort is the
problem of uniquely identifying entities2 [
We claim that the above problem is at the core of the semantic web effort. Along with
the problem of assigning global identifiers to entities in the semantic web also come the
problems of managing these identifiers throughout the entire lifetime of the entities.
Giving solutions to the above issues is the goal of OKKAM [
In such a system, with which a large number of users is expected to interact, it is natural to have diversity among user queries about the same entity. This is due to the fact that their knowledge and viewpoints about the specific entity may differ from each other. Exploiting this innate property of system interaction, the entities in the system repository should respond to this diversity and evolve with time. This evolution can be triggered by nascent (i.e., new knowledge) or tacit knowledge discovery (i.e. discovering duplication, coexistence, resemblance, etc.). The aim of this study is to discuss requirements and propose solution directions for the problems of keeping the data in the OKKAM system that are related to the representation of entities consistent, up-to-date and unsullied. We will collectively refer to all the above problems as the problem of entity lifecycle management.
The rest of the paper is organized as follows. We review the relevant literature in Section 2, and give an overview of the OKKAM system in Section 3. In Section 4, we describe the requirements of the entity lifecycle management. Section 5 outlines the solution we envision and the research directions we are currently pursuing. Finally, we conclude in Section 6. 2 In the rest of this paper, we will use the term entity to refer to individuals, particulars, and instances. This notion of entity is quite liberal, and includes things like products, organizations, associations, countries, events, publications, hotels, people, etc. It may also include fictional objects (e.g., Pegasus), objects from the past (e.g., Plato), or abstract objects (e.g., Gödel’s Theorem).
In this section, we review different approaches related to entity lifecycle management that have been proposed in the literature.
There has been lots of work on rule-based reasoning for data partitioning and placement
techniques [
Various techniques that employ different strategies have been proposed for efficiently
storing different versions of data objects [
When entities are created and modified, we are interested in keeping track of
information related to the provenance of the entity data stored in the repository [
Sometimes the propagation of annotations is dependent on the syntax of the query.
One may want to control the propagation of annotations in a schema. The custom
propagation schemes allow the user to specify where to obtain annotations from. Bhagwat
et al. [
A lot of structural heterogeneity is expected in the OKKAM system (for example,
representing a date as year/month/day in place day/month/year, or the location of a room
as room number-building-university in place of university-room number-building). For
such situations various data cleaning techniques are necessary [
Elmagarmid et al. [
Jaro et al. [
The ALIAS system [
Duplicate detection through record linkage has also been studied [
In this section, we give a brief overview of the OKKAM system (a more detailed
presentation can be found elsewhere [
The overall goal of OKKAM is to handle the process of assigning and managing unique identifiers for entities in the WWW. These identifiers are global, with the purpose of consistently identifying a specific entity across system boundaries, regardless of who and where references this entity. Figure 1 shows a high-level conceptual view of the OKKAM system and the interactions with its environment.
The OKKAM system has a repository for storing the entity identifiers (note that in reality this repository will be distributed and replicated) along with some small amount of descriptive information for each entity. The purpose of storing this information is to use it for discriminating among entities, not exhaustively describing them. Note that there is no fixed schema for this kind of information. Entities are described by a number of attributevalue pairs, where the attribute names and the potential values are user-defined (arbitrary) strings. The exact number of attribute-value pairs used to represent an entity is not preset, but may vary according to the information provided for each specific entity.
Clients interact with the system through the OKKAM Services layer. Clients can be both human users and applications. There are two types of interaction. First, clients inquire about the identifier of an entity by providing a set of attributes that describes this entity. If the entity exists in the repository, the system returns its identifier. Second, clients may insert a new entity in the system. The system returns the newly assigned identifier.
As shown in Figure 1, the end result is that all instances of the same entity (i.e., mentioned in different systems, ontologies, web pages, etc.) are assigned the same OKKAM identifier. Therefore, entity identity resolution becomes trivial, and is done without any further interactions with OKKAM.
In this section we discuss the requirements for entity lifecycle management, in the context of a large, distributed repository of entities for the semantic web. We start by examining the representation of entities. Then, we present the issues arising for the processes of creating, modifying, versioning, and merging entities, as well as keeping track of information relevant to provenance and access control.
The OKKAM system is designed to store arbitrary entities, referring to very diverse domains, including (but not limited to) persons, buildings, documents, and products. As such, the representation of the entities in the system has to be flexible in order to accommodate the requirements of all the different domains. Note that in OKKAM we are merely interested in assigning and managing unique ids to entities, which means that we do not need to represent all the known information about an entity, but rather only a small amount of data that can help us discriminate this entity from all the rest. Nevertheless, the set of data that need to be stored can vary drastically among entities. 4.2
The creation of new entities can be initiated through one of the following two ways: an automatic OKKAM-ization process, or a manual interface-based method. When a document is parsed, entities are identified using an automatic entity identification process that is part of the OKKAM-ization process. When new entities are created, we have to check if these entities already exist in the system. This process can be of two kinds: (a) Offline Check: the entities are added first and checked for duplication later, and (b) Online check: the entities are checked for duplication before they are actually added to the database.
If the entity is unique, it is assigned a unique identifier, and stored in the system. After the entity has been added to the system, it is subject to updates. New attributes may be added to the description of the entity, or the values of existing attributes may change (e.g., when the information is outdated). If the description of an entity changes, we once again have to check if this entity is a duplicate of another entity stored in the repository of the system. 4.3
When entities are created and modified, we are interested in keeping track of
information related to the provenance of the entity data stored in the repository [
The above information can potentially be very useful for other algorithms operating on the entities in the repository, such as matching and merging. For example, this kind of information can allow the matching algorithm to differentiate between attributes modified by humans (i.e., manually) and by computers (i.e., automatically), as well as between attributes that were changed in the recent past (i.e., up-to-date) and the distant past (outof-date). Obviously, the knowledge of how and when each of the data representing an entity has been edited may lead to different strategies for performing entity matching.
The information on data lineage can refer to each entity as a whole, or be more finegrained, and refer to each individual attribute of every entity in the repository. The latter alternative results in a much more detailed view of how all the entity data was inserted in the repository, but also leads to higher space requirements and management cost. The proposed solution will have to take into account this tradeoff between flexibility and implementation cost. 4.4
Regular updates of the attributes describing an entity lead to the creation of different versions of the same entity. In several cases, it is beneficial to store old information for future reference. For example, queries may ask for entities based on old attributes/attribute values.
When a query is performed, the results returned to the user are from the latest information that has been collected after the update procedures. In many cases, once the information is updated, the old information is deleted. Of course we have to define a limit (by date, or by version) with respect to the storage of old records. The user should be given this facility to query across different versions of the entity or in some cases, search the changes that have been performed on an entity over a certain period of time.
The possibility of having different versions of the same entity raises some efficiency questions. The OKKAM system will be deemed efficient if it entails the following properties with respect to efficiency.
Storage: it is important to define the storage schemes and physical representation for versions and the up-to-date information.
Query partitioning and redirection: Defining whether the user wants to search into the up-to-date records or the version, and appropriately redirecting the query. Search and matching: the searching algorithms that are going to fetch the query results for the user. 4.5
Merging of entities may take place when one or more entities exceed some threshold of similarity. Before making this decision, one has to carefully take into account the nature of the considered entities and the tools used to compute this similarity.
As we have mentioned, entities are described by a set of attributes. The values of these attributes can be either numerical (e.g., year, age) or categorical (e.g., name, address). In these cases, it is evident that the same proximity measure cannot be used. Therefore, suitable distance measures will need to be devised, which will also take into account the different characteristics of the various types of attributes.
As more and more entities are added in the system, it may be the case that a single entity is represented by multiple instances in the repository. In such cases, we would like to employ techniques in order to detect such situations, and merge the duplicated entities. These techniques will be monitoring the evolution of entities and their attributes and/or corresponding values and will take the necessary actions either automatically or after interacting with the curator of the OKKAM repository.
Ideally, we would like to be able to identify duplicates at the time when new entities are inserted in the system, using on-line algorithms. This assumes that (a) summaries exist to store the necessary information from existing entities, and (b) a proper threshold is used to guide the decision of whether the entities can be merged or not. We envision the use of techniques used in clustering to build attribute and attribute value summaries, and use them to decide whether a new or existing entity can be merged with one or more entities in the repository. 4.6
An important issue that we have not discussed so far is the access control (AC) model. This is probably the most important aspect to take into account regarding the security of the OKKAM infrastructure from the users’ point of view. The huge amount and the heterogeneity of the information stored require very scalable and flexible access control mechanisms in order to adequately protect each individual piece of information. Additionally, the information stored in OKKAM repositories must respect different (and sometimes very strong) privacy requirements. Furthermore, the information to be protected is not only the one returned in the queries to the repositories, but also the information that can be derived (for instance, by means of data mining techniques) from the data stored.
Solving this situation requires the ability to define restrictions on the data that can be used for searching, and data that can be returned as a query result. For the access control scheme to be able to suit the needs of OKKAM we have identified the following subrequirements: Flexibility; scalability; manageability; and provision of advanced features such as controlled delegation, owner-retained control, dynamic self-adaptability (i.e. content-based and context-aware access), anonymous access and provisional authorization. All these characteristics pose important challenges in the protection and access control mechanisms.
Furthermore, we believe that the importance of automation and ease of management must not be underestimated: due to the large-scale and distributed nature of OKKAM it is essential that security management is highly automated and does not require a lot of administration, as otherwise the system would rapidly become vulnerable due to the human limitations of the administrators and the high complexity of the system. In fact, this aspect, which is usually overlooked when designing a security infrastructure, is the most important source of vulnerabilities and attacks.
In what follows, we briefly outline the directions that we will pursue in order to address the issues related to entity lifecycle management we identified in the previous section.
In OKKAM, we represent an entity E as a tuple <P, M>. We call the set P the profile of the entity, because it stores the unique identifier of the entity, and contains information that specifies the (semantic) type of an entity, as well as the relationship of the entity with other entities in OKKAM (if we know that it is identical to another entity stored in the system), or outside OKKAM (if there exists another id assigned to the entity by another system). The entity profile is also composed of a set of arbitrary, used-defined attributes that describe the entity. For example, if the entity is a person, possible attributes are name, date of birth, and nationality. Note that this set of attributes can be different for every entity, even for entities in the same domain.
The set M refers to the metadata of the entity. These metadata are used to support complex algorithms for the other functionalities offered by OKKAM, such as entity matching that based on the attributes in P identifies if two entities are the same or not. Examples of the information that these metadata may carry are the creation time and usage patterns of the entity, and of each individual attribute in P. The information in M can also be used to store some simple information regarding the version history of the entity. Nevertheless, specialized data structures are needed in order to keep track of the history of changes in P.
The way the users access the system and interact with it may determine several aspects of the entity lifecycle management. Consider the following example. Assume that many users search for an entity with attributes A1 and A2, and always select entity E1, which is the only entity in the repository that contains attribute A1 in its profile. If E1 does not contain A2 as well, we may choose to add it to the profile of E1, because many users refer to E1 using A2.
Alternatively, assume that the query for entities with attributes A1 and A2 returns n entities, E1, E2, … , En, that satisfy the search conditions, but the interested users always select entity Ek, 1 ≤ k ≤ n. In this case, we may choose to increase the importance of entity Ek, so that it ranks first for the particular query.
In both the above situations, we are interested in monitoring the usage patterns of the
system, in order to obtain some knowledge that can help the system perform better. By
monitoring and analyzing the way users interact with OKKAM, we can determine which
entities, or profile attributes, are relevant to specific queries or to certain contexts. This
information can subsequently be used for updating the profile or the metadata of the
entities, and ultimately for producing more relevant search results. The above kind of
processing can be done automatically, in an online fashion, and be flexible enough to
allow effective and efficient data analysis [
The results of the usage patterns monitoring techniques that we discussed in the previous paragraphs are also relevant to the repository evolution process. One of the important aspects of this process is the entity merging operation, which takes place when we discover that two entities in the repository represent the same real-world entity.
As we already mentioned, when merging entities, it is important to consider the type of
values at hand, i.e., numerical vs. categorical with their corresponding measures. When
the merging of the entities takes place off-line, we plan to employ standard techniques
from clustering in order to group similar entities together. Although time may not be an
issue in this case, we seek to perform the merging in an as efficient fashion as possible.
Adopting techniques like BIRCH [
The greatest advantage of employing techniques as the ones mentioned above is that we
get to summarize the input data set, i.e. the OKKAM entities, in summaries that retain as
much of the initial information as possible. We plan to extend the construction of
summaries so that a) they can handle both numerical and categorical data at the same
time, and b) can be used effectively with streaming data. The big challenge in this case is
the maintenance of the summaries in that we will employ policies, either automatic or
user-driven with the use of which we can “forget” summaries [
In current access control models, the complexity of management grows exponentially with the size and complexity of the contents. This is due to (i) the existence of different related artifacts such as roles, groups, which capture semantics in a “hidden” way; (ii) the possibility of creating conflicting policies, which in turn introduces the need for conflict resolution strategies; (iii) the direct relation between the location where contents are stored and the policies; (iv) the lack of dynamism and context-awareness in the AC model; and (v) the lack of policy validation tools. In this situation, when the size, dynamism and heterogeneity of the content set increases, it becomes impossible for administrators to understand the result of the policies they define, which inevitably leads to errors.
The OKKAM security model, and in particular the access control model, is based on the use of semantic modeling of the contents, policies and users. Semantic modeling brings important advances to access control because it facilitates the creation of easy to understand policies that can be automatically assigned to contents. Additionally, it facilitates interoperability of users’ credentials and the development of mechanisms providing advanced access control features such as controlled delegation and user-retained control.
Among the traditional access control models, Role-Based Access Control (RBAC) is the most popular and has received much attention from researchers, but despite such effort, there are situations that are not well-handled by this model. In RBAC, a role must be defined for each different set of access criteria required by the group of resources controlled. This means that when the number of resources and the heterogeneity of access conditions are very high, the administration of RBAC systems becomes very complex.
A more general approach is needed for these new environments, and in particular for
OKKAM repositories. The Semantic Access Control (SAC) model [
The web is quickly moving towards the direction of adding semantics to the online information, and using these semantics for enabling a vastly richer range of applications and user-experiences. A major step, necessary for achieving this goal, is to have a way for uniquely identifying entities in the emerging semantic web.
In this paper, we argue for an entity naming and management system, and we discuss the various problems that arise when considering the entity lifecycle management in this context. We examine the special requirements of representing entities, creating new and modifying existing entities, detecting duplicates, merging and versioning entities, and finally controlling the access to entities. Evidently, all the above functionalities are interrelated and affect each other. This work identifies these relationships, and presents the directions we are currently pursuing for realizing the functionalities outlined above.