2 Related work

Although there is much work dealing with the combination of diverse lexical resources for particular tasks, much less work has been done concerning the integration of lexical resources in a general way.

Just to mention a few works, Jing and McKeown (Reference Jing and McKeown1998) describe a work to build a large-scale lexicon for different natural language generation applications, by combining multiple heterogeneous resources primarily designed for other purposes (WordNet, EVCA, COMLEX, and the Brown Corpus). Kwong proposes to integrate WordNet and the Roget's Thesaurus in order to improve word sense disambiguation tasks (Kwong, Reference Kwong2001). More recently, Shi and Mihalcea (Reference Shi and Mihalcea2005) aim to integrate FrameNet, VerbNet, and WordNet into a unified knowledge base to the end of enabling robust semantic parsing.

However, these works differ substantially from the work presented here, mainly because of two reasons. First, they integrate a fixed number of well-known sources, and usually they do not consider the scalability of the integration process. Thus, adding a new resource can often lead to a complete re-implementation of the integration procedure. Second, their aim is to create new lexical resources, which, once built, remain completely unrelated to the original ones. Therefore, changes in the original sources will not be reflected in the new one.

Several projects such as GENELEX (Normier and Nossim Reference Normier and Nossim1990), MULTILEX (MacNaught Reference MacNaught1990), PAROLE/SIMPLE (Ruimy, Corazzari, Elisabetta, Spanu, Calzolari and Zampolli Reference Ruimy, Corazzari, Elisabetta, Spanu, Calzolari and Zampolli1998; Bel, Busa, Calzolari, Gola, Lenci, Monachini, Ogonowski, Peters, Peters, Ruimy, Villegas and Zampolli Reference Bel, Busa, Calzolari, Gola, Lenci, Monachini, Ogonowski, Peters, Peters, Ruimy, Villegas and Zampolli2000), or EAGLES/ISLE (Uszkoreit, Backofen, Calder, Capstick, Dini, Dörre, Erbach, Estival, Manandhar, Mineur and Oepen Reference Uszkoreit, Backofen, Calder, Capstick, Dini, Dörre, Erbach, Estival, Manandhar, Mineur and Oepen1996; Calzolari, Zampolli and Lenci Reference Calzolari, Zampolli and Lenci2002) have provided computational techniques for filtering out the knowledge given in existing lexicons and transferring it into a uniform representation with the aim of producing standardized lexicons that can be reused in new applications. They also propose uniform formalisms for storing the data independently of languages, applications, or even linguistic theories. The standardization initiatives have made great efforts trying to identify common structures of lexical entries shared by the majority of existing resources. Moreover, some of them have proposed common and normalized values for representing linguistic phenomena such as part-of-speech (POS) or subcategory values.

We have borrowed much of the work done by these initiatives, and they have been very useful in providing guidelines to define our general conceptual model (see Section 5.1). Apart from this, PAROLE normalized values are used in ELHISA to map POS and subcategory values across the sources (see Section 7).

However, our approximation to lexical integration is fundamentally different from theirs. Indeed, the aim of these initiatives is to be flexible enough to cover any linguistic application, still providing efficient ways to represent and access the information. Therefore, they must cope with the problem of representing very diverse lexical information at different levels of granularity, and store the information efficiently. ELHISA is designed primarily to be a consultation system, and its main goal is to provide the users with a uniform access point to the lexical data. Thus, its requirements are weaker than those of the standardization initiatives. For example, in ELHISA there is no need to represent lexical information at every granularity level. Furthermore, information too tied to a concrete resource or to a particular linguistic theory can be discarded from our system. Anyhow, ELHISA can bee seen as a complementary system that puts the standards initiatives in use, as it is based on them to a great extent.

On the other side, the works in Patrick, Zhang and Artola (Reference Patrick, Zhang and Artola1999), Zajac (Reference Zajac1999), and Cunningham, Bontcheva, Peters and Wilks (Reference Cunningham, Bontcheva, Peters and Wilks2000) can be effectively seen as an effort towards the integration of different lexical resources.

In Patrick et al. (Reference Patrick, Zhang and Artola1999), we can see an approach to an architecture for a federation of heterogeneous dictionary databases, much like in the work presented here. They describe the problem of integration of lexical information, and propose a Generalized Dictionary Query Language as a ‘lingua franca’ to access the sources. However, their work is concerned mainly with dictionaries, and the problem of integrating other lexical resources (as lexical databases or knowledge bases) is not under consideration.

In Zajac (Reference Zajac1999), integration techniques are used to model different lexical resources at the CLR.Footnote ¹ He offers a framework where the information of these resources is organized in a structured way, following the recommendations of the EAGLES initiative (Uszkoreit et al., Reference Uszkoreit, Backofen, Calder, Capstick, Dini, Dörre, Erbach, Estival, Manandhar, Mineur and Oepen1996). The author proposes a layered architecture of structures, each encapsulating the lexical information at a concrete level of abstraction.

