Resumen del Tema 72: Los sistemas de gestión de bases de datos (SGBD)
Introducción a los SGBD
Un Sistema de Gestión de Bases de Datos (SGBD) es un software diseñado para gestionar datos de forma eficiente, permitiendo su almacenamiento, consulta, actualización y eliminación. Facilita el manejo de grandes volúmenes de información mientras asegura integridad, disponibilidad y seguridad de los datos.
Modelos y arquitecturas de bases de datos
- Bases de datos centralizadas:
- Los datos se almacenan en un único servidor central.
- Ventajas: mayor control y gestión centralizada.
- Desventajas: dependencia del servidor central, limitaciones en escalabilidad.
- Bases de datos distribuidas:
- Los datos se almacenan en múltiples nodos interconectados.
- Ventajas: alta disponibilidad, escalabilidad y rendimiento.
- Desafíos: mayor complejidad en sincronización y control de concurrencia.
- Bases de datos federadas:
- Integración de varias bases de datos independientes que colaboran como si fueran una sola.
- Útiles para unificar datos heterogéneos.
- Bases de datos no relacionales (NoSQL):
Diseñadas para aplicaciones con grandes volúmenes de datos o estructuras complejas, como Big Data. Incluyen:- Clave-valor: Datos almacenados como pares clave-valor, eficientes para búsquedas simples (e.g., Redis).
- Documentales: Manejan documentos semiestructurados, como JSON o XML (e.g., MongoDB).
- De objetos: Modelan los datos como objetos, integrando programación orientada a objetos (e.g., db4o).
- De grafos: Almacenan relaciones complejas entre nodos y aristas, ideales para redes sociales o análisis de rutas (e.g., Neo4j).
- Columnares: Optimizadas para consultas analíticas, almacenan datos en columnas en lugar de filas (e.g., Apache Cassandra).
Motores de indexación
Los motores de indexación permiten acelerar las búsquedas en bases de datos, organizando los datos de forma que puedan recuperarse de manera más eficiente.
- Ejemplo: índices B-Tree para bases de datos relacionales o índices invertidos en sistemas de búsqueda documental.
Modelo de referencia ANSI/SPARC
Divide un SGBD en tres niveles para abstraer su funcionalidad:
- Nivel interno: Define cómo se almacenan físicamente los datos en el hardware.
- Nivel conceptual: Muestra la estructura lógica de los datos, independientemente de su almacenamiento físico.
- Nivel externo: Permite a los usuarios acceder a los datos según su necesidad, proporcionando vistas personalizadas.
Monitor de transacciones y control de concurrencia
- Monitor de transacciones:
- Coordina las operaciones en la base de datos para garantizar que sean consistentes.
- Principios ACID (Atomicidad, Consistencia, Aislamiento, Durabilidad) para transacciones.
- Control de concurrencia:
- Permite el acceso simultáneo a los datos por múltiples usuarios o procesos sin comprometer su integridad.
- Técnicas comunes:
- Bloqueos: Evitan conflictos mediante restricciones de acceso a los datos durante una transacción.
- Versionado: Cada transacción trabaja sobre una versión de los datos, evitando bloqueos.
Recuperación de errores
Los SGBD implementan mecanismos para recuperar datos en caso de fallos:
- Journaling: Registro de transacciones realizadas para recuperar el estado previo.
- Snapshots: Copias puntuales de los datos para restaurarlos.
Integridad en bases de datos
La integridad garantiza que los datos en la base de datos sean consistentes, válidos y estén correctamente relacionados:
- Integridad de entidad: Cada registro debe ser identificable mediante una clave única.
- Integridad referencial: Las relaciones entre tablas deben mantenerse mediante claves foráneas.
- Restricciones de dominio: Los valores almacenados deben cumplir reglas predefinidas, como tipos de datos o rangos.
Árboles:
-
Pregunta: ¿Cuál de los siguientes algoritmos se utiliza comúnmente para recorrer un árbol binario en profundidad?
- a) BFS (Breadth-First Search)
- b) DFS (Depth-First Search)
- c) Dijkstra
- d) Kruskal
- Respuesta correcta: b) DFS (Depth-First Search). La búsqueda en profundidad explora una rama del árbol lo más profundo posible antes de retroceder.
-
Pregunta: ¿Cuál es la principal ventaja de un árbol AVL sobre un árbol binario de búsqueda estándar?
- a) Menor consumo de memoria.
- b) Mayor velocidad de búsqueda.
- c) Autobalanceo para mantener una altura logarítmica.
- d) Mejor manejo de datos duplicados.
- Respuesta correcta: c) Autobalanceo para mantener una altura logarítmica. Los árboles AVL realizan rotaciones para garantizar que la altura de los subárboles de cada nodo difiera a lo sumo en una unidad, lo que asegura un tiempo de búsqueda logarítmico en el peor caso.
Grafos:
-
Pregunta: ¿Cuál de los siguientes algoritmos se utiliza para encontrar el camino más corto entre dos nodos en un grafo con pesos positivos?
- a) Dijkstra
- b) Bellman-Ford
- c) Kruskal
- d) Prim
- Respuesta correcta: a) Dijkstra. El algoritmo de Dijkstra es eficiente para encontrar el camino más corto en grafos con pesos positivos.
-
Pregunta: ¿Cuál es la diferencia principal entre un grafo dirigido y uno no dirigido?
- a) Un grafo dirigido tiene ciclos, mientras que uno no dirigido no.
- b) Las aristas de un grafo dirigido tienen un peso, mientras que las de uno no dirigido no.
- c) Las aristas de un grafo dirigido tienen una dirección, mientras que las de uno no dirigido no.
- d) Un grafo dirigido siempre es conexo, mientras que uno no dirigido puede ser disconexo.
- Respuesta correcta: c) Las aristas de un grafo dirigido tienen una dirección, mientras que las de uno no dirigido no.
Hash Tables:
- Pregunta: ¿Cuál es la función principal de una función hash en una tabla hash?
- a) Ordenar los elementos.
- b) Mapear claves a índices.
- c) Eliminar elementos duplicados.
- d) Realizar búsquedas binarias.
- Respuesta correcta: b) Mapear claves a índices. Una función hash transforma una clave en un índice numérico para acceder directamente a la ubicación correspondiente en la tabla.
Complejidad Algorítmica:
- Pregunta: ¿Cuál es la notación asintótica que representa el mejor caso para la búsqueda en un árbol binario de búsqueda balanceado?
- a) O(n)
- b) O(log n)
- c) O(1)
- d) O(n^2)
- Respuesta correcta: c) O(1). En el mejor caso, el elemento buscado es la raíz del árbol, por lo que se encuentra en una sola operación.
Algoritmos de Ordenamiento:
-
Pregunta: ¿Cuál de los siguientes algoritmos de ordenamiento tiene una complejidad promedio de O(n log n) y es estable?
- a) Quicksort
- b) Mergesort
- c) Bubblesort
- d) Selectionsort
- Respuesta: b) Mergesort. Es estable y tiene una complejidad promedio de O(n log n) en el peor de los casos.
-
Pregunta: ¿Cuál de los siguientes algoritmos de ordenamiento in-place es inestable?
- a) Quicksort
- b) Heapsort
- c) Insertionsort
- d) Mergesort
- Respuesta: a) Quicksort. Aunque es eficiente, no garantiza el orden relativo de elementos iguales.
Hashing:
- Pregunta: ¿Cuál de las siguientes técnicas se utiliza para resolver colisiones en una tabla hash?
- a) Árbol binario de búsqueda
- b) Encadenamiento
- c) Ordenamiento por inserción
- d) Todas las anteriores
- Respuesta: b) Encadenamiento. Se crea una lista enlazada en cada celda de la tabla para almacenar elementos con la misma clave hash.
Árboles:
-
Pregunta: ¿Cuál es la altura máxima de un árbol binario perfecto con n nodos?
- a) log2(n+1) – 1
- b) n – 1
- c) n/2
- d) 2^n – 1
- Respuesta: a) log2(n+1) – 1. En un árbol binario perfecto todos los niveles están completamente llenos.
-
Pregunta: ¿Cuál es la principal diferencia entre un árbol AVL y un árbol rojo-negro?
- a) Los árboles AVL tienen un factor de balance más estricto.
- b) Los árboles rojo-negro permiten duplicados.
- c) Los árboles rojo-negro son más fáciles de implementar.
- d) Los árboles AVL tienen una altura máxima garantizada.
- Respuesta: a) Los árboles AVL tienen un factor de balance más estricto, lo que garantiza un tiempo de búsqueda logarítmico en el peor de los casos.
Grafos:
-
Pregunta: ¿Cuál de los siguientes algoritmos se utiliza para encontrar todos los caminos posibles entre dos nodos en un grafo?
- a) Dijkstra
- b) Bellman-Ford
- c) Búsqueda en profundidad (DFS)
- d) Búsqueda en anchura (BFS)
- Respuesta: c) Búsqueda en profundidad (DFS). Puede encontrar todos los caminos, aunque no necesariamente el más corto.
-
Pregunta: ¿Cuál es la complejidad temporal promedio del algoritmo de Dijkstra para encontrar el camino más corto en un grafo con V vértices y E aristas?
- a) O(V)
- b) O(E)
- c) O(V+E)
- d) O(V^2)
- Respuesta: c) O(V+E) utilizando una cola de prioridad.
Estructuras de Datos Avanzadas:
-
Pregunta: ¿Cuál de las siguientes estructuras de datos es más adecuada para implementar un caché LRU (Least Recently Used)?
- a) Pila
- b) Cola
- c) Lista doblemente enlazada
- d) Árbol AVL
- Respuesta: c) Lista doblemente enlazada. Permite insertar y eliminar elementos en cualquier posición de forma eficiente.
-
Pregunta: ¿Cuál es la principal ventaja de una trie sobre un árbol de búsqueda binario para almacenar cadenas de caracteres?
- a) Menor consumo de memoria.
- b) Mayor velocidad de búsqueda de prefijos.
- c) Mejor manejo de datos duplicados.
- d) Todas las anteriores.
- Respuesta: b) Mayor velocidad de búsqueda de prefijos. Las tries almacenan los caracteres de las cadenas en los nodos, lo que permite buscar prefijos de forma eficiente.
Complejidad Algorítmica:
- Pregunta: ¿Cuál de las siguientes afirmaciones sobre la notación Big O es correcta?
- a) O(n) es siempre más eficiente que O(log n).
- b) O(1) representa un algoritmo que nunca termina.
- c) La notación Big O describe el peor caso de un algoritmo.
- d) La notación Big O solo se aplica a algoritmos de ordenamiento.
- Respuesta: c) La notación Big O describe el peor caso de un algoritmo.
Algoritmos de Búsqueda:
-
Pregunta: ¿Cuál es la complejidad promedio de la búsqueda binaria en un arreglo ordenado?
- a) O(n)
- b) O(log n)
- c) O(n^2)
- d) O(1)
- Respuesta: b) O(log n). Divide el espacio de búsqueda a la mitad en cada iteración.
-
Pregunta: ¿Cuál es la principal ventaja de la búsqueda interpolada sobre la búsqueda binaria?
- a) Menor consumo de memoria.
- b) Mejor rendimiento en datos uniformemente distribuidos.
- c) Mayor velocidad en datos aleatorios.
- d) Capacidad de manejar datos duplicados.
- Respuesta: b) Mejor rendimiento en datos uniformemente distribuidos. Aprovecha la distribución de los datos para hacer estimaciones más precisas del punto medio.
Estructuras de Datos Avanzadas:
-
Pregunta: ¿Cuál de las siguientes estructuras de datos es más adecuada para implementar un autocompletar?
- a) Árbol binario de búsqueda
- b) Trie
- c) Tabla hash
- d) Lista enlazada
- Respuesta: b) Trie. Permite buscar prefijos de manera eficiente.
-
Pregunta: ¿Cuál es la principal diferencia entre una cola y una pila de prioridad?
- a) El orden de inserción.
- b) El criterio de extracción.
- c) El tamaño máximo.
- d) La implementación.
- Respuesta: b) El criterio de extracción. Las colas extraen elementos en el orden de llegada, mientras que las pilas de prioridad extraen el elemento con mayor o menor prioridad.
Análisis de Algoritmos:
-
Pregunta: ¿Cuál de las siguientes afirmaciones sobre la notación Theta (Θ) es correcta?
- a) Describe el mejor caso de un algoritmo.
- b) Describe el peor caso de un algoritmo.
- c) Describe el caso promedio de un algoritmo.
- d) Describe el espacio utilizado por un algoritmo.
- Respuesta: c) Describe el caso promedio de un algoritmo. Indica un límite superior e inferior ajustados asintóticamente.
-
Pregunta: ¿Cuál es la complejidad espacial de un algoritmo recursivo que utiliza una pila para realizar llamadas recursivas?
- a) O(1)
- b) O(log n)
- c) O(n)
- d) Depende del tamaño de la entrada
- Respuesta: d) Depende del tamaño de la entrada. El espacio utilizado por la pila depende de la profundidad de la recursión.
Temas Adicionales:
-
Pregunta: ¿Cuál es la principal ventaja de utilizar un grafo dirigido acíclico (DAG) para representar relaciones de precedencia entre tareas?
- a) Permite detectar ciclos.
- b) Garantiza un orden de ejecución único.
- c) Es más eficiente que un grafo no dirigido.
- d) Todas las anteriores.
- Respuesta: b) Garantiza un orden de ejecución único.
-
Pregunta: ¿Cuál de las siguientes estructuras de datos es más adecuada para implementar un conjunto?
- a) Árbol binario de búsqueda
- b) Tabla hash
- c) Lista enlazada
- d) Todas las anteriores
- Respuesta: b) Tabla hash. Proporciona una búsqueda en tiempo constante en promedio.
-
Pregunta: ¿Cuál es la principal diferencia entre un algoritmo online y uno offline?
- a) El uso de memoria.
- b) La disponibilidad de toda la entrada de antemano.
- c) La complejidad temporal.
- d) El tipo de datos de entrada.
- Respuesta: b) La disponibilidad de toda la entrada de antemano. Los algoritmos online procesan la entrada a medida que llega.
-
Pregunta: ¿Cuál de las siguientes técnicas se utiliza para reducir la complejidad temporal de un algoritmo recursivo?
- a) Memorización
- b) Iteración
- c) Búsqueda binaria
- d) Todas las anteriores
- Respuesta: a) Memorización. Almacena los resultados de subproblemas ya calculados para evitar recalcularlos.