jjordanoc/file-organization-dbms

Para este proyecto, se nos ha pedido crear y manipular un DataSet usando estrategias de organización de archivos.

• Conocer el funciomaniento de la manipulación de metadata en una base de datos usando estrategias de organización de archivos.

• Identificar las ventajas y desventajas de cada estrategia utilizada.
• Analizar el comportamiento computacional al implementar una base de datos.
• Comprender como funciona la interacción usuario-servidor mediante la implementación de una GUI.

Las estrategias usadas para este proyecto son las siguientes:

• ISAM-Sparse Index
• Extendible Hashing
• AVL

Para cada estretegia, se debe implementar y visualizar las siguientes funciones:

• vector search(T key)
• vector rangeSearch(T begin-key, T end-key)
• bool add(Registro registro)
• bool remove(T key)

Además, se pide implementó un parser y un GUI en QT para una mejor visualización del proyecto.

Hemos usado un dataset de Películas IMBD. Esta elección fue debida a los siguientes factores:

• Los atributos son fáciles de tratar: la mayoría son de tipo string o int.
• Los datos son requeridos obligatoriamente para todos los atributos menos uno: el "certificate". Esto hace que nuestro potencial de valores NULL disminuya considerablemente.
• El DataSet está compuesto de la mezcla de dos DataSets (uno de peliculas y uno de series), combinándolos en más 100'000 registros listos para organizar en un sistema de ficheros, lo que lo convierte en un buen candidato para indexar dada la cantidad de registros.
• El DataSet solo consta de una tabla, por lo que facilita su manejo y manipulación para los índices a utilizar.

A continuación, explicamos los atributos del DataSet previamente mencionado.

struct MovieRecord {
    int dataId{};
    char contentType[16]{'\0'};
    char title[256]{'\0'};
    short length{};
    short releaseYear{};
    short endYear{};
    int votes{};
    float rating{};
    int gross{};
    char certificate[16]{'\0'};
    char description[512]{'\0'};

En la implementación se logra visualizar un cuadro de texto en donde acepta e interprete algunas sentencias del lenguaje pgSQL. Esto se pudo cumplir gracias a una técnica llamada Top-Down: Recursive-Descent. Es un método básico para poder cumplir un parseo, este es apoyado mediante una gramática en donde las reglas determinan el proceso de la generación de la sentencia original.

Para empezar, se realiza una lectura de palabra por palabra de la instrucción introducida y mediante una serie de condicionales cual serían las reglas de la gramática se logra determinar si la cadena introducida es aceptada. Si la cadena no es aceptada, se emite un mensaje que no ha sido aceptada y se puede volver a introducir otra instrucción. Una vez la cadena es válida, se procede a obtener todos los valores necesarios de la instrucción para poder ejecutar la consulta respectiva. En este caso, nos apoyamos de un struct definido que guarda valores de la sentencia introducida.

A continuación se mostrará las consultas que soporta nuestro parser.

Como se puede observar, el parseo tiene algunas limitaciones, puesto que solo recibe a la tabla movies, mientras solo puede leer algunas columnas ya definidas. En el caso de los tipos de índices se puede tolerar ese ajuste.

Hemos realizado algunas consultas que demuestran la eficiencia de los índice para buscar registros.

SELECT * FROM movies WHERE endYear = 2014;

SELECT * FROM movies WHERE title = "Star Wars";

SELECT * FROM movies WHERE releaseYear BETWEEN 1800 AND 1900;

• El método Top-Down: Recursive-Descent para realizar el parseo es fácil de entender y sencillo de implementar. Sin embargo, por su simplicidad genera una limitación en la generación de sentencias. En este caso se acude a buscar otros métodos de parseo para poder realizar un análisis léxico y sintáctico más genérico.

• Se utilizaron índices para optimizar consultas sobre un dataset por encima de los 100000 registros, mostrando su superioridad para gestionar búsquedas sobre muchos registros.

• Se comparó el indice Hash respecto al AVL para búsquedas por igualdad y se obtuvo que, en casos promedio, el Hash realizaba sus operaciones de búsqueda en un tiempo mucho menor que el AVL; sin embargo, se encontraron casos específicos donde el AVL podia llegar a concretar sus operaciones en un tiempo similar al Hash (casos donde la llave a buscar esta cerca a la raíz).

• El tiempo de creación del indice AVL resultó ser muy superior al de creación del índice Hash. Esto es potencialmente debido a la cantidad de rotaciones necesarias durante la inserción de todos los nodos del AVL.

• El AVL resultó de utilidad para realizar busquedas por rango y reportes ordendados, operación la cual no es soportada por el Hash; estas consultas resultaron ser ejemplos claros en las que puede preferirse una estructura que prevalezca cierto orden entre las llaves respecto a un Hash, en el cual se pierde el orden de los atributos por lo que se indexa.

Joaquín Jordán	Juan Diego Castro	José Chachi	Juan Diego Laredo
.com/jjordanoc	.com/ByJuanDiego	.com/JoseChachi	.com/DarkNeSsJuaN25

• [1] K. C. Louden, "Compiler Construction: Principles and Practice". Available: http://grsotudeh.ir/compiler/compiler_ebooks/compiler-construction-principles-and-practice-k-c-louden-pws-1997-cmp-2002-592s.pdf .[Accessed: Apr 26, 2023]

• [2] Elmasri, R. & Navathe, S. (2010). Indexing Structures for Files. In Fundamentals of Database Systems (pp. 643-646). Addison–Wesley.