Estrategias de Optimización de Consultas XPath Flexibles sobre XML Wavelet Trees

Nieves Brisaboa, Ana Cerdeira, Gonzalo Navarro, and Gabriella Pasi

El almacenamiento autoindexado y comprimido de documentos es un área de investigación muy activa y prometedora debido a que las estructuras de datos que usan permiten no sólo ahorrar espacio de almacenamiento en bases de datos documentales y bibliotecas digitales, sino que además proporcionan ahorros significativos de tiempo de procesamiento. En [2] se presentó una nueva estructura de datos denominada XML Wavelet Tree (XWT), un auto-índice comprimido para documentos XML creado mediante la adaptación de un auto-índice para textos planos [3] basado en el uso de wavelet trees. Además, se mostraba cómo el XWT podía ser usado para responder eficientemente consultas típicas XPath sobre estructura y contenido de los documentos XML. En este trabajo mostramos cómo el XWT puede usarse también para resolver consultas flexibles [5,8,9]. Estas consultas constituyen una extensión de XPath que trata de introducir cierta flexibilidad en las búsquedas, adecuándolas más al ámbito de la recuperación de información; ya que permiten no sólo combinar restricciones sobre estructura y contenido, sino también puntuar y hacer ránking de las respuestas, es decir, de los distintos documentos y/o fragmentos de documentos recuperados. Por último, presentamos diversas estrategias heurísticas de optimización del plan de resolución de las consultas y las evaluamos experimentalmente.