The main goal of Cunningham et al. (Reference Cunningham, Bontcheva, Peters and Wilks2000) is to develop a framework that offers the user uniform access to lexical information. With this goal, the authors propose to create a common object-oriented model for language data resources that encapsulates the union of linguistic information contained in a broad range of them. At the top of the resource hierarchies, there are very general abstractions, while at the leaves there are data items specific to each resource. The authors offer programmatic access at each level, so that the user is allowed to select an appropriate level of commonality for each application.

The main difference between these works and ours relies on the fact that they focus primarily on this programmatic access to lexical information, much like Application Programming Interfaces in traditional programming. ELHISA, on the other hand, offers the users a data-centric approach to a federation of lexical resources, and does not demand from them any further knowledge apart from being able to query a database system. Apart from this, in ELHISA the rules for integrating the different resources are described in a declarative way (by means of the so-called content description rules, see Section 5.3), thus making explicit how the resources are integrated.

Our work relies on several systems that have been developed in the data integration field. For instance, the TSIMMIS project (Garcia-Molina, Papakonstantinou, Quass, Rajaraman, Sagiv, Ullman, Vassalos and Widom Reference Garcia-Molina, Papakonstantinou, Quass, Rajaraman, Sagiv, Ullman, Vassalos and Widom1997), OBSERVER (Mena, Kashyap, Seth and Illarramendi Reference Mena, Kashyap, Seth and Illarramendi2000), SIMS (Arens, Hsu and Knoblock Reference Arens, Hsu and Knoblock1996), or the Information Manifold (Levy, Reference Levy1998) are examples of different systems that address the problem of data integration, taking the approach of gathering different information sources in a virtual repository, providing uniform access to them.

These projects have in common the use of logic formalisms to describe the domain model and the contents of the information sources. However, they differ mainly in the way they map between domain (global) relations and the source (local) relations that represent the contents of the information sources. In the local as view (LAV) approach, illustrated by Information Manifold or SIMS, the local relations are defined as views over the global relations. In the global as view approach, illustrated by TSIMMIS or OBSERVER, the mapping is done from the global relations to the local relations: the local relations are considered as new base predicates in terms of which global relations can be expressed. Besides, these systems can also be classified depending on whether they use a unique domain model or ontologyFootnote ² (SIMS, Information Manifold), multiple ontologies (OBSERVER), or no ontology at all (TSIMMS).

ELHISA uses a logic formalism to describe the information, and follows the LAV approach for defining the mappings among classes and relations. It relies on a unique and common domain model (the GCM) as a ‘meeting point’ between the sources. The main difference between ELHISA and the systems presented above is that while these systems are not tied to any particular domain—theoretically they can integrate information of any domain—our system is concerned only with lexical data. In fact, the characteristics of these data have guided heavily the design and architecture of the system.

Finally, there is much work done in the area of data warehousing (Jarke, Lenzerini, Vassiliou and Vassiliadis, Reference Jarke, Lenzerini, Vassiliou and Vassiliadis2003) where big central repositories are built out of heterogeneous information coming from diverse sources. Its main goal is to be able to provide fast response times to online analytic processing applications, thus providing new ways to access and analyze the information. These techniques differ from the integration approach presented here in the sense that they are aimed at supporting fast mining techniques over the data, which is not our main concern. Besides, data warehousing requires the duplication of the data, and great care must be taken to keep this information up to date wrt the sources.

3 Overview and main characteristics of the system

As stated before, ELHISA is an integration system for lexical resources. Its main purpose is to serve as a knowledge base for different users—human users and NLP applications mainly—providing a variety of lexical information coming from several heterogeneous lexical resources.

We propose to leave each resource on its own, so that it must not be modified in order to be integrated into ELHISA. Instead of converting the information of the different lexical resources into a uniform representation, we propose to integrate the sources into a so-called ‘federation of highly heterogeneous lexical sources’. The term federation is used here in a broad sense, and must not be confused with the federation term used in database technology. Instead, ELHISA is a global information system (Ives and Jarvenpaa, Reference Ives and Jarvenpaa1991), where each specific resource is mapped to a common model. In federated databases, on the contrary, mappings are defined for each database to every other one. So, in the case of n databases, there will be n ² mappings in a database federation, but only n in a global information system (Seth and Larson, Reference Seth and Larson1990).

For this purpose, a GCM for describing diverse lexical data has been conceived. The GCM establishes a fixed vocabulary describing objects in the lexical information domain, their attributes, and the relationships among them. Thus, it provides the user with a global view of the information the system contains, stating it by means of a taxonomy of interrelated classes in an object-oriented fashion. The user, then, poses the queries in terms of the GCM classes and relations, stating what kind of information is needed, rather than where to obtain such information. Hence, the queries do not need to contain information describing which sources are relevant to a particular query or where they are located. It is the task of ELHISA to determine how to transparently retrieve and integrate the data necessary to answer a query. Therefore, we can say that the integration in ELHISA is done at the query time.

The sources are autonomous and highly heterogeneous in the sense that they use very different data models and vocabularies. You could find among them from relational databases up to object-oriented knowledge bases, ontologies such as WordNet, or XML-encoded documents such as TEI-conformant machine-readable dictionaries. They are also heterogeneous from the point of view of the data they contain, because we are considering here lexical databases, electronic dictionaries, lexica used in NLP tasks, or even language-processing programs such as lemmatizers or POS taggers.

