Affiliations: Consiglio Nazionale delle Ricerche, Istituto della
Scienza e delle Tecnologie della Informazione, Via Giuseppe Moruzzi, 1 - 56124
Pisa, Italy. E-mail: carlo.meghini@isti.cnr.it | Department of Computer Science, University of Crete
Heraklion, Greece | Université Paris-Sud, Laboratoire de
Recherche en Informatique Orsay, France
Abstract: We consider a general form of information sources, consisting of a
set of objects classified by terms arranged in a taxonomy. The query-based
access to the information stored in sources of this kind, is plagued with
uncertainty, due, among other things, to the possible linguisticmismatch
between the user and the object classification. To overcome this uncertainty in
all situations in which the user is not finding the desired information and is
not willing or able to state a new query, the study proposes to extend the
classification, in a way that is as reasonable as possible with respect to the
original one. By equating reasonableness with logical implication, the sought
extension turns out to be an explanation of the classification, captured by
abduction. The problem of query evaluation on information sources extended in
this way is studied and a polynomial time algorithm is provided for the general
case, in which no hypothesis is made on the structure of the taxonomy. The
algorithm is successively specialized on a most common kind of information
sources, namely sources whose taxonomy can be represented as a directed acyclic
graph. It is shown that query evaluation on extended sources is easier for this
kind of sources. Finally, two applications of the method are presented, which
capture very important aspects of information access: information browsing and
query result ranking.
Keywords: Logic-based abduction, information systems, algorithms
