Módulo 1. Datos PDF

Introducción Información importante para el cursado En el módulo 1, conoceremos diferentes medios de almacenamiento, y detallaremos uno de los medios que más se usa: el disco rígido. Luego, veremos el concepto de archivo, y los diferentes tipos existentes, para más tarde conocer las operaciones y fo...

Introducción Información importante para el cursado En el módulo 1, conoceremos diferentes medios de almacenamiento, y detallaremos uno de los medios que más se usa: el disco rígido. Luego, veremos el concepto de archivo, y los diferentes tipos existentes, para más tarde conocer las operaciones y formas en las que se puede organizar un archivo. Ahondaremos en los archivos secuenciales y hash. Sobre estos últimos, veremos el encadenamiento y direccionamiento. El objetivo de esta materia es que diseñes y pongas en funcionamiento una base de datos. Para ello, el recorrido de la materia estará contextualizado en un proyecto. Te proponemos que imagines que formas parte de este proyecto, el cual está desarrollado por la empresa File Data. En esta empresa, tu rol es muy importante, por lo que el contenido de la materia y las actividades están relacionadas con esta situación. Por esta razón, es importante que observés detenidamente cada uno de los videos dispuestos al principio de cada lectura. Asimismo, prestá atención al contenido y los videos que se encuentran dentro de cada lectura, ya que estos te darán una guía para avanzar en la materia y cumplir con los objetivos propuestos. Además, en cada módulo, retomaremos este caso práctico a través de ejercicios relacionados que te permitirán poner en práctica lo aprendido. Base de Datos 1 Bienvenidos a la empresa File Data: caso práctico Proyecto En "File Data" nos diferenciamos del resto de las empresas del rubro, por la calidad de nuestros servicios y las soluciones personalizadas que ofrecemos a nuestros clientes. Mi trabajo, como líder, es asegurar el profesionalismo de cada uno de los integrantes de mi equipo para realizar los proyectos que nos encargan. Es por eso, que antes de comenzar a trabajar en el desarrollo de la biblioteca de la Universidad General Pulsar, quiero asegurarme que contás con los conocimientos necesarios para llevarlo a cabo. A continuación, vas a encontrar, en primer lugar, los documentos de la empresa donde detallamos algunos conceptos teóricos que debés conocer. Y luego, los requerimientos de software que debés instalar para poder trabajar. Una vez que tengas todo listo, y apruebes la autoevaluación, sé que estás listo para formar parte de mi equipo. iA trabajar! Video de inmersión Base de Datos 2 Unidad 1. Almacenamiento y archivos Antes de comenzar, y para poder comprender mucho mejor los contenidos, veamos un video en el que se explica cómo hacer la instalación de base de datos. Instalación de una base de datos Tema 1. Tipos de almacenamiento Las bases de datos, independientemente del modelo de datos que se haya usado para su diseño, se almacenan físicamente como archivos de registros; normalmente, se almacenan en discos rígidos. A lo largo del desarrollo de este apartado, hablaremos de las técnicas que permiten acceder a los datos en su espacio de almacenamiento de la manera más eficiente y eficaz posible. Además, presentaremos la organización de la base de datos en su espacio de almacenamiento. La colección de datos, que constituye una base de datos, debe guardarse en algún medio de almacenamiento. De esta manera, el sistema gestor de bases de datos (SGBD) debe ser capaz de recuperar, actualizar y procesar los datos, siempre que sea necesario. Los medios de almacenamiento forman una jerarquía llamada jerarquía de almacenamiento o jerarquía de memoria, la cual contiene dos categorías principales: Almacenamiento primario. Incluye la memoria principal y la memoria caché. Son medios de almacenamiento muy rápidos, aunque con capacidad limitada. Almacenamiento secundario: incluye discos magnéticos, discos ópticos, cintas, etc. Son medios de almacenamiento de grandes capacidades, aunque con un acceso mucho más lento. Si bien el nivel de almacenamiento primario se caracteriza por ser más caro y rápido que el secundario, podemos decir que, dentro de cada uno de estos niveles, hay subniveles; también, agregamos a estos criterios los conceptos de coste y velocidad. Así, en el nivel de almacenamiento primario, destacamos los siguientes subniveles: Memoria caché. Es la capa más cara de la jerarquía, y se trata de una memoria RAM estática que usa la CPU para aumentar la velocidad de ejecución de las máquinas. Es volátil. Memoria DRAM (RAM dinámica) o memoria principal: la usa la CPU para mantener los programas y los datos. Es más lenta que la RAM estática, aunque más barata. Es volátil. Memoria flash: memoria no volátil que se sitúa en el último subnivel dentro del Base de Datos 3 nivel primario. Por otra parte, en el nivel de almacenamiento secundario, tenemos los siguientes elementos: Discos de estado sólido (SSD). Discos rígidos: son los que más se usan en este nivel por su relación velocidad/precio. Discos que se basan en tecnología óptica con lectura/escritura láser: compact disks (CD), digital versatile disks (DVD), blu-ray disks. Las cintas: se encuentran en el nivel más barato. En cualquier caso, tanto el nivel de almacenamiento primario como el secundario se usan para las bases de datos. La memoria principal, siempre que tenga capacidad suficiente, se puede usar para albergar datos (o parte de ellos), manteniendo siempre una copia de respaldo en memoria secundaria para evitar los problemas que podrían ocasionar la volatilidad de la primera. No obstante, en la gran mayoría de las ocasiones, el tamaño de la base de datos impide su almacenamiento en una memoria primaria, y se mantiene en almacenamiento secundario utilizando la memoria primaria para cargar índices que aumentan la velocidad de acceso a los datos. Dentro de la jerarquía del almacenamiento secundario, el principal soporte hasta el momento es el disco rígido; asimismo, los discos de estado sólido son protagonistas en la actualidad. En este curso, nos centraremos en ver el funcionamiento de los discos rígidos, el principal medio en las bases de datos. Tema 2. Archivos, tipos de archivos y operaciones básicas Estructura de un archivo y tipos Un archivo, en base de datos, es una secuencia de registros. Estos registros pueden ser de longitud fija o variable. Cada registro es una colección de campos que se asocian de manera independiente con un puntero. Por lo general, un registro está asociado a una entidad, es decir, posee una serie de campos con valores relacionados entre sí. Los archivos pueden clasificarse según la forma en la que se manejen los conceptos mencionados anteriormente. Figura 1: Organización de archivos según el tipo de registro Base de Datos 4 Fuente: elaboración propia. Organización de un archivo Según el tipo de registro Según el ordenamiento de los registros Extendida: los espacios libres en cada bloque se ocupan o se aprovechan. Para hacerlo, se almacena parte del registro en un bloque, y lo restante en otro. El enlace de ambos bloques se realiza a través de un puntero al final del bloque. De este modo, se indica cuál es el bloque en el que continuará el registro. Se usa cuando el registro es mayor que el bloque. No extendido: los espacios libres no se utilizan. Deriva en un procesamiento de datos más simple, pero el espacio del disco no se utiliza de manera óptima. Archivos desordenados: en este tipo de archivos, no existe un ordenamiento; los registros se insertan al final del archivo en la medida que se ingresan. Archivos ordenados o secuenciales: hay un orden al momento de la inserción de los registros. Se ordenan físicamente con algún campo clave. Por ejemplo, en el archivo de artículos, se ordena por nombre de artículo. Operaciones básicas Las operaciones básicas que podemos hacer con los archivos son las que se describen a continuación: Insertar. Esta operación permite poblar la base de datos. Las inserciones pueden ser individuales o masivas, según se ingresen uno o muchos registros al archivo. Por ejemplo, una inserción individual podría ocurrir en un sistema de facturación cuando damos de alta a un cliente. La inserción masiva puede suceder cuando se importan, masivamente, todos los artículos, mediante la importación de un archivo externo como un libro de Excel. Extraer: se busca un determinado dato/campo para ser presentado. Esta búsqueda se puede realizar con alguna condición para delimitar el universo de archivos que se deban recorrer. Este tipo de operación no modifica los datos de los archivos, ni los de la base de datos. Suele ser llamada operación de lectura. Una funcionalidad de este tipo de operaciones es traer o leer todos los artículos de un determinado rubro, por ejemplo, listar todos los artículos del rubro electrónico. Actualizar: se busca un determinado dato o universo de datos, con el fin de Base de Datos 5 realizar una modificación sobre un campo o varios campos. Al igual que la inserción, esto se puede hacer de forma masiva, si queremos incrementar en un 5 % el precio de todos los artículos del rubro de electrónica o, de forma individual, si queremos incrementar el precio de un solo artículo. Eliminar: es la operación inversa a la inserción de datos. Cuenta con la dinámica de poder procesar de forma masiva o de manera individual. Es importante tener presente, en este tipo de operación -principalmente cuando se hace de manera masiva-, que la recuperación puede no ser posible. Deberemos estar muy seguros al momento de hacer la eliminación. Actividad de repaso ¿Es el disco rígido el medio de almacenamiento más barato? o Verdadero o Falso Justificación Tema 3. Archivos secuenciales y ordenados Los archivos secuenciales se caracterizan por tener un orden físico según los valores de uno de sus campos: el campo de ordenación. Si tiene, además, propiedades de identificador, es decir, si siempre tiene valor y no se repite, se conoce como clave de ordenación del archivo. Estos tipos de archivos poseen ciertas ventajas: a) La lectura de registros en el orden físico almacenado es extraordinariamente eficiente. b) Los accesos a registros son en orden consecutivo y no se requiere cambiar de bloque en la mayoría de los casos, por lo que se optimiza el acceso al disco. c) Las condiciones de búsqueda que afectan a valores de un campo clave de ordenación son muy eficientes cuando se emplea una estrategia de búsqueda binaria. Una búsqueda binaria accede, normalmente, a log2(n) bloques, encuentre o no el registro que busca entren bloques. Base de Datos 6 Figura 2: Archivo secuencial y ordenado Fuente: elaboración propia. Base de Datos 7 Aun así, existen algunas desventajas. Analicemos cada una de las operaciones sobre archivos. La inserción es una operación costosa, ya que se debe conservar el orden físico de los registros: a) encontrar la posición para el nuevo registro en el fichero, según el campo de ordenación; b) abrir espacio en el bloque correspondiente, desplazando el resto de los registros. Esta última fase de la operación es especialmente dura, debido a que implica tener que leer y volver a escribir una media de n/2 bloques para un fichero de n bloques. La búsqueda por un campo de ordenación -ya sabemos- es extremadamente eficiente; sin embargo, la búsqueda por cualquier otro tipo de campo se convierte en una tarea de búsqueda lineal. El borrado implica primero buscar el registro, eliminarlo y mover los registros posteriores. Esto es una operación costosa. La única ventaja que existe es cuando hay búsqueda del registro a borrar por el campo de ordenación. La actualización implica la búsqueda del registro, que solo es eficiente cuando la restricción contiene el campo de ordenación. Si lo que se ha modificado es el valor del campo de ordenación, entonces, se convierte en una operación de borrado más inserción del registro en su nueva ubicación, con la complejidad que ello conlleva. La lectura secuencial del fichero ordenado es muy eficiente, siempre que se siga el campo de ordenación. En cualquier otro caso, es una búsqueda lineal. Tema 4. Archivos hash. Función hash. Resolución de conflictos Los archivos de direccionamiento calculado, también conocidos como dispersos o hashing, proporcionan un acceso muy rápido a los registros, bajo ciertas condiciones de búsqueda. La condición de búsqueda se realiza sobre un único campo del registro, que se conoce como campo de direccionamiento calculado o clave hash. El funcionamiento de este tipo organización se basa en establecer una función hash que, una vez aplicada sobre el valor del campo de direccionamiento de un registro, produciría la dirección del bloque de disco en el que se almacena el registro buscado. Una vez que se obtiene el bloque, se copia a memoria principal, y se realiza la búsqueda del registro dentro del bloque. Base de Datos 8 Figura 3: Almacenamiento disperso en disco Fuente: elaboración propia. Tabla hash Una tabla hash es una estructura de datos, que se conoce, además, como tabla fragmentada. Esta estructura se basa en una operación en la que se asocian claves con valores. Esto permite lograr accesos muy rápidos al momento de buscar la información que se precisa, por ejemplo, la búsqueda de un artículo por su nombre a partir de una clave generada. Lo que se hace con esta estructura de tablas es transformar una clave a través de una función, función de = IDI (M mayor o igual al tamaño del diccionario) y que sea primo, no cercano a potencia de 2 o de 10. Siendo K la clave a buscar y h(K) la función hash, se tiene h(K) = K %M (resto de la división k/m). 2. Hash de multiplicación: si, por alguna razón, se necesita una tabla hash con tantos elementos o punteros como una potencia de 2 o de 1O, será mejor usar una función hash de multiplicación, independientemente del tamaño de la tabla. Se escoge un tamaño de tabla M >= IDI (M mayor o igual al tamaño del diccionario) y un cierto número irracional cp (normalmente, se usa 1+5A (1/2) /2 o 1-5A (1/2) /2). De este modo, se define h(K) = suelo (M*parte fraccionaria (K *cp)). (https://bit.ly/3LkqjvH). Tabla 1: Hash perfecto vs. hash dinámico Perfecto La función de hash no duplica los valores de las claves o genera valores únicos. No se presentan colisiones. Dinámico Las estructuras de las tablas hash son del tipo árbol, y permiten almacenar un gran número de informaciones. Su mayor eficiencia la presentan en las operaciones de inserción, eliminación y búsqueda. La función hash que genere valores únicos no existe. No pueden crecer, ya que son estructuras estáticas, debido a que necesitan un tamaño fijo. Fuente: elaboración propia. Hash: aplicaciones Existen múltiples aplicaciones que se relacionan con las tablas hash. Una de ellas es la del uso de la firma digital. Cada vez son más las empresas y entidades que se dedican, exclusivamente, a la seguridad en el software. Global Sign es una autoridad certificada por Web Trust que provee servicios de identidad. Fundada en Bélgica en 1996, la compañía ofrece una amplia gama de soluciones de servicios de identidad. Veamos cómo explican en su blog la aplicación del hash en el concepto de firma digital: Base de Datos 12 ¿Cómo funcionan las firmas digitales? Fuente: Global Sign. (2016) ¿Cómo funcionan las firmas digitales? Recuperado de https://www.globalsign.com/es/blog/como-funcionan-las­ firmas-digitales Base de Datos 13 Unidad 2. Índices y árboles Tema 1. Archivos de índices En el apartado anterior, vimos que hay diferentes formas de organización para almacenar la información. Analizamos archivos secuenciales y de direccionamiento calculado (dispersa o hashing). Sin embargo, estas estructuras pueden no ser suficientes para las necesidades de una base de datos. En muchos casos, es necesario hacer uso de unas estructuras de acceso auxiliares llamadas índices. Los índices se emplean para aumentar la performance de acceso a registros, bajo ciertas condiciones de búsqueda. Dichas estructuras proporcionan caminos alternativos para acceder a la información deseada, sin que se vean afectados los datos puros dentro del disco. Los campos de un registro que se utilizan para construir un índice se denominan campos de indexación. Cualquier campo del registro puede ser un campo de indexación y un mismo archivo puede incluir múltiples índices (es decir, más de un campo de indexación por registro). Detallemos, entonces, el funcionamiento de un archivo de índice: cuando se produce una condición de búsqueda que afecta a un campo de indexación, en lugar de acceder directamente al archivo de datos para iniciar la búsqueda (según la organización propia del fichero de datos: ordenada o direccionamiento calculado), se accede previamente a un archivo (llamado índice o archivo de índice) en el que se encuentran los valores del campo de indexación correspondiente -ordenados según la organización propia del índice, junto con un puntero que señala físicamente al bloque de disco que alberga a ese registro en el archivo. El acceso al registro ya es una tarea trivial, según hemos visto. El uso de índices permite llevar a cabo las siguientes acciones: Realizar búsquedas eficientes en archivos de datos organizados en montículo. Acceder, de forma eficiente, mediante condiciones de búsqueda que afectan a cualquier campo en un archivo ordenado (recordemos que a esta organización solo se accedía de forma eficiente cuando la búsqueda se realizaba sobre el campo de ordenación, y este era único para un determinado fichero). Acceder, de forma eficiente, mediante condiciones de búsqueda que afectan a cualquier campo en un archivo con direccionamiento calculado (este accede de forma eficiente cuando la búsqueda se refiere al campo de direccionamiento calculado, pero las búsquedas por otros campos se tienen que realizar secuencialmente). Para poder aplicar los archivos de índice, se debe usar un archivo de tipo secuencial o realizarlo mediante el empleo de estructuras de datos en árbol (árboles binarios), que optimizan las búsquedas. Base de Datos 14 A partir del concepto de índice, podemos tener diferentes posibilidades al crear este tipo de archivos. Veamos, entonces, la clasificación de los diferentes índices que existen: Densos. Una entrada por cada valor de la clave de indexación. No densos o escasos: solo entradas para algunos valores de la clave de indexación. Tipos de índices ordenados de un nivel: o primario o principal; o agrupado; o secundario. Índices multinivel: o índices multinivel; o índices multinivel dinámicos que utilizan árboles B y B+. Tema 2. Índices primarios y secundarios Índice primario En estos índices, es necesario que el archivo de datos esté ordenado (físicamente) por campo clave, y que no contenga valores repetidos. El archivo de índice tiene dos columnas: la primera contiene el valor del campo clave del primer registro de cada bloque, y la segunda un puntero al bloque de datos «puro». Los índices primarios son no densos, es decir, no se cargan todas las claves, ocupan menos espacio que el archivo de datos y poseen registros de longitud fija. Se utiliza la búsqueda binaria porque el archivo es ordenado, y luego la lectura del bloque con el dato de interés. La inserción de datos es un problema, debido a que puede cambiar registros anclas o usar desbordamiento. Para el borrado, se utiliza un marcador en lugar de eliminar el dato físicamente. Figura 7: Índice primario Fuente: [Imagen sin título sobre índice]. (s.f.). Base de Datos 15 Índice secundario Los índices secundarios se usan cuando un archivo ya posee un índice. Se generan por la necesidad de búsquedas sobre campos que pueden o no ser primarios, pero es necesario que no existan valores duplicados (únicos). Pueden existir muchos índices secundarios por archivo de datos, y proporcionan orden «lógico» a los registros almacenados. El archivo índice consta de dos columnas: la primera es el campo de indexación, y la segunda un puntero al bloque o al registro. Si el índice es por clave candidata, hay una entrada en el índice por cada registro en el archivo de datos (índice denso), pero sigue siendo más pequeño que el archivo de datos. Es lento para la búsqueda y crece proporcionalmente. Si el índice es por campo no clave, los valores del campo de indexación se repiten. Ante esto, se puede generar lo siguiente: un índice denso con un registro por cada valor, incluso repetido; un índice con registro de longitud variable con un campo repetitivo de punteros a bloque; un índice no denso, es decir, cada registro almacena puntero a bloque de punteros, y estos apuntan a registros (usado). Figura 8: Índice secundario, puntero a registro Fuente: [Imagen sin título sobre índice]. (s.f.). Base de Datos 16 Figura 9: Índice secundario, puntero a bloque de punteros NumDplo Nombre í f-1. - * Drn TrahaJo Fectia,Nac Suelclo 6 4 8 8 Fuente: [Imagen sin título sobre índice]. (s.f.). Actividad de repaso ¿Cuál de las siguientes es una utilidad de los archivos de índices? o Ocupar espacio extra. o Realizar accesos eficientes al disco. o Hacer eficiente el uso de la memoria RAM Justificación Tema 3. Índices agrupados y multinivel Índice agrupado Precondición: archivo de datos ordenado (físico) por campo no clave. El fichero índice tiene dos columnas: o contiene un registro por cada valor distinto del campo agrupado; o puntero al primer bloque que contiene un registro con ese valor. Es un índice no denso. Ocupa menos espacio que el archivo de datos; registro de longitud fija. Tiene más registros del archivo índice en cada bloque. Permite una búsqueda binaria en el archivo índice y lectura del bloque. Actualización: o inserción y borrado son un problema. Se sugiere reservar un bloque o contiguos por cada valor distinto del campo de indexación. Base de Datos 17 Figura 10: Índice agrupado, más de un valor por bloque Fuente: [Imagen sin título sobre índice]. (s.f.). Figura 11: Índice agrupado, bloque por valor Fuente: [Imagen sin título sobre índice]. (s.f.). Índice multinivel Se aplica después de generar el índice principal, agrupado o secundario. Ese índice de primer nivel es sobre campo clave, valores no repetidos y entradas de longitud fija. Genera el segundo nivel principal, y toma el primer nivel como fichero ordenado con valor distinto en clave. El segundo nivel posee una entrada por bloque. Genera el tercer nivel, si el segundo nivel ocupa más de un bloque. Lo anterior ocurre sucesivamente hasta que las entradas de un mismo nivel se almacenan en un bloque. Base de Datos 18 Figura 12: Índices multiniveles Fuente: [Imagen sin título sobre índice]. (s.f.). Tema 4. Árboles AVL, B y B+ ¿Sabés lo que es un árbol? A continuación, te contamos de qué se trata: Video 1. Estructuras de datos Fuente: Makigas.es [Makigas: tutoriales de programación]. (2016). Estructuras de datos - 11. Introducción a los árboles [YouTube]. Recuperado de https://www.youtube.com/watch?v=Qexq1k8LB6k. ¡Tomate unos minutos para ver video con atención! Árboles AVL Siguiendo a Ponce (201O): Los llamados árboles AVL no son perfectamente equilibrados, pero son lo suficiente como para ofrecer un comportamiento bastante bueno al ser usados. La rama derecha, por lo general, no difiere en altura en más de una unidad de la rama izquierda o viceversa. El factor de equilibrio puede ser almacenado directamente en cada nodo o ser computado a partir de las alturas de los subárboles. Si, al realizar una operación de inserción o borrado, se rompe la condición de equilibrio, hay que realizar una serie de rotaciones de los nodos para volver a equilibrarlo (https://bit.ly/3FCffc1 ). Base de Datos 19 El árbol AVL fue creado por los matemáticos rusos Adelson-Velskii y Landis, y es un tipo especial de árbol binario. Figura 13: Árbol AVL no equilibrado Fuente: [imagen sin título sobre árbol AVL no equilibrado], 2013, https://bit.ly/39ydxqA. Figura 14: Árbol AVL equilibrado Fuente: [imagen sin título sobre árbol AVL equilibrado], 2013, https://bit.ly/3I2IpHB. Árboles B y B+ Los índices multinivel dinámicos, que utilizan árboles By B+, son casos especiales de estructuras dinámicas de datos. Permiten implementar índices multinivel, con la posibilidad de que un índice se expanda o contraiga. Cada nodo contiene los siguientes elementos: 1. un puntero por cada nodo hijo que tiene; 2. valor del campo de indexación. De acuerdo con Rodríguez-Tastets (2017): Las dos limitaciones que tienen los árboles de búsqueda, siendo K un valor de búsqueda de conjunto ordenado, son: dentro de cada nodo: K1