Preservación de consultas expresables en fragmentos existenciales en bases de datos relacionales

Abstract

En el contexto de bases de datos, el concepto de preservacióon de teorí as en una cierta l ógica y entre dos estructuras relacionales A y B dadas, signi fica que el conjunto de consultas Booleanas que son expresables en dicha l ógica y que son verdaderas en la base de datos A tambi én son verdaderas en la base de datos B. As , por ejemplo ante el agregado de nuevos elementos a una base de datos es posible determinar si el conjunto de consultas Booleanas expresables en FOk(9) (y en la extensi ón in nitaria Lk 1;!(9)) se preserva. Existen juegos de fichas que caracterizan la preservacióon de teorí as para estas dos l ógicas, y es sabido que dicha preservaci ón puede determinarse en tiempo polinomial. En el presente trabajo mostramos una caracterización alternativa de la preservación de teorí as en FOk(9) (y en la extensi ón infi nitaria Lk 1;!(9)) mediante la realización de tipos de k-tuplas. Luego presentamos un algoritmo polinomial que permite determinar dicha preservación y en el que utilizamos nuestra ara teorización.