To integrate the lexical resources into the federation, an SCM is built on top of each one, representing the lexical objects concurring in each particular source. The concepts and relations identified in the SCMs are then related to the corresponding concepts and relations in the GCM using mapping rules (CDRs).

To answer the queries, ELHISA must access the integrated resources, and hence it must translate the query expressed in GCM terms into queries in terms of the SCM of each source. The Query Translator module accomplishes this task and guarantees that the rewritings of the query are sound and complete. Informally speaking, this means that the rewritings should give the same answers as if all the data were stored in a single huge database. The output of this module is then passed to the planner, which creates a plan, sends the queries to be executed at the local sources, and receives and combines the answers.

The main characteristics of the system are the following:

• • Heterogeneous data: The information stored in the different lexical sources will be highly heterogeneous, despite the fact that all will be of lexical nature, that is, related with words and word senses. The heterogeneity of the data can be classified at different levels:

  • Representation level: Each resource uses different representation systems to store the lexical data in electronic format. From plain texts to complex lexical knowledge bases, the lexical data are stored in many formats.

  • Query level: Very related to the representation level, each resource will have its particular language to query the information it stores. Note that these languages can have different query capabilities.

  • Semantic level: The information in each resource will be stored according to some kind of schema,Footnote ³ and these schemas will not match each other.

  The first two levels can be grouped into the so-called structural heterogeneity. We cope with this problem with the aid of wrapper technology (Roth and Schwartz, Reference Roth and Schwartz1997), and so we must attach a wrapper to each resource. Wrappers are software modules that act like bridges between the sources and ELHISA. The wrappers receive a query expressed in the internal language the system uses, but described in terms of the local resource schema, and transform it to the particular query language of the resource. They also collect the answers and bring them back to the system. Therefore, the use of wrappers allows us to make an abstraction and view the lexical sources as sets of concepts and relations among them.

  Regarding the semantic level of heterogeneity, semantic mappings between the sources and the GCM must be defined by means of the so-called CDR as explained in Section 5.3.

• • Multilingual data: The information stored in the resources may refer to different languages. If we want ELHISA to provide the users with uniform access to multiple lexica, it must deal with multilingual data. Therefore, there must be mechanisms for representing multilingual relationships between concepts of different languages.

• • Distributed system: A global information system is, by definition, a distributed system, as the sources are located in physically different places across the world. Nowadays, there exists a wide range of technologies for connecting physically distant sources such as CORBA, SOAP, etc.

• • Autonomy of the sources: The sources integrated into the federation proposed here are autonomous. Indeed, the ‘integrator’ of each resource will decide the level of integration of the source into ELHISA. Moreover, she or he can add/delete/modify the data in the sources, and the system will adopt these changes automatically.

  Regarding the traditional meaning of autonomy at its different levels, such as those identified in Seth and Larson (Reference Seth and Larson1990) and Heimbigner and McLeod (Reference Heimbigner and McLeod1985), the resources will be almost fully autonomous. First, each source ‘decides’ which information to export to ELHISA, by means of an export schema defined by the designer of the source. Second, when posing queries to the local sources, these decide how and when to answer them. Finally, the design of the sources may change. In this case, however, a complementary work must be done in order to give ELHISA the chance of adopting the changes: if the design changes are at the query language level, but not in the schema, we must only redesign the wrapper attached to the source; however, if the changes are deeper, that is at the schema level, the integration steps for the source must be redone.

• • Scalable: ELHISA permits the integration of new lexical resources at any time. Moreover, the inclusion of new resources should have a minimum impact over the system, and, specifically, it must not invalidate the integration status of already incorporated resources.

• • Read-only: ELHISA is primarily defined as a consultation system for accessing structured lexical information, and therefore it does not have the capability to modify or update the underlying information. This is the approach taken by nearly all the usual data integration systems, as the modification of information would bring an extra level of complexity to the system (concurrent access, inconsistencies, etc).

4 Architecture of the system

In Figure 1, we can see the general architecture of ELHISA. At the bottom of the picture, we can see the lexical resources. Attached to every one there is a wrapper, which allows its integration into ELHISA.

Fig. 1.

Architecture of the system.

Let us summarily explain the information flow shown in Figure 1. When a user—either a human user or an NLP application—needs some information, several steps are performed.

The user poses a query to ELHISA with the aid of the Interface module, in terms of the concepts and relations of the GCM. The Interface module hands the query to the Query Translator, which translates it into rewritings expressed in terms of the SCMs of the particular resources relevant to that query. Then, the Optimizer receives the rewriting set from the Query Translator and tries to remove the redundant rewritings. A rewriting in a set will be redundant if the data it asks for are already contained by the other rewritings in the set.

The Optimizer sends the optimized rewritings to the Plan Generator in order to create plans for retrieving the information requested in them. After this, the Plan Generator sends the plans to the Query Sender, whose goal is to deliver each plan to a particular source. The wrapper attached to each resource executes the local queries, and returns the answers to the system. These answers are collected by the Answer Receiver in an asynchronous way, so that, when answers arrive, it sends them back to the Plan Generator.

