Titulación DCC

Los Qdags son estructuras muy compactas que permiten hacer joins en bases de datos de grafos en forma worst-case-optimal, ver https://users.dcc.uchile.cl/~gnavarro/ps/tods22.pdf. Recientemente, se produjeron dos mejoras importantes sobre el tiempo que toman para realizar consultas: 1) Representar su estructura en orden DFS en vez de BFS (ver https://users.dcc.uchile.cl/~gnavarro/ps/spire25.1.pdf) Y 2) Utilizar "pre-joins" para bajar su dimensionalidad en la parte más costosa de la operación (ver https://users.dcc.uchile.cl/~gnavarro/ps/grades26.pdf).

El objetivo de esta memoria es tratar de obtener lo mejor de los dos mundos, realizando los pre-joins sobre la representación DFS. Esto podría mejorar aún más los tiempos del pre-joining, y requiere, en particular, programar el algoritmo de join y de proyección sobre la representación DFS. Puede llevar a una publicación si los resultados son buenos.

Para doble titulación, se podría agregar el extender estos resultados a implementar un álgebra de matrices. El algoritmo de join que se programa en la primera parte sirve para multiplicar matrices (como ya se indica en el paper de grades26), y esto se podría extender a sumas y clausuras transitivas para implementar regular path queries (ver https://users.dcc.uchile.cl/~gnavarro/ps/vldbj24.pdf).