Preguntas Parcial Y Final Flashcards
La cursada fue hecha con Moscuzza
¿Para qué sirven los grafos?
Los grafos sirven para modernizar matemáticamente una estructura de datos.
Desarrolle el concepto de Grafo, utilización de tipos y representación computacional de los mismos.
Es una pareja G=(V,A), donde V es un conjunto de vértices (o nodos) y A es un conjunto de pares que une dichos vértices, llamadas aristas. Sirve para establecer relaciones. Pueden mantener o no jerarquía entre sí, y en caso de hacerlo, dicha jerarquía se representa poniendo un sentido al arco.
Los grafos pueden ser dirigidos o no dirigidos, y pueden ser restrictos o irrestrictos.
La representación computacional se puede dar por estructuras estáticas como dinámicas. Entre las estáticas se encuentran la matriz de adyacencia, y la matriz de incidencia. Entre las dinámicas se pueden representar por Listas, como PFlatz, Siklosy, o listas de adyacencias. La estructura estática es menos conveniente en casi todos los casos, porque ocupa más espacio (O(V2))y no es flexible para el crecimiento del grafo, pero tiene menos costo computacional. La estructura dinámica es más conveniente debido a que ocupa menos espacio (O(V+A)), pero tiene un costo computacional mayor.
Definición de maximal.
Conjunto de nodos desde los cuales no parte ningún arco hacia otro lado (los bucles no se tienen en cuenta).
Definición de minimal.
Conjunto de nodos desdes los cuales no llega ningún arco proveniente de otro
nodo (los bucles no se tienen en cuenta).
Definición de grafo restricto.
Son aquellos grafos los cuales solo pueden modelizar relaciones que no cumplan con las propiedades de reflexión, simetría y transitividad.
Definición de grafo irrestricto. Cómo se representa computacionalmente
Son aquellos grafos los cuales pueden modelizar relaciones sin importar si cumplen o no ciertas propiedades.
Para representarlo computacionalmente existen dos formas: una dinámica y otra estática.
En el caso de la dinámica, se puede crear una lista por cada nodo que indique las relaciones que tiene con los otros nodos. En el caso de la estática, se puede crear una matriz (vector de dos dimensiones) que almacene con un bit las relaciones entre los nodos.
Definición de grafo completo.
Grafo en el cual para cada par de nodos existe un arco que los une.
Tipos de representación computacional. Ventajas y desventajas.
Representación estática: matriz de adyacencia o matriz de incidencia.
Representación dinámica: listas enlazadas o representación de Pfaltz. Las listas enlazadas convienen para grafos dispersos.
Representación estática
Ventajas
Permite un acceso más fácil de forma directa por posición.
Desventajas
~ Puede llegar a ocupar espacio innecesario.
~ No permite guardar atributos.
Representación dinámica
Ventajas
~ Solo se ocupa el espacio necesario.
Desventajas
~ Para acceder a los datos hay que recorrer toda la lista.
Condiciones que tiene que cumplir un grafo para ser un arbol.
Un grafo G (P,E) es un árbol si cumple con las siguientes propiedades:
1) ACICLICO: El grafo no tiene ciclos
2) |P| = |E| + 1
3) Para todo a perteneciente a E => a es desconectante
4) Para todo x,y pertenecientes a P => Existe un walk único (x,y)
Un nodo solo puede ser un árbol.
VOF? Grafos / Árboles – Un grafo que posee un solo nodo siempre es un árbol.
Verdadera, porque cumple las 4 condiciones.
Definición de árbol completo.
Un árbol es completo cuando todos sus nodos no maximales (nodos
que no son hojas) tienen igual grado de salida.
Tipos de barridos.
Preorden (raíz - subárbol izq - der).
Simétrico (izq - raíz - der).
Postorden (izq - der - raíz).
Espacio desperdiciado de un árbol r-ario.
Para calcular el espacio desperdiciado se utiliza:
(r-1) * | P | + 1
Donde r = Grado del árbol y | P | = N° de nodos.
¿Para qué se utiliza la transformada de Knuth?
Se utiliza para transformar árboles r-arios en árboles binarios.
VOF? Knuth – Si un árbol n-ario tiene 2 niveles, entonces la profundidad máxima que puede alcanzar un nodo en la trasformada de Knuth es n.
Para mi falsa porque la profundidad puede ser mayor, por ejemplo en la carpeta yo tenia un arbol de grado 4 y que un nodo tiene una profundidad de 6, profundidad es la cantidad de arcos que hay de distancia entre la raiz y un cierto nodo.
VOF? Knuth: El barrido de pre orden del árbol r-ario original coincide con el pre orden del binario.
V
Definición de árbol balanceado.
Árbol que para todo nodo se cumple que la Cardinalidad del
subárbol izquierdo es igual a la Cardinalidad del subárbol derecho o difiere en 1.
Todo arbol balanceado es AVL. No todo árbol AVL es balanceado.
Definición de árbol AVL.
Arbol que para todo nodo se cumple que el nivel del subárbol izquierdo es
igual al nivel del subárbol derecho o difiere en 1.
Todo arbol balanceado es AVL. No todo árbol AVL es balanceado.
¿Para qué se utiliza la rotación y qué garantiza?
La rotación de arboles se utiliza para balancear un árbol en un punto critico determinado.
La rotación garantiza que el barrido simétrico del árbol rotado sea igual al barrido
simétrico del árbol original desbalanceado.
VOF? El barrido de pre orden se puede hacer en todo tipo de árboles pero el simétrico es solo para árboles binarios.
V. El barrido simétrico consiste en recorrer el árbol de la siguiente forma:
- Visitar el subárbol izquierdo.
- Informar la raíz.
- Visitar el subárbol derecho.
Conceptualmente que exista un nodo hijo izquierdo y derecho se produce porque el grado de todos los nodos es 2. Por lo tanto se trata de árboles binarios.
VOF? Un grafo que posee n nodos y ( n - 1 ) arcos siempre es un árbol.
es falso pero porque ademas de esta condicion se tienen que cumplir otras mas:
- arbol aciclico
- todo arco es desconectante
- existe walk unico para todo x, y (camino sin direccion entre x e y)
- sumatoria de nodos = sumatoria de arcos + 1
VOF? Arbol B- Al dar de alta una nueva clave, solo puede producirse un slip.
Falso. Solo hay slip si no hay punteros disponibles.
VOF? Arbol B- si el load factor es de 100% y la altura del árbol es mayor a 1, todas las hojas tienen la mitad de los punteros ocupados.
V
Explique en no más de 10 reglones la diferencia entre árbol completo y árbol lleno.
Un árbol completo es una estructura de datos cuyos nodos no maximales tienen el mismo grado de salida.
Ej:
O
/ \
O O
/ \
O O
En cambio un árbol lleno es una estructura de datos en la que sus nodos maximales se encuentran en el mismo nivel. Es un caso particular de árbol completo.
Ej:
O
/ \
O O
/ \ / \
O O O OVoF? Un árbol de grado mayor a dos no puede ser representado mediante una representación computacional estática.
F. No se podría visualizar, pero se puede implementar una matriz multidimensional y poner todas las combinaciones.
VoF? Si un árbol B tiene N claves entonces el grado es N+1.
F. El grado del árbol depende de la cantidad de claves que soporta por nodo y su load factor. Lo que no quiere decir que va a tener N+1 grado.
VoF? Es posible realizar un barrido simétrico en un árbol n-ario con n>2.
F. Solo se puede en árboles binarios. Para un arbol n-ario se puede aplicar el algoritmo de Knuth y transformarlo en binario.
VoF? Al aplicar un barrido simétrico sobre un ABB se obtiene el conjunto de datos ordenados.
V. El barrido simetrico, o también conocido inorden, evalua el nodo izquierdo, luego la raíz, y por último el nodo derecho, así recursivamente, por ende, siendo el ABB un arbol ordenado donde los nodos de la izquierda son menores a la raiz y los de la derecha mayores, cuando haces un barrido inorden se puede leer la secuencia ordenada.
VoF? El árbol lleno y el árbol completo son dos tipos de árboles binarios balanceados.
F. El arbol lleno y el completo son dos propiediades de árboles.
VoF? El Árbol B+ nunca puede quedar lleno.
F. La diferencia que tiene el árbol B+ es que tiene un número mínimo de claves por registro, que es la mitad al número máximo.
VoF? Sobre un árbol n-ario con n>2 se pueden realizar los siguientes barridos (recorridos) preorden, simétrico, postorden, y por niveles.
F. Solo se puede aplicar dichos barridos para árboles binarios. El barrido simétrico solo se puede realizar en árboles con n=2. Para eso es que se usa el algoritmo de Knuth, para transformar un árbol n-ario en binario y poder aplicarle el barrido simétrico.
VoF? El Arbol B es más óptimo para la búsqueda de claves puntuales que la estructura de Hashing.
F. El Arbol B es más óptimo para la búsqueda de claves secuenciales que el hashing. El hashing es más óptimo para la búsqueda de claves puntuales.
VoF? Es posible implementar el concepto de ABB (Arbol Binario de Búsqueda) en un array.
V. Es posible por medio del barrido por niveles, y con las operaciones sobre los índices para obtener los hijos de la rama izquierda y los de la rama derecha.
VoF? Todo grafo de grado 2 es un árbol binario.
F. Para que sea un árbol no debe haber ciclos en el grafo y debe ser conexo. Independientemente del grado del grafo. Si el grafo es de grado 2, pero es cíclico, no nos encontraríamos con un árbol (por definición de árbol).
VoF? ABB - Cuando un ABB se basa en un árbol AVL su orden de complejidad será el mejor O(n log2 n).
F. La complejidad computacional promedio es O(log n) y el peor de los casos es O(n).
VoF? La cantidad de nodos de un árbol de expresión siempre es par.
F. Basta con solo contradecir la afirmación poniendo el arbol de la expresión: (10 + 5) * 3. Lo que daría 5 nodos, siendo este un número impar.
VoF? Un árbol de expresión siempre estará balanceado en su raíz.
F. No necesariamente. Depende del tipo de barrido utilizado (PreOrden, InOrden, PostOrden) y de la expresión representada.
VoF? Los grafos irrestrictos solo pueden representarse computacionalmente de manera dinámica.
F. Pueden representarse mediante matrices de adyacencia, que es una estructura estática.
VoF? Para reducir espacio al representar un grafo siempre es más conveniente la forma dinámica que estática.
F. El espacio ocupacional de una representación dinámica de un grafo es O(V + A), mientras que el de una representación estática es de O(V2). La representación dinámica siempre aprovecha mejor el espacio, y es más flexible para el crecimiento del grafo, aunque tiene mayor costo de procesamiento. Mientras que la representación estática carece de dicha flexibilidad, pero tiene menor costo procesamiento. Si la cantidad de Vertices es de 0 o 1, la complejidad computacional es la misma para ambos, dado que a 0 vertices, no hay aristas, entonces O(0+0) = 0, y O(02) = 0; O(1 + 0) = 1 y O(12) = 1. Por ende NO SIEMPRE es más convieniente la dinámica que la estática.
VoF? Si un árbol binario está completo y balanceado, todas las hojas están en el mismo nivel.
F. Un Arbol completo de nivel N, es cuando tiene hojas tanto en el nivel N, como el N-1, y un arbol es balaceado (AVL), cuando en ambas ramas tiene la misma profundidad y dicha profundidad es N o N-1. Por ende no necesariamente debe tener hojas en el mismo nivel.
Explique las diferencias, ventajas y desventajas de los métodos de Hashing y árbol B
Ambos métodos son aplicables al armado de índices en las bases de datos:
Mientras que hashing permite mayor velocidad de acceso directo, árbol B entrega mejor performance a la hora de realizar accesos secuenciales.
Ambos permiten claves duplicadas, pero solo árbol B acepta una clave que no sea completa.
Mientras que árbol B desperdicia mucho espacio en nodos y punteros, hashing solamente necesita al menos una tabla de índices.
–
El Hashing tiene como ventaja el acceso rápido a una clave específica, a diferencia del arbol B que tiene como ventaja el acceso secuenciald e claves.
El Hashing se encuentra en memoria principal, mientras que el B tree puede estar en memoria secundaria
El Hashing tiene la desventaja de que se pueden producir colisiones, teniendo que generar una función de rehash, mientras que el arbol B no tiene colisiones (puede soportar duplicados), pero tiene un costo computacional muy alto cuando se llenan los nodos, teniendo que splitear todos los nodos dado que todos se encuentran en el mismo nivel.
VOF? Árbol B – Todas las hojas se encuentran en el mismo nivel.
Verdadera, Un árbol-B se mantiene balanceado porque requiere que todos los nodos hoja se encuentren a la misma altura.
VOF? Árbol B – El árbol B es más performante que el árbol B+ en el manejo de consultas por clave puntual.
F. El árbol B+ es una estructura que guarda los datos en las hojas y es muy utilizado por los motores de base de datos para la creación de índices. Entonces al basarse en un árbol balanceado donde los datos se encuentran en el mismo nivel, la consulta por clave puntual es más performante.
Quicksort vs Heapsort.
- El Quicksort es más sencillo y tiene menos líneas de codigo que el Heapsort aunque tiene un orden de complejidad más alto.
- El Heapsort generalmente es más rápido que el Quicksort, aunque no en todos los casos.
- El Quicksort puede llegar a ejecutarse menos veces que el Heapsort en el mejor de los casos.
VOF? El algoritmo de quick sort no puede ser recursivo.
F, justamente tambien se lo llama procedimiento recursivo, asi que si puede ser recursivo.
VOF? El algoritmo Quicksort sobre un conjunto de datos desordenados tiene una complejidad menor que si se ejecuta sobre datos ordenados.
V. El algoritmo quicksort en el mayor de los casos tiene un orden de complejidad de n log N. Esto se da cuando el valor de pivote elegido se encuentra en el centro de la lista. En el peor de los casos el órden de complejidad es n2 y se da cuando el valor del pivote se encuentra en alguno de los extremos o cuando la lista está casi ordenada.
VOF? En cada paso del algoritmo de quicksort un elemento es ubicado en su posición definitiva.
V
VoF? El peor caso del algoritmo de ordenamiento Quicksort es igual al de Heapsort.
F. En el peor de los casos, QuickSort tiene una complejidad computacional de O(n2), mientras que heapsort mantiene siempre su misma complejidad computacional que es O(n log n).
VoF? El algoritmo QuickSort es siempre más rápido que Heap Sort.
F. El Heapsort es más rápido que QuickSort en todos los casos, dado que en el peor de los casos HeapSort tiene una complejidad computacional de O(n log n), mientras que QuickSort tiene una complejidad computacional de O(n2).
VoF? El algoritmo Heapsort siempre tiene la misma complejidad computacional para cualquier orden en el que ingresan los datos.
V. Siempre es O(n log n) para el mejor caso, el peor caso, y el caso promedio.
VoF? El Quicksort es más performante que el Heapsort, sin importar cómo vengan los datos (ordenados o desordenados).
F. En el peor de los casos, el Quicksort tiene una complejidad computacional de O(N2), y en el mejor de los casos y el promedio tiene una complejidad computacional de O(n log n), igual que en todos los casos de HeapSort.
VoF? El Heapsort tiene peor rendimiento si los datos ya vienen ordenados.
F. Ante cualquier cualquier caso, Heapsort tiene una complejidad computacional de O(n log n), y el peor rendimiento para el peor caso lo tiene QuickSort, que tiene una complejidad computacional de O(n2).
VoF? Si tengo un conjunto de datos tendiendo a ordenados, el algoritmo de Quicksort es el más eficiente para su ordenamiento total.
F. Si tiende a ordenado, sería el peor de los casos, y su complejidad computacional tiende a O(n2), siendo el peor de los casos.
VoF? El Orden de complejidad de un ABB siempre es mejor que el Orden de complejidad de Quicksort.
V. El orden de complejidad de un ABB es en promedio O(log n), mientras que el promedio del Quicksort es de O(n log n), en los peores casos, el ABB tiene un orden de complejidad O(n), mientras que el QuickSort es de O(n2).
VoF? El algoritmo de Quicksort tiene en promedio un grado de complejidad O(n log n) pero en determinada circunstancia puede tener grado de complejidad O(n2) y ser el peor de todos los métodos de clasificación.
V. QuickSort tiene como mejor caso y caso promedio, un O(n logn), pero en el peor de los casos tiene un O(n2), a diferencia del HeapSort y MergeSort que en todos sus casos tiene un O(n logn).
VOF? Huffman – La longitud variable del código no puede superar los 8 dígitos.
F
VoF? El algoritmo de Huffman siempre se basa en árboles completos.
F. Depende de la frecuencia de uso de los caracteres en cuestión. Puede pasar que el árbol no quede completo al haber pocos caracteres con mucha frecuencia y muchos con frecuencia mínima.
oF? El algoritmo de Huffman se basa conceptualmente en un árbol binario del que consigue los códigos comprimidos para cada caracter.
V. Se basa en un arbol binario que consigue los códigos comprimidos para cada caracter según la frecuencia de uso de cada uno.
VoF? La cantidad de nodos de un árbol de Huffman siempre es impar.
V. Dado que la fórmula para saber la cantidad de nodos es: (hojas * 2) -1, esto SIEMPRE va a dar un número impar.
VoF? En el árbol de Huffman la cantidad total de nodos es la siguiente: (total de hojas * 2) -1.
V. Dado que el árbol de Huffman va tomando 2 caracteres de menor frecuencia y los une por medio de un nodo auxiliar, y así recursivamente, se llega a que la fórmula de expresión para saber la cantidad total de nodos es: hojas * 2 - 1.
VoF? Huffman - El árbol en el que se basa es un árbol principal derecho balanceado.
F. Depende de la frecuencia de ocurrencia de uso de los caracteres.
VoF? El algoritmo de Huffman obtiene los códigos comprimidos parseando un árbol binario balanceado.
F. No necesariamente tiene que estar balanceado el árbol. Eso depende de la frecuencia que aparezca el caracter.
Detalle las estructuras del algoritmo de Huffman.
Las estructuras son 4, tenes la tabla de frecuencias que siempre arranca en 1 y una vez que pasas a la frecuencia siguiente vas a pasar el puntero abajo de todo devuelta, despues tenes el arbol binario que lo armas desde las hojas hasta la raiz teniendo en cuenta que todos los caracteres son hojas. Para saber si es 0 o 1, el arco del hijo izquierdo es 0 y el arco del hijo derecho es 1. Ahora la estructura que sigue es la pila, porque vos metes los 0 y 1 desde la hoja hasta la raiz, cuando siga despues de la raiz va a venir un caracter porque todos los caracteres son hojas, entonces va a cortar y sabe que hasta la raiz es el codigo del caracter anterior. Y despues para leerlo haces LIFO, lo lees desde la raiz hasta la hoja y ese es el codigo del caracter. Y despues la ultima estructura es la del archivo original y archivo comprimido, vos vas a poner todos los codigos de caracteres uno al lado del otro y los concatenas formando de 8 bits para obtener que caracter en ASCII es.
VOF? Si el puntero Ledge de un nodo no es nulo, entonces el nodo es un minimal.
Si el puntero ledge no es nulo, quiere decir que a ese nodo le esta entrando un arco, es falso porque en los minimales solo salen arcos, no le entra ninguno.
VOF? Si se usara para implementar un árbol el puntero link es siempre nulo.
V. El puntero “LLINK” en la implementación de Pfaltz se encuentra en la estructura de arcos y contiene la dirección del primer elemento de una listas de arcos con el mismo “RPOINT”, es decir, aquellos arcos que llegan al mismo nodo que al que está analizando. Los nodos en los árboles tienen un solo camino desde la raíz hasta el mismo par lo que ese campo estaría vacío.
VOF? PFaltz - todos los arcos con idéntica 2da componente se enlazan mediante el Rlink.
V
Detalle las estructuras del algoritmo de Pfaltz.
Serían dos listas, una para nodos y una para arcos.
La de nodos tiene: ID, Funciones, LEDGE, REDGE, y NEXT (puntero al próximo).
Y la de arcos tiene: ID, Funciones, RLink, LLink, RPoint, LPoint y NEXT (puntero al próximo).
VOF? Siklossy - si hay un único nodo en la estructura este apunta al front.
Falso. (El valor para el cual se usa el or exclusivo no tiene nada que ver con la posición del FRONT).
VOF? Usando el método Hashing into buckets la tabla de hash puede ser mas chica que la cantidad de claves a alocar.
V
VOF? Al aplicar la función de dobles a la clave 7373 el resultado da uno.
V. La función de dobles separa el número?? de dos mitades, las convierte a binario y luego las suma con or exclusivo y eso lo pasa a decimal de nuevo. En este caso, ambas partes serían 73 en binario, por lo que el sumarles? Cada par de dígitos va a dar uno por ser iguales.
El cero en binario también es cero en decimal, por lo que el resultado final será cero.
(tabla de verdad de or exclusivo).
VOF? Hashing - Al aplicar la función de dobles a la clave 4444 el resultado es 0.
V
VoF? El método de Hashing resuelve más eficientemente las búsquedas con rangos de claves.
F. El método de Hashing resuelve eficientemente las búsquedas directas, y el Árbol B resuelve las secuenciales y por rangos.
VoF? La implementación de la cantidad de entradas para claves en una tabla de hash es dinámica.
F. La cantidad de entradas en una tabla de hash es estática por definición.
VoF? Hashing es más performante que el árbol B en la búsqueda de una clave particular existente.
V. Para la búsqueda de claves específicas, Hashing es más performante. Para la búsqueda de claves secuenciales, árbol B es más performante.
VoF? La indexación de Hashing es más óptima que el árbol B para buscar valores por rangos.
F. Hashing es más óptima para la busqueda de valores directos, en cambio los de Arbol B es más óptima para la búsqueda de valores por rangos.
VoF? El método de árbol B es más rápido que Hashing para la creación de Índices.
F. Para la creación del INDEX, no siempre se da el caso de que es más rápido. Depende los campos utilizados y los tamaños.
VoF? El método de hashing es más performante que el método de Arbol B para el manejo de claves duplicadas.
F. El método de hashing es performante para el acceso directo a las claves, y justamente tiene problemas por no soportar claves duplicadas, donde hay métodos para manejar dichas “colisiones”. En cambio, y escrito por Reinosa, “El árbol B puede administrar claves duplicadas si las hay, está una debajo de la otra en la hoja que les corresponde apuntando cada una de ellas a la componente de datos correspondiente.”
Componentes de una base de datos
- Datos: Los datos pueden ser integrados (minimiza la redundancia) o
compartidos (pueden ser accedidos de forma concurrente). - Programas – Procesos: El DBMS es el programa más importante, los procesos
controlan las actividades del DBMS y abstraen al usuario de los detalles a nivel
de HW. - Usuarios: Hacen referencia a los programadores de la aplicación, al DBA
(Administrador de BD), a los usuarios finales y a otros grupos funcionales. - Tecnología: Hacen referencia al Hardware (Memoria) y el Software (Sistema
operativo).
VoF? La única manera de establecer la integridad de los datos es mediante el CHECK.
F, La integridad de los datos pueden ser por entidad o referencial, y los mismos se pueden dar por definiciones de dominio como son las contraint de primary key, foreign key, y las de UNIQUE.
Detallar en una carilla todo lo que sepa del objeto de BD Constraint y su relación con integridad.
Las constraints se basan en tres tipos de integridades:
-integridad de entidad: es usada para asegurar que los datos pertenecientes a una misma tabla tienen una unica manera de identificarse, es decir que cada fila tenga una PK capaz de identificar univocamente una fila y esa no puede ser nula.
-integridad referencial: es usada para asegurar la coherencia entre datos de dos tablas, aca se hace referencia a la FK. Ademas las constraints referenciales permiten a los usuarios especificar claves primarias y foraneas para asegurar una relacion padre hijo.
Hay tres tipos de constraints referenciales: ciclic referencial constraint, self referencing constraint y multiple path constraint.
-integridad semantica: es la que nos asegura que los datos que vamos a almacenar tengan una apropiada configuracion y que respeten las restricciones definidas sobre los dominios o sobre los atributos. Son data type, default, unique, not null y check.
¿Qué es algo que caracteriza a las BD no relacionales?
Las BD no relacionales no cumplen con consistencia.
Backup y Restore. Definición y tipos.
Backup es copiar total o parcialmente la información de una BD y
almacenarla en otro sistema de almacenamiento masivo. Los tipos de backups son
1. Backup completo o full: Se guarda toda la información que se actualizó.
2. Backup incremental diferencial: Se guarda la información que se actualizo a
partir de una fecha tomando como punto de partida (delta T) la fecha del ultimo
backup incremental.
3. Backup incremental acumulativo: Se guarda la información que se actualizo a
partir de una fecha tomando como punto de partida (delta T) la fecha del ultimo
backup full.
4. Backup en caliente: Se realiza cuando la aplicación está funcionando.
5. Backup en frio: Se realiza cuando la aplicación no esta en uso.
6. Backup de logs transaccionales: Se realiza sobre logs transaccionales.
Niveles de aislamiento.
- READ UNCOMMITED: minimiza el overhead ya que no genera bloqueos. En contrapartida puede generar Lecturas sucias, lectura no repetibles, y lecturas fantasmas.
- READ COMMITED: Es la opción por defecto de SQL. Una operación de lectura establece un bloqueo compartido sobre los datos que se están leyendo, pero se desbloquea al cuando finaliza dicha operación (SELECT). Evitando las lecturas sucias, pero con la posibilidad de generar lecturas no repetibles y lecturas.
- REPEATABLE READ: La operación de lectura (SELECT) establece un bloqueo compartido hasta el final de la transacción (COMMIT), para poder garantizar que no se produzcan lecturas no repetibles. Si bien tampoco genera lecturas sucias, podría generar lecturas.
- SERIALIZABLE: Bloquea la inserción y lectura en todos los valores del rango propuesto en el WHERE para poder así evitar lecturas fantasmas. De más está decir que evita lecturas no repetibles y lecturas sucias.
Definición de índices.
Los índices son una estructura asociada a una tabla en una base de datos con el fin de mejorar la performance de la misma. Son independientes de la información física.
Estos pueden llegar a ser basados en la técnica de hashing o en árboles B. Cada uno tiene sus ventajas y desventajas, principalmente en el acceso a datos. Mientras que hashing es mejor para el acceso directo, árbol B es mejor para el acceso secuencial.
Ventajas y desventajas de los índices.
La gran ventaja de los índices es que te permite acceder a los datos de forma más rápida, mejorando la performance de las consultas. La gran desventaja es que necesitas de espacio adicional para almacenar y mantener las estructuras que se crean para los índices. Tienen un costo ocupacional y computacional muy alto, dado que al hacer inserts, deletes, o updates, generan que se recalculen los índices.
Utilización de los índices.
Sirven para mejorar la performance de las consultas donde hay JOINs, WHEREs, y ORDER BY.
Tipos de índices.
B tree index
B tree cluster index
Reverse key index
Bitmap index
Clasificación de los índices.
Los índices pueden ser:
- UNIQUE (únicos)
- CLUSTER (Los datos se ordenan físicamente igual que el índice).
- DUPLICADOS (Dos índices para un mismo campo).
- COMPUESTOS (Un índice compuesto entre 2 o más campos).
VoF? Los índices sólo se usan en las base de datos para ganar velocidad.
F. También sirven para asegurar unicidad para las filas almacenadas.
Explique el objetivo de los índices y sus tipos.
El objetivo de los índices es acceder de forma más rápida a los datos almacenados en las tablas. Son estructuras opcionales asociadas a estas que son independientes física y lógicamente de los datos almacenados. Se pueden crear distintos tipo de índices sobre uno o más campos. Los tipos de índices son los siguientes: B-Tree index B-Tree clustered index Bitmap index (oracle) Hash index (mysql) Functional index/function based index Reverse key index La estructura de Árbol-B es la más utilizada por los motores de bases de datos para la creación de los índices. La variante que usa cluster ordena los índices, por lo que al entrar de forma contigua son accedidas de forma más eficiente.
Explique el concepto de utilización de una vista.
Una vista (VIEW) es un objeto de DB el cual es utilizado para encapsular una consulta a una o más tablas, pudiendo cambiar la forma de representar los datos para quien consume la vista. Internamente no guarda los datos de la vista, sino que hace la consulta a las tablas. Sirven para facilitar el acceso de ciertas consultas complejas a las aplicaciones para que éstas aprovechen mejor la forma en que se muestran los datos. También generan mayor seguridad dado que no se muestra la tabla cómo realmente es.
Detallar en una carilla todo lo que sepa del objeto de BD Vista y su relación con seguridad.
Una view es un conjunto de columnas, ya sea reales o virtuales, de una misma tabla o no, con algún filtro determinado o no.
De esta forma, es una presentación adaptada de los datos contenidos en una o más tablas, o en otras vistas. Una vista toma la salida resultante de una consulta y la trata como una tabla.
Se pueden usar vistas en la mayoría de las situaciones en las que se pueden usar tablas.
Caracteristicas:
- tiene nombre especifico
-No aloca espacio de almacenamiento
-No contiene datos almacenados.
-Está definida por una consulta que consulta datos de una o varias tablas.
Las vistas se pueden utilizar para:
•Suministrar un nivel adicional de seguridad restringiendo el acceso a un conjunto predeterminado de filas o columnas de una tabla.
•Ocultar la complejidad de los datos.
•Simplificar sentencias al usuario.
•Presentar los datos desde una perspectiva diferente a la de la tabla base.
•Aislar a las aplicaciones de los cambios en la tabla base.
También y con respecto a la seguridad estaria bueno mencionar el uso del with check option ya que con esto se puede actualizar siempre y cuando el checkeo de la opción en el where sea verdadero.
Qué es una tabla temporal, mencione un ejemplo concreto de su uso.
Una tabla temporal es una tabla creada cuyos datos son de existencia temporal. No son registradas en las tablas de diccionario de datos. No es posible alterarlas, si eliminarlas y crear los indices temporales que necesite una aplicacion. Las actualizaciones a una tabla temporal podrian no generar ningun log transaccional si asi se configurara. Un ejemplo en donde te conviene usarlas es como almacenamiento intermedio de consultas muy grandes ya que si usas tablas temporales podes crear tablas con resultados intermedios basados en consultas de menor tamaño en lugar de intentar ejecutar una consulta unica que sea demasiado grande y multiples joins.
VOF? Siklossy – Si la dirección de un nodo es 0011, entonces la calda link de ese mismo nodo no puede tener el valor 0011.
V. Porque el algoritmo de Siklossy se basa en el or exclusivo por lo mismo no podrá repetirse el valor.
VOF? Hashing – Al producirse una colisión en direccionamiento abierto se debe agregar un nuevo nodo en la lista para esa posición.
F. Depende de que método se use para reducir las colisiones. Podría ser rehashing, chaining o separate chaining (hashing into buckets).
Explique el acceso a datos por Árbol B+, mencionar de que modo resuelve las búsquedas por rangos.
A diferencia del árbol B, el Árbol B+ tiene arcos entre sus hojas lo cuál facilita las busquedas por rangos.
El árbol B empieza su recorrido en la raíz y va hasta una hoja, luego vuelve a la raiz y va a la siguiente hoja, lo cual lo hace altamente performante para busquedas por rangos.
En cambio, el árbol B+ no necesita volver a la raiz si no que cuando llega a la primer hoja del rango simplemente avanza hacia sus hermanos.
Explicar el modelo ANSI Sparc.
Según el modelo ANSI/SPARC nuestra base de datos está dividida en tres niveles: Nivel Interno (Fisico): Se ocupa de la implementación fisica de los datos. Se especifican las estructuras de datos, se definen índices y métodos de acceso, etc. Nivel Conceptual (Lógico): Es el nivel intermedio que interactua entre el nivel interno y el externo. Es el encargado de agurpar todas las vistas en una sola. Tambien es la representación abstracta de la DB ya que tiene estructuras orientadas al usuario (archivo, campo, registro). Se define mediante un esquema conceptual que se escriba en DDL. Contiene definiciones del contendio de la DB, tipos de datos, restricciones Nivel Externo (vistas): Se ocupa de la forma en que los usuarios recibiran la información. Esto se puede dar por medio de distintos lenguajes, entre ellos el PL/SQL, y los usuarios finales acceden por medio de alguna interfaz.
VOF? La transformada de knuth es un algoritmo cuyo objetivo principal es optimizar el uso de memoria al implementar un árbol r-ario.
V
VOF? El árbol B+ es más performante que el árbol B en el manejo de consultas por rango.
, ya que posee un puntero en cada nodo para “pasar” de un nodo “hermano” sin necesidad de regresar al nodo padre previamente, como es el caso de árbol B.
Definición de clustering.
El “clustering” es la probabilidad que se distribuya uniformemente las claves.
VOF? Árboles – Hallar el right del nodo raíz en un árbol r-ario con r = 4 es menos performante que hallar el right de un nodo en la transformada de Knuth.
V, ya que la T. de Khuth es un árbol binario.
VOF? Hashing – El método de “Dobles” permite resolver el problema de colisiones entre claves distintas.
F. El método de dobles es solo un método para implementar una función de hashing. Esta consiste en dividir a clave en dos partes, cada una transformarlas en binario, realizar la operación de OR exclusivo entre ellas y el resultado en decimal será el cubíndice de la tabla donde se encontrará la dirección que apunta a los datos.
El problema de colisiones se puede resolver con rehashing (solución final o hashing doble) o con chaining o encadenado (hashing into buckets).
VoF? La única manera para asegurar unicidad de os campos es con una Primary Key o con un UNIQUE.
F, con un trigger también se puede.
