IIC3432 - Tópicos Avanzados en Bases de Datos
Algunos temas para proyectos

• Proyecto I (teórico y práctico): La mayor parte de los parsers para DTDs permiten expresiones regulares arbitrarias. Por el contrario, la W3C recomienda sólo utilizar expresiones regulares deterministas porque existen algoritmos muy eficientes que pueden verificar si una palabra pertenece al lenguaje de una de estas expresiones.
  
  En ninguno de estos casos se considera cuáles son las expresiones regulares que los usuarios utilizan en la práctica. Una pregunta que aún está abierta es identificar una clase de expresiones regulares que sea muy utilizada en la práctica, que sea lo suficientemente expresiva como para ser utilizada en muchas especificaciones y que pueda ser manipulada eficientemente. La idea de este proyecto es contribuir en resolver este problema.
  
  Algunos proyectos posibles:
  
  • Construir una herramienta computacional que sea capaz de encontrar DTDs en la Web.
  • Construir un repositorio de DTDs (puede ser manualmente).
  • Definir una clase de expresiones regulares que sean usadas frecuentemente en DTDs en la práctica y que puedan ser manipuladas eficientemente. En particular, el problema de determinar si una palabra w está en el lenguaje de una expresión r en esta clase debe poder resolverse eficientemente. La clase de expresiones regulares puede ser una subclase de las expresiones deterministas.
  • Definir una clase de expresiones regulares que contenga a la clase de expresiones deterministas, que tenga una sintaxis fácil de definir y que pueda ser manipulada eficientemente, es decir, es posible determinar eficientemente si una palabra w está en el lenguaje de una expresión r en esta clase.
  
  Material relevante:
  
  • Byron Choi: What are real DTDs like? WebDB 2002: 43-48.
  • Geert Jan Bex, Frank Neven, Jan Van den Bussche: DTDs versus XML Schema: A Practical Study. WebDB 2004: 79-84.
  • Denilson Barbosa, Laurent Mignet, Pierangelo Veltri: Studying the XML Web: Gathering Statistics from an XML Sample. World Wide Web 8(4): 413-438 (2005).



• Proyecto II (teórico y práctico): Al igual que en el caso de las bases de datos relacionales, en XML existen muchas maneras distintas de representar el mismo dominio de interés. Como un ejemplo, basta pensar de cuantas maneras distintas se puede almacenar la información de una biblioteca en XML.
  
  En el caso de las bases de datos relacionales, las distintas formas de representar un mismo dominio difieren en las relaciones y atributos usados. En el caso de XML, las distintas alternativas no sólo difieren en las etiquetas y atributos usados, sino que también pueden diferenciarse en el grado de estructuración que poseen; algunas de estas alternativas pueden ser muy estructuradas mientras que otras pueden ser poco estructuradas.
  
  A pesar de la importancia que tiene el grado de estructuración al momento de decidir entre distintas formas de representar un mismo dominio de interés, se sabe muy poco de como medir este grado. La idea de este proyecto es contribuir en resolver este problema.
  
  Algunos proyectos posibles:
  
  • Definir una medida de estructuración. Esta medida debería tener como entrada un DTD (o algún otro lenguaje para definir el esquema de una base de datos XML) y debería indicar que tan estructurados son los documentos que satisfacen este DTD.
  • Definir un conjunto de propiedades que una buena medida de estructuración debería satisfacer. Por ejemplo, una propiedad básica de una buena medida de estructuración debería ser que un DTD que representa directamente a una base de datos relacional debería ser muy estructurado.
  • Construir un repositorio de DTDs (puede ser manualmente) que puedan ser utilizados como casos de estudios para posibles medidas de estructuración. Este repositorio debe contener tanto DTDs muy estructurados como DTDs con muy poca estructura que usted debe clasificar.



• Proyecto III (práctico): Ha sido descrita como una de las ventajas de XML el hecho de que la información puede ser almacenada de una forma semiestructurada, lo cual permite mayor flexibilidad al usuario. Sin embargo, esta flexibilidad también puede traer problemas si es usada sin entender sus ventajas reales, como podemos ver hoy en muchas bases de datos XML que podrían haber sido modeladas directamente como bases de datos relacionales. La idea de este proyecto es contribuir en identificar posibles áreas de aplicación para XML.
  
  Algunos proyectos posibles:
  
  • Encontrar una aplicación donde XML es claramente superior a la alternativa relacional. Justificar claramente porque XML es la mejor alternativa en este caso.



• Proyecto IV (teórico y práctico): En clases vimos dos posibles alternativas a los DTDs: DTDs especializados que tienen mayor poder expresivo y DTDs no ambiguos que tienen menor poder expresivo pero que pueden ser implementados eficientemente.
  
  La combinación de los DTDs especializados y los no ambiguos parece tener un gran atractivo por la combinación entre poder expresivo y eficiencia. Un DTD D es especializado y no ambiguo si D es un DTD especializado donde cada expresión regular es determinista. La idea de este proyecto es que usted estudie esta clase de DTDs.
  
  Algunos proyectos posibles:
  
  • Determine la complejidad de verificar si una documento XML satisface a un DTD especializado y no ambiguo. ¿Es posible resolver este problema eficientemente?
  • Determine si los DTDs especializados y no ambiguos son al menos tan expresivos como los DTDs. ¿Es cierto que cualquier DTD (que puede contener expresiones regulares no deterministas) es equivalente a un DTD especializado y no ambiguo?



• Proyecto V (teórico): En clases vimos que la combinación entre DTDs, claves y claves foráneas puede generar especificaciones inconsistentes, vale decir, es posible que por separados un DTD D y un conjunto R de claves y claves foráneas sean consistentes, pero que (D,R) sea inconsistente.
  
  Se llama análisis estático de consistencia al problema de determinar si un DTD D junto con un conjunto de claves y claves foráneas R son consistentes, vale decir, determinar si existe un documento XML que satisface tanto a D como a R. La idea de este proyecto es que usted estudie la complejidad de este problema.
  
  Algunos proyectos posibles:
  
  • Una clave se dice unaria si menciona un sólo atributo, y una clave foránea se dice unaria si en cada lado menciona un sólo atributo. Por ejemplo, todos los ejemplos de claves y claves foráneas mostrados en las transparencias del curso son unarias.
    Determine si el siguiente problema es decidible: Dado un DTD D no recursivo y un conjunto R de claves y claves foráneas unarias y relativas, verificar si (D,R) es consistente.
  • Encuentre una clase C de claves y claves foráneas para las cuales el problema de consistencia (incluyendo DTDs) sea decidible. De un algoritmo que permita resolver el problema.
  • Encuentre una clase C de claves y claves foráneas para las cuales el problema de consistencia (incluyendo DTDs) pueda ser resuelto eficientemente. Indique cuál es el algoritmo que permite resolver el problema.
  
  
  
• Proyecto VI (teórico y práctico): También puede ser un aporte al área de bases de datos XML el mostrar cuál es el estado estado del arte de alguna sub-área e identificar problemas a resolver. La idea de este proyecto es que usted haga este ejercicio, vale decir, que escoja alguna sub-área de bases de datos XML que le parezca interesante, haga un resumen breve sobre lo que se sabe en esta área e identifique problemas a los cuales los investigadores deberían prestar atención.
  
  Algunos sub-áreas interesantes:
  
  • Implementación de bases de datos XML usando tecnología relacional.
  • Diseño de bases de datos XML.
  • Implementación eficiente de lenguajes de consulta XML.
  • Optimización de consultas.