Expressiveness and complexity analysis of information extraction languages

Abstract

Los lenguajes de Extracción de Información (EI) en base a reglas han recibido atención de parte de la comunidad de bases de datos últimamente, con varios lenguajes nuevos apareciendo en los últimos años. A pesar de que los sistemas de EI suelen procesar datos semi-estructurados, todos los lenguajes que se han propuesto hasta ahora están diseñados para producir relaciones y, por lo tanto, son incapaces de trabajar con información incompleta. Además, existe poco conocimiento acerca de cómo estas propuestas se comparan en términos de poder expresivo y complejidad. Para remediar esto, esta tesis estudia la expresividad y complejidad de distintos lenguajes de EI a través de un marco teórico unificador con soporte para información incompleta.Con este fin, se propone un lenguaje que generaliza otras propuestas anteriores y que utiliza funciones parciales (también llamadas mappings) en lugar de relaciones. Luego utilizamos este lenguaje general para comparar distintos métodos de EI definidos en el pasado y estudiar sus propiedades computacionales, tales como: enumeración de consultas, satisfacibilidad y equivalencia. Como se muestra, ninguno de los métodos propuestos domina a los otros, sin embargo, combinando ciertas características de distintos enfoques se puede obtener un lenguaje para EI que es expresivo, puede implementarse eficientemente y puede ser utilizado en la práctica.