Final del 14/12/15 (Bases de Datos)

De Cuba-Wiki
Final

Respuestas a algunas preguntas optativas


1) Como es una logica de modelos finitos, no vale compacidad, entonces muchos resultados de primer orden se caen. En particular https://en.wikipedia.org/wiki/Trakhtenbrot's_theorem te dice que Finite-SAT (SAT para modelos finitos) no es decidible para lógicas de primer orden. Y phi es universalmente valida <=> not phi no es sat, por lo que no puede ser decidible.

2) Es una forma que describe (en ingles se usa la nocion de witness, la discrimina del resto) a la respuesta de la query. First order query es una cuya formula asociada es expresable en logica de primer orden.

3) Hay varias, como que un grafo es conexo, que el numero de elementos del modelo es par, etc. Se basan en logicas extendidas.