Expressiveness and complexity analysis of information extraction languages

Expressiveness and complexity analysis of information extraction languages

000

Ciencias de la computación

Metadatos.

Administración de bases de datos.

Tesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2017

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.

Maturana Sanguineti, Francisco José

2018-01-30T15:12:58Z

2018-01-30T15:12:58Z

2017

Riveros Jaeger, Cristian

Pontificia Universidad Católica de Chile. Escuela de Ingeniería

acceso abierto

ix, 94 hojas

application/pdf

es

tesis de maestría

10.7764/tesisUC/ING/21495

https://doi.org/10.7764/tesisUC/ING/21495

https://repositorio.uc.cl/handle/11534/21495