Then, partial answers are sent to the Data Cleanser, which performs the data cleaning. When the complete set of answers arrives, the Plan Generator activates the Data Cleanser again, in order to perform the object identification step.

Finally, the Interface module shows to the user the unified answer received from the Plan Generator.

5 The conceptual level

The conceptual model provides a conceptual representation of the lexical data managed by ELHISA. It includes a conceptual representation of the GCM, the conceptual models of the sources, and the semantic mappings among them.

The information is expressed independently from any system considerations, capturing the semantics of the data. Therefore, it has to be provided in terms of representation mechanisms that allow us to abstract from the physical and logical structure of data in the sources. Moreover, the conceptual representation will make possible automatic reasoning processes to be carried out on it, as, for example, in the query rewriting stage. In this way, the system is able to derive and verify different properties concerning the conceptual specification of information.

The use of description logics to express domain knowledge is widely explored in the literature (Levy, Rajaraman and Ordille Reference Levy, Rajaraman and Ordille1996; Calvanese, De Giacomo and Lenzerini Reference Calvanese, De Giacomo and Lenzerini1999a; Mena et al. Reference Mena, Kashyap, Seth and Illarramendi2000). It is the formalism we have chosen to describe the different conceptual models, which have been implemented using the Neoclassic Description Logic Language (Brachman, Borgida, McGuiness, Patel-Schneider and Resnick Reference Brachman, Borgida, McGuinness, Patel-Schneider and Resnick1992). This language is used to model domain knowledge and it belongs to the family of KL-ONE knowledge representation languages. Thus, Neoclassic gives us most of the representation power available in semantic networks. Although its expressive power is somewhat limited, it guarantees that certain basic operations (like testing if certain individual subsumes another one) are satisfiable in a reasonable time.

The conceptual level is classified into three main parts:

• • The General Conceptual Model

• • The Source Conceptual Models

• • The Content Description Rules

5 General Conceptual Model

The whole integration process ELHISA performs lies on the design of a GCM for describing lexical information. The GCM provides a consolidated view of the concepts and relationships that are relevant to the lexical domain.Footnote ⁴

The goal of the GCM is twofold. First, it guarantees the communication between ELHISA and the user, as the queries will be posed in terms of the GCM classes and relations. Second, the GCM acts as a conceptual model for describing general lexical information, thus behaving as an integration schema. As we will see later, the different sources are mapped on to the GCM via semantic mappings.

As we want the GCM to be general, it must be necessarily simple. But, at the same time, it must gather all the features and relationships that a lexical information source can contain about the entities it describes. Therefore, the GCM has two requirements that are somewhat contradictory: it must be able to gather as much information as possible from the local resources, but, on the other hand, its design cannot be too tied to any of them in order to keep it general enough. Besides, ELHISA users must find easy and intuitive ways to pose their queries in terms of the GCM classes and relations.

To achieve these requirements, we have followed a two-way strategy for designing the GCM. First, we have identified the most representative classes and relations from several existing lexical resources. We have also borrowed much of the work and conclusions of different standard initiatives such as EAGLES/ISLE (Uszkoreit et al., Reference Uszkoreit, Backofen, Calder, Capstick, Dini, Dörre, Erbach, Estival, Manandhar, Mineur and Oepen1996; Calzolari et al., Reference Calzolari, Zampolli and Lenci2002) or PAROLE/SIMPLE (Ruimy et al., Reference Ruimy, Corazzari, Elisabetta, Spanu, Calzolari and Zampolli1998; Bel et al., Reference Bel, Busa, Calzolari, Gola, Lenci, Monachini, Ogonowski, Peters, Peters, Ruimy, Villegas and Zampolli2000), which have coped with similar problems as ours. Second, we have identified the most typical queries posed to these lexical resources, trying to ensure that the queries can be easily represented in the GCM.

In our model, the GCM is described by means of a taxonomy of classes and by a set of binary relationships established among the different objects or classes in the taxonomy.Footnote ⁵ There is a main class called LexicalObjects, which has three subclasses: Words, Concepts, and Features (see upper side of Figure 2).

Fig. 2.

A partial class diagram of the General Conceptual Model.

The Concepts class models the ‘lexical concept’ as described in the literature (Normier and Nossim Reference Normier and Nossim1990; Calzolari et al., Reference Calzolari, Zampolli and Lenci2002), and therefore it is the core of the GCM, where all the features are specified. It has a unique descendant, the Senses class, which represents classic dictionary senses (upper-left side of Figure 2).

The Words class and its subclasses model the variety of word forms that can be found in lexical resources, from pure ‘word forms’ to inflected forms, multiwords, etc. It also covers non-standard words, and relates them with the correct, standard formFootnote ⁶ (Figure 2).

Finally, the Features class and its subclasses represent diverse lexical features a lexical item may have attached. Features are classified into four main subhierarchies, representing phonologic, morphosyntactic, syntactic, and semantic features (Figure 3).

Fig. 3.

General Conceptual Model Lexical features.

As for the relationships, a wide set of relations that link different classes in the hierarchy has been established and defined. Figure 4 shows a partial view of those relations, specifying the domain, range, and maximum cardinality. We can refer here only to the maximum cardinality of each relation because, in the GCM, the relationships (and so the classes) are virtual in the sense that they do not actually store any information at all (the GCM is an abstract model).

Fig. 4.

General Conceptual Model. Some relationships between classes. N.B. Cardinality figures denote only the maximum value for each relation.

5.2 Source Conceptual Models

The integrated sources are modeled in a similar way, expressing each source class and the relationships among classes in the so-called SCM.

The underlying structure and physical organization of the information sources are expected to be very diverse but, due the ‘wrapper’ technology we have adopted, we can make an abstraction, and conceive and model an information source as a collection of objects belonging to some source relations. So, like in the GCM, every source model is described by means of a taxonomy of classes and by a set of binary relationships established among them.

As stated before, some information represented in the sources will not be integrated into ELHISA. Information that is very dependent to a resource, or that is represented at a very fine level of granularity, would be very difficult to relate to a GCM that must be considered general. Thus, we consider these kind of information as not being part of the federation.Footnote ⁷ This approach is very common in the database federation literature, where each local resource defines its own ‘export schema’, describing precisely which information should be shared with the other sources of the federation (Seth and Larson, Reference Seth and Larson1990) and which not. Therefore, the SCMs can be seen as the export schemas of the local resources.

Figure 5 shows the class hierarchy defined for modeling the Euskal Hiztegia resource (EH; Sarasola, Reference Sarasola1996), a complex Basque monolingual dictionary, which contains information about words, word senses, related words, definitions, examples, etc. In Figure 6, the relations among the EH classes are depicted. Note that now we can also give the minimum cardinality for any source relation because they represent real relations, as opposite to the GCM where the relationships (and classes) are virtual.

Fig. 5.

Source Conceptual Model of the EH dictionary.

Fig. 6.

Relationships between lexical objects in the EH's SCM.

5.3 Content Description Rules

To achieve the integration of the sources into ELHISA, there must be an explicit relation between the GCM and the SCMs of the sources. In ELHISA, this relation is described by means of mapping rules called CDRs.

The CDRs allow us to address the semantic heterogeneity between the sources, caused by the different conceptualizations they follow in order to describe the underlying data. Among others, we must face the following conflicts:

• • Name conflicts arise because different schemata may refer to the same data using different terminologies. The sources typically model the information by means of concepts, attributes, and relations, usually referenced with different names. Sources refer to possibly the same concept with different names, and so name conflicts among them might.

• • Domain conflicts. In different sources, two concepts with the same name may belong to different domains. For instance, a source that stores information about verbs may have a concept named Words that represent verb forms. Some other lexical resource may also have a concept with the same name that represents not only verb forms but also word forms of any category. So the same name is used to represent concepts of different domains.

• • Type conflicts. The same concept may be represented in the sources in different ways, due to different choices in the level of abstraction when modeling real-world entities. For example, one source may express a particular concept by means of an entity, while other one may do it by means of relationships.

To integrate a resource into ELHISA, a rule must be attached to every relation (and class) of its SCM. The rule expresses a logical query over the GCM, describing the conditions the tuples in the local relation (and class) must satisfy.Footnote ⁸ Thus, the queries in ELHISA follow the well-known LAV paradigm (Ullman, Reference Ullman, Afrati and Kolaitis1997; Florescu, Levy and Mendelzon Reference Florescu, Levy and Mendelzon1998) in the data integration literature.Footnote ⁹ This approach gives us two main advantages:

• • The GCM does not change when a new resource is integrated into the system. This property allows us to offer the users a unique domain and vocabulary to pose the queries. It also leaves the way open to dynamically add new databases to the system.

• • We can make fine-grained distinctions between the relations and concepts of the sources, giving to the system the possibility of integrating very diverse lexical resources.

The syntax rules vary slightly depending whether they are referred to local concepts or local relations. For defining local concepts, the rules have the following syntax:

• 

where:

• • V _c is a local concept, that is, an element of an SCM.

• • The p _i are concepts or relations of the GCM and the X_i are their arguments.

On the other hand, for each local relation the rules have the following syntax:

• 

where

• • V _r is a local relation, again an element of an SCM.

• • The p _i are as above.

• • α is the adornment of the rule. The adornment describes the domain of the local concept according to the SCM of the source.

In Figure 7, we can see a couple of CDRs for the EH monolingual dictionary. Classes are expressed as logical predicates with arity 1, and relationships are described by predicates with arity 2 (binary relations). So, the first rule of the example must be read as follows: if an individual a is a Concepts instance in the GCM, it will also be an EH_Senses instance in the SCM of EH. The second rule states that if s is a Concepts individual, l is a DictionaryEntries individual, and both instances are related via the sense relation in the GCM, then s and l will be related via the EH_writtenForm relation in the SCM of EH. It also states by means of the adornment that the individual s is an instance of EH_Senses in the SCM of EH.

Fig. 7.

Some Content Description Rules for the EH dictionary.

Note that the source does not need to contain all the objects that satisfy the query, as the query only gives the necessary (but not sufficient) condition for the individuals. This led us to adopt the so-called open-domain assumption (Abiteboul and Duschka, Reference Abiteboul and Duschka1998), that is, we left the way open for other objects besides those described by the sources to exist. In fact, in the field of lexical information, the existence of a source that contains information about a certain concept does not obviously guarantee that all the lexical information about that concept is present in it. There can always be alternative sources that give us additional information on the concept.

6 Query rewriting

As said before, the GCM terms the user queries are expressed in are virtual, that is, they have no extension. To collect the information necessary to answer the query, ELHISA must go where the actual data reside, that is, access the local sources. Therefore, two processes must be accomplished. First, the sources relevant for answering the query must be identified. Second, the query must be translated into a set of semantically equivalent queries, called rewritings, expressed only in terms of the SCMs of the selected sources.

The semantic mappings between the GCM and the SCMs of the sources are expressed following the LAV approach. Under LAV the query rewriting step is recognized as being a hard task, which involves inference techniques over the queries. This problem is known to be closely related to the so-called ‘answering queries using views’ problem (Yang and Larson, Reference Yang and Larson1987; Levy, Mendelzon, Sagiv and Srivastava 1995; Beery, Levy and Rousset Reference Beery, Levy and Rousset1997; Abiteboul and Duschka, Reference Abiteboul and Duschka1998; Calvanese et al., Reference Calvanese, De Giacomo and Lenzerini1999a) that can be stated as follows: given a query Q formulated in terms of the database schema, and a set of view definitions V ₁,. . ., V _n over the same schema, answer the query Q using only the answers to the views V ₁,. . ., V _n. In our case, the view definitions are just the content descriptions of every relation (or class) in the local sources.

In general, the problem of answering queries using views problems is NP-Complete wrt the size of source descriptions (CDR) because it involves searching a possibly exponential number of rewritings. However, answering queries can be polynomial wrt the number of the data in the sources provided that the queries describing the sources and the user queries are conjunctive (Levy et al., Reference Levy, Mendelzon, Sagiv and Srivastava1995). Therefore, there are several efficient algorithms that face the problem of answering queries using views in the context of data integration (Levy et al., Reference Levy, Rajaraman and Ordille1996; Duschka and Genesereth, Reference Duschka and Genesereth1997; Mitra, Reference Mitra1999; Pottinger and Levy, Reference Pottinger and Levy2000). We have borrowed the MiniCon algorithm (Pottinger and Levy, Reference Pottinger and Levy2000), an improvement of the famous Bucket algorithm originally developed as part of the Information Manifold system (Levy et al., Reference Levy, Rajaraman and Ordille1996; Levy, Reference Levy1998). The MiniCon algorithm finds the relevant sources for a given query Q and reformulates them exclusively in terms of those source models in polynomial time. Minicon also guarantees that these rewritings are the maximally contained rewritings, that is, that they provide all the possible answers for a given set of sources.

The query rewriting step in ELHISA is addressed as follows (see Figure 8): the Query Translator module receives the original query described as a conjunctive query over the GCM. Then, it passes it to the Query Preprocessor, which applies a few minor optimizations to the query, such as removing redundant information or replacing some general concepts with more specific ones. As a result, a simplified query is obtained. This simplification step is crucial for obtaining accurate rewritings.

Fig. 8.

The Query Translator.

The simplified query is then passed to the MiniCon module, which actually performs the query rewriting. It produces a set of positive queries,Footnote ¹⁰ which are the translations of the original query referred to the SCM of the relevant sources.

We have augmented the capabilities of the MiniCon algorithm, mostly for adapting it to deal with our data model. The design of the algorithm is primarily intended to work with flat relations, following the Entity Relationship model, and therefore some extra work had to be done for exploiting the rich hierarchical model we use for describing the resources. For instance, at the first stage of the algorithm, and for every predicate in the body of the query, MiniCon tries to unify the predicate with some predicate in the body of the CDRs.Footnote ¹¹ If this succeeds, it means that the head of the CDR (a local class or relation) is relevant for answering the query, and so it is retained for further processing. In its original formulation, two predicates will unify whenever they are not disjoint in the database schema. We restrict this condition, and let the two predicates unify if and only if the predicate of the query subsumes the predicate in the CDR, according to the GCM. Informally, this optimization guarantees that, if the user asks for Words, answers related also with Variants or DictionaryEntries will be returned, as both of them are descendants of the class Words in the GCM. On the contrary, if the query requests DictionaryEntries, no information about its parents or disjoint siblings such as Variants will be returned.

Furthermore, the MiniCon algorithm assumes that the semantic mappings are always accurate, but unfortunately this is not always the case. Indeed, at the modeling stage, there will be local classes and relations that do not fit well in the GCM. As an example, the class EH_Date in the EH's SCM, which represents the estimate date of the first appearance of the entry headword in Basque literature, does not have an exact equivalent in the GCM. In fact, an instance of the EH_Date class will be an instance of the more general class Usages of the GCM, whose type attribute will be ‘date’.

As a consequence, some of the rewritings produced by the MiniCon algorithm turn to be inconsistent with the SCM of a particular source. The last module of the Query Translator, called the Verifier, deals with inconsistent rewritings. It receives a set of rewritings, each one referring to a unique SCM, as produced by the MiniCon module. Then it verifies that the rewritings are consistent wrt the SCM of the sources involved, and discards those that are inconsistent. For this task, it uses the inference engine of the NeoClassic description logic system. As a result, a set of valid rewritings is produced.

For instance, let us suppose that the MiniCon algorithm produces the following rewriting:

The rewriting is not consistent wrt the EH's SCM. It states that d is an instance of the EH_Dates class, that a is an instance of the EH_Senses class, and that both instances are related by the EH_usg relation. However, the SCM of EH states that the range of the EH_usg relation is the EH_Usages class. So, d turns to be an instance of the EH_Dates and the EH_Usages classes, but these classes are disjoint in the SCM. So, the whole rewriting is inconsistent wrt the SCM of EH, and so it must be discarded.

6 An example

Let us suppose that a user asks for the non-standard word forms (variants) of a given word ‘arrazoi’ (Basque for reason), as well as their sense identifiers. She or he would pose the following query:

• 

The Query Translator will find two relevant resources to answer this question: the EH dictionary and EDBL, a Basque lexical database. It then performs the query rewriting, translating the original query into a set of semantically equivalent rewritings referred only to the SCMs of EH and EDBL. Among others, it will produce the rewritings shown in Table 1. It can be seen that each of these rewritings will effectively query the corresponding lexical source for non-standard word forms of the word ‘arrazoi’.

Table 1.

Rewritings for the EH and EDBL resources

The Query Translator passes these rewritings to the Planner, which is responsible for making each one of them reach the appropriate resource, or, more precisely, the wrapper each resource has attached to. The wrappers then translate syntactically the rewritings into the particular query language the local source supports. Table 2 shows the final queries that will be posed to EH and EDBL. The EDBL data lie in a relational database, so the queries must be made in SQL. EH is stored as a collection of XML files, so it accepts queries expressed in XQuery.

Table 2.

Queries sent to EH and EDBL by their wrappers

The queries are then executed in the local sources, and the answers are sent back to ELHISA. However, a last integration step must be done at an instance level, in order to recognize commonalities among these data. This task is performed by the Data Cleanser, and is explained in the next section.

7 Data cleansing

The data cleansing process addresses the integration at an extensional level, needed if we want to compare the data arriving from different sources, so that the answers from each source are not isolated with respect to the others (Monge, Reference Monge1997; Galhardas, Florescu, Shasha and Simon Reference Galhardas, Florescu, Shasha and Simon2001; Rahm and Do, Reference Rahm and Do2000; Tejada, Knoblock and Minton Reference Tejada, Knoblock and Minton2001). For instance, some information in the sources (such as parts-of-speech) should be comparable across them, as they are expected to store similar data, although using different formalisms and values. Therefore, some attributes are mapped on to a uniform representation, and hence can be combined across the sources. Furthermore, the cleanser should be able to determine if two n-tuples arrived from different sources refer to the same world object, so that the information related to these tuples can be compared.

Data cleansing is further complicated by the fact that many data in the sources may be wrong or contain inconsistencies, that is, the data may be dirty. Dirtiness of data occurs when there are spelling errors in some attribute values, when some attributes represent more than one element, etc. This kind of errors occurs mainly in semi-structured resources, such as human-oriented dictionaries or online resources on the Internet.

Table 3 shows some answers received from the EH dictionary for a particular query. Some data are dirty in this example. For instance, the value at the third column of the first row, ‘Iparr eta Naf’Footnote ¹² has actually two different values, joined with a conjunction ‘eta’.Footnote ¹³ Furthermore, the elements in the second column are supposed to have the same values, as they refer to the POS of the entry. However, some values mismatch, as ‘ize’ and ‘iz’, both refer to the ‘Izena’Footnote ¹⁴ lexical category.

Table 3.

‘Dirty’ data arriving from the EH dictionary

For cleaning these data, ELHISA adopts the abstract domains approach (Calvanese, Giacomo, Lenzerini, Nardi and Rosati Reference Calvanese, Giacomo, Lenzerini, Nardi and Rosati1999b), attaching to each class of the SCMs some cleaning rules, which actually perform the data cleaning as soon as the data arrive to ELHISA. The rules are implemented as NeoClassic rules and cover three types of cleaning:

1. 1. Decomposing rules. They try to verify if some attribute values are composed, and, if so, decompose them into basic elements.

2. 2. Correction rules. They look for wrong values in the attributes (for instance, spelling errors) and try to correct them.

3. 3. Normalization rules. Certain attributes are normalized and their values are replaced with standard ones. Some examples of these attributes are the lexical category or subcategory; we have adopted the values proposed by the PAROLE project (Ruimy et al., Reference Ruimy, Corazzari, Elisabetta, Spanu, Calzolari and Zampolli1998) for this standardization.

As stated before, the rules are implemented in the framework of the NeoClassic description logic. The rules are defined in a declarative way, clearly expressing the initial and final states of the operation, via pre- and postconditions. For instance, the following rule will accomplish the normalization process of the EH_Pos class:

It states that whenever an EH_Pos instance is added to the NeoClassic KB, the rule will fire over the posVal attribute and will execute the mapUDF user-defined function whose work is to normalize the attribute according to the EHPosHash hash mapping.

In Table 4, we can see the data after the cleaning process. The rule-type column indicates which kind of rules has been fired for this particular n-tuple. Note that elements of the second column are now normalized to PAROLE standards, and multiple-valued attributes have been decomposed into single values.

Table 4.

‘Clean’ answer from the EH dictionary

Once the data for each resource are cleaned, ELHISA addresses the problem of object identification, that is, it tries to determine if tuples of different resources refer to the same real-world entity.

Continuing with the example of Section 6.1, the (cleaned) data arriving from the sources can be seen in Table 5. We can see that EH finds five variants for the word ‘arrazoi’, while EDBL finds three. Note that some information is overlapped, as the variant form ‘arrazoin’ comes from the two sources.

Table 5.

Answers from EH and EDBL

For dealing with the object identification process, the data are first stored in a local database, which implements in a relational fashion the classes and relations of the GCM. Table 6 shows these answers, stored in the local database.Footnote ¹⁵ As can be seen, much of the information is duplicated, and the user has no way to compare the answers of the two sources.

Table 6.

Answers before the object identification step

The Data Cleanser module performs the object identification step, and for that purpose adopts an approach much like in Monge (Reference Monge1997). Furthermore, in our system, we must explicitly declare which attributes are relevant for identifying a tuple in the database and which are not. For instance, the sCod attribute of the Senses class cannot be used for comparing two records, as it is a unique key attached by the system to each record in the database. So, much like in the data cleaning process, each class of the GCM has attached a rule describing which attributes are meaningful for this particular class.

Table 7 shows the final results of the query after the object identification process has been performed. We can see that all the repeated information has been removed, and as a consequence the number of n-tuples decreases significantly. Furthermore, the data arrived from the two sources are combined, giving to the user the possibility to relate this information in a uniform way.

Table 7.

Answers after the object identification step

8 Evaluation

In this section, we present an evaluation of the rewriting engine of ELHISA. The evaluation is performed by posing several prototypical queries against the system and measuring the number and correctness of the proposed rewritings, as well as the time elapsed in producing them. The queries are the following:

• Q ₁ Give the non-standard forms of a given standard one.

• Q ₂ Give the lexical category (POS) of a given word form.

• Q ₃ Give the definition of a given word form.

• Q ₄ Give the word forms of a given category.

• Q ₅ Give the senses/concepts corresponding to a given word form.

• Q ₆ Give the hypernyms of the senses/concepts corresponding to a given word form.

• Q ₇ Give the hypernyms and definitions of the senses/concepts corresponding to a given word form.

• Q ₈ Give the translations of a given word form.

These queries can be considered prototypical since they represent requests that NLP applications frequently make from their lexicons. Also, when you see in the formulation of the examples above that the hypernyms of a concept are asked, you can obviously replace ‘hypernym’ by any other lexical-semantic relationship to build a similar query. Query Q ₁ is a typical and useful request in a spelling checking and correction application, where it is used for a knowledge-based generation of candidates for correction, but it shows up useful too in lemmatization, when non-standard uses of words must be recognized and lemmatized according to a standard or canonical form. Query Q ₂ is the most typical lexical request in any NLP application. The third, and maybe the fourth query, find its place obviously in electronical dictionaries, that is, in any human-oriented dictionary applications. Asking for the senses of a given word form (Q ₅) is needed whenever word-sense disambiguation must be performed, and it is well known that this disambiguation constitutes nowadays a prominent intermediate task in NLP, required by many applications. Queries Q ₆ and Q ₇ are requests of lexically related words, useful in information retrieval and question answering. Q ₇ is in fact the composition of two simpler queries, showing the feasibility of these kind of constructs in ELHISA. This way, complex queries can be easily posed to the system. Finally, Q ₈ takes us to an automatic or computer-assisted translation context.

Table 8 summarizes the number of valid rewritings and the time the program took to produce them for seven queries. The rows of the table represent the different queries, and the columns the lexical resources integrated into ELHISA so far.Footnote ¹⁶ The first number in the cells tells us the number of rewritings generated for this query in this resource. This number is sometimes 0, indicating that this particular source cannot answer the original query. In some cases, the algorithm produces a big number of redundant rewritings, in the sense that the information they ask for is already contained in another, more general set of rewritings. The Optimizer should consider all the rewritings for a particular source and discard the redundant ones.

Table 8.

Different queries and elapsed times (in seconds)

The second number indicates the time spent in generating the rewritings.Footnote ¹⁷ As we can see, the algorithm performs very well in almost all the cases, giving overall a short time in producing the rewritings.