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.
Describa las diferencias entre Store procedure, una función y un Trigger
Un Store procedure es objeto de DB, que consta de un conjunto de operaciones el cual puede tener parámetros, y genera modificación de los datos (tiene efecto de lado) sin retornar información alguna.
Una funcion es un conjunto de operaciones el cual puede tener parámetros, que no tiene efecto de lado, solo retorna valores. Se pueden llamar en Contraints o Consultas
Un Trigger es un objeto de DB el cual se attacha a un evento y ejecuta operaciones o procedimientos. Tiene efecto de lado, o sea que puede modificar los datos de la DB y no devuelve valores.
Explique las principales características que diferencian a una DB operacional de un DW
Una DB operacional está normalizada, es relativamente más pequeña que un DW, es volátil dado que la información cambia todo el tiempo. El tiempo de consulta es relativamente menor que en los DW. La información tiende a estar organizada para el uso de aplicaciones.
Qué objetos y funciones dispone un motor de DB para el manejo de seguridad de datos.
El motor de DB dispone de objetos de base de datos como son los TRIGGERS y las Vistas. Los triggers son utilizados para hacer logs de auditoria, o chequeos de permisos. Las vistas se usan para encapsular consultas de una o varias tablas joineadas escondiendo la implementación real de cada una y de esta forma, entre otros usos, defenderse de ataques de seguridad.
Desarrolle el concepto de Restore y Recovery
Recovery: Lleva la DB a un estado consistente utilizado los logs transaccionales
Restore: Restaura la DB en base a los backups generados anteriormente.
Explique qué significa la sigla ACID y desarrolle cada concepto.
Atomico, Consistente, Aislamiento (isolation), Durable.
Atomico: los DBMS garantiza que cada transacción se efecua de manera atómica, o sea que se hacen todas las operaciones o ninguna
Consistente: Se asegura que la DB va a quedar consistente luego de cada cambio en los datos, o sea que no se romperá
Aislamiento (Isolation): Te asegura que en caso de haber concurrencia sobre una tabla, cada transacción va a manejar un conjunto de datos para poder efectuar sus operaciones. El nivel de aislamiento se puede configurar, y son: READ UNCOMMITED, READ COMMITED, REPEATABLE READ, SERIALIZABLE.
Durable: La idea es que la información va a estar persistida, o sea que una vez que la transacción se acepto, los cambios van a quedar por más que el sistema falle.
VoF? Los árboles B garantizan mayor velocidad que Hashing para el acceso a los datos
F. El Hashing en la mayoria de los casos es acceso directo F(x)=y.
VoF? Las funciones de hashing no poseen funciones inversas.
V. F(x)=y.
VoF? La implementacion de un hash permite obtener a partir de una entrada “x” una salida “y” unica y reversible.
F, no es reversible ni unica en algunos casos
VoF? Si una función de hash no posee una buena dispersión, se van a producir muchas colisiones.
V
VoF? Nunca es posible ejecutar la operación de insert sobre una vista.
F, depende de como fue creada la vista y que campos involucra el insert.
VoF? Si un árbol está balanceado entonces está completo.
F, para que este completo tiene que tener todas las hojas al mismo nivel, para balanceado puede ser <=1 la diferencia.
VoF? Un árbol binario con cuatro nodos nunca puede ser completo.
V. Un árbol binario completo de altura h ≥ 0 contiene al menos 2^h nodos y a lo sumo 2^(h+1) −1 nodos.
VoF? El método de compresión de Huffman es sin pérdida, por eso es recomendable para compactar Imagenes o video.
Falso, no sirve para compactara imágenes o vídeos.
VoF? Un vector es una representation computacional estatica que puede almacenar un arbol.
V
VoF? En un árbol de expresión los nodos maximales siempre son los operadores.
F. Los nodos maximales son las hojas. Y en un árbol de expresión, las hojas son los operandos, no los operadores.
VoF? Si un árbol esta balanceado entonces está completo.
F. Porque puede tener un “hueco” y no sería completo.
VoF? Un árbol de expresión siempre es completo.
F. De hecho El ejemplo de Arbol de Expresion del apunte de Arboles no es completo: a/b + (c-d)e
Restricciones sobre las views.
- No se pueden crear índices en las views.
- Algunas views tienen restringido los: inserts, deletes, updates.
- Aquellas que tengan joins.
- No es posible adicionar a una view las cláusulas de: order by y union.
Algoritmo de Warshall, uso del algoritmo.
- Para conocer la cantidad de pasos distintos de igual longitud hay entre dos nodos.
- Para saber la longitud de paso mínima entre dos nodos.
Algoritmo de Siklossy - Definición y característica.
El algoritmo de Sikloosy presenta la posibilidad de minimizar el espacio ocupado, utilizando un único campo link, sin aumentar el tiempo de acceso, mediante el or exclusivo.
Para evitar el doble linkeo, Sikloosy propone almacenar en un mismo campo de dirección un valor que permita recorrer la estructura en ambos sentidos basandose en la suma del or exclusivo.
Carasterística:
- complejidad espacial.
Recorre la lista en ambos sentidos.
Sort topológico. Definición y procedimiento.
Definición: El sort topológico es el proceso de convertir un conjunto de precedencias en una lista lineal simple, en la cuál ningún elemento posterior precede a uno anterior.
Para comenzar el algoritmo, se obtienen los minimales.
Al grafo resultante de la eliminación de los nodos minimales con sus respectivas relaciones, se aplica nuevamente el algoritmo de obtener los minimales
Y así sucesivamente.
Representación pfaltz - Definición de LEDGE.
LEDGE: Puntero con la dirección de la primer celda de tipo ARCO de una lista de arcos que llegan al nodo.
Representación pfaltz - Definición de REDGE.
REDGE: Puntero con la dirección de la primer celda de tipo ARCO de una lista de arcos que parten del nodo
Representación pfaltz - Definición de LPOINT.
LPOINT: Puntero con la dirección de la celda de tipo NODO de la cual parte el arco.
Representación pfaltz - Definición de RPOINT.
RPOINT: Puntero con la dirección de la celda de tipo NODO de la cual llega el arco.
Representación de Knuth - Estructura del registro.
Leftlink (puntero al padre)
ID
Funciones de asignación
Rightlink ( puntero al primer hijo ) Next RightLink ( puntero al próximo hermano )
Algoritmo de Huffman - Inconvenientes que originan el uso del algoritmo.
- Insuficiente cantidad de espacio en discos
2. Tiempos de transmisión prolongados y costos elevados.
Algoritmo de Huffman - Estructura del nodo.
Padre
Frecuencia
ID
Hijo izq Hijo der.
Chaining.
Consiste en enlazar entre si los distintos pares de clave/puntero que colisionen entre sí, de forma tal de agruparlos. El encadenamiento puede darse en forma interna dentro de la misma tabla de hash, o también utilizando algún tipo de estructura auxiliar.
Hashing into buckets.
Este proceso, basado en el concepto de las estructuras dinámicas, permite resolver el problema de las colisiones a través de listas linkeadas que agrupan los registros cuyas claves randomizadas generan la misma dirección. Básicamente el proceso tiene como estructuras de datos una tabla principal (área base) y una lista linkeada (área overflow).
Árbol B - Definición de Split.
Un split puede producirse en el momento de dar de altas claves en un árbol B.
Al momento de querer dar de alta una clave en un Nodo maximal, si el mismo se encuentra lleno, se deberá partir el nodo maximal en dos nodos maximales.
Puede suceder que dicho nodo se encuentre lleno o que llegue a su % de llenado (Load factor), en dicho caso se debe realizar un split en el nodo.
Es conveniente minimizar la probabilidad de ocurrencia de splits en un árbol B. Para ello se utiliza el Load Factor en la Carga Inicial del Árbol B.
Árbol B - Definición de Factor de carga.
El load factor es un porcentaje de carga de los nodos del Árbol B, el cual se aplica sólo en el proceso de carga inicial del Árbol B.
El Load factor puede variar dependiendo de las claves a insertar o del tipo de archivo o tabla asociada a dicho Árbol B.
Definión de complejidad computacional.
Tiempo de procesador utilizado.
Árbol B qué tipo de árbol es?
Es un árbol n-ario.
Definición de colisión.
Se da cuando al aplicar una función hash da como resultado una posición del vector ocupado.
Enumere y explique al menos tres algoritmos de clasificación que conozca
MergeSort, HeapSort, QuickSort.
El MergeSort es un algoritmo que se basa en la premisa “divide y venceras”, lo que es es dividir el array de valores en dos, de forma recursiva, hasta que los elementos queden en un array solos. Luego los va comparando a los grupos que fueron dividiendo, y va ordendandolos subiendo por cada array superior que habia divido anteriormente. Cuando se llegue al array principal, se obtendrá ordenado
El Heapsort se basa en los monticulos binarios, lo que hace es generar un arbol binario y luego va recorriendo cada una de los subarboles hasta el arbol principal, verificando que la raiz sea mayor que las hojas, Cuando se obtiene el mayor valor en la raiz principal, se saca dicho valor y se coloca ultimo en el array de ordenados. En dicha raiz que se saco el valor se coloca la última hoja del arbol y se repite el procedimiento
El Quicksort consta de un pivote y dos punteros, uno izquierdo que se recorre hacia la derecha, y otro derecho que se recorre hacia la izquierda. Se compara el pivote con el array derecho hasta que este valor sea menor que el valor al cual apunta el ptr derecho, en ese momento se intercambia y luego pasa a moverse el puntero izquierdo de la misma forma hasta que el valor sea mayor que el pivote. Cuando los dos punteros apuntan al mismo lugar significa que todo los valores a la derecha están ordenado. Se repite el procedimiento tomando otro pivote (siempre entre los punteros), por ahora el puntero derecho va a estar en el valor que termino apuntando anteriormente.
Desarrolle el concepto de estrella en datawarehouse.
DW es un almacén de información proveniente tanto de sistemas internos o externos con la información desnormalizada. La idea es explotar dicha info por medio del datamining, para obtener indicadores que luego se utilizarán para la toma de deciciones. El DW esta orientado a sujetos, es variante en el tiempo, no es volatil, y es simple de usar.
Hay tres modelos de construccion, que son el MOLAP (multidimensional), ROLAP (relacional), HOLAP (Hibrido).
La idea del Datawarehouse es tener una carga de datos, y hacer consultas, por lo que hace que sea más simple, pero el volumen de datos, al estar desnormalizado, genera un costo ocupacional muy grande, aunque un costo de procesamiento menor. De todos modos las consultas son mucho más lentas que en una DB operacional debido al volumen de datos que maneja..
Enumere y explique al menos dos algoritmos de ordenamiento y clasificación.
Dos alogritmos de ordenamiento pueden ser el heapsort y el quicksort. y dos métodos de clasificación son la clasificación externa y la clasificación interna
El Heapsort es un algoritmo de ordenamiento donde se va llevando a las raices el mayor valor entre sus hijos, aprovechando los monitculos binarios. Haciendo esto desde abajo hacia arriba, se va a obtener el mayor valor en la raiz, el cual podremos quitarlo y ponerlo en el array ordenado. En reemplazo de este valor quitado anteriormente, se pondrá el último nodo del árbol en la raiz. Se repite el mismo proceso de busqueda de mayores entre raices y sus hijos hasta completar el array ordenado. Tiene una complejidad computacional de O(n log n) para el mejor caso, para el caso promedio y para el peor caso
En el quicksort se toma un pivote, y se tienen dos punteros, uno izquierdo, que recorre de izquierda a derecha el array, y uno derecho que recorre de derecha a izquierda el array. Se compara el pivote con el ptr derecho, y en caso de ser menor o igual, se intercambian, y se mueve el ptr derecho una posicion, empezando a mover el ptr izquierdo. Se compara el ptr izquierdo con el pivote y se va moviendo de a una posicion hasta encontrar un valor que sea mayor, donde se intercambia con el ptr derecho, y ahora se pasa a mover el ptr derecho. Así hasta que se junten los ptr, donde se intercambia el piviote seleccionado por dicha posicion. En el Mejor de los casos, y en el caso promedio, su complejidad computacional es de O(n log n), pero en el peor de los casos es O(n2). De todos modos es el caso más eficiente para la mayoria de los casos.
Clasificación Interna se refiere a que el archivo a ordenar esta complemente en memoria, por lo que se puede acceder a la información de forma facil y aleatorea.
Clasificación externa se refiere a que el archivo a ordenar se encuentra en un disco de almacenamiento, por lo que genera el acceso a los datos de forma secuencial.
Definición de Staging Area.
Unárea destage(se puede traducir como área depruebaso área deensayo), también llamadazona
delanding(zona deaterrizaje), es un área intermedia de almacenamiento de datos utilizada para el
procesamiento de los mismos durante procesos deextracción, transformación y carga (ETL). Esta área
se encuentra entre la fuente de los datos y su destino, que a menudo sonalmacenes de datos,data
martsu otros repositorios de datos.
Las zonasstagepueden proporcionar beneficios diversos, pero la principal motivación para su uso es
aumentar la eficiencia de los procesosETL, garantizar la integridad de los datos y apoyar ciertas
operaciones que aseguren la calidad de los mismos.
VoF? Un modelo OLAP solo puede ser implementado en una DB Multidimensional.
F, Si esta implementada en una DB Multidimencional se llama MOLAP, pero también se puede implementar en DB relacionales que se llaman ROLAP, o hacer casos híbridos que se llaman HOLAP.
VoF? Si una columna posee la constraint de UNIQUE, entonces ninguna fila acepta NULOS en dicha columna.
F. Únicamente una sola fila va a aceptar NULL en el campo que tiene aplicado dicha contraint.
VoF? Las claves alternas (o alternativas), son posibles claves foráneas que pertenecen al conjunto de las claves candidatas.
F. Las claves candidatas son posibles claves primarias, pero cuando no son primarias, se llaman alternas o alternativas.
VoF? Si en una tabla un atributo tiene una Contraint de UNIQUE, no puede tener varias filas con valores nulos correspondiente a dicho atributo.
V. Como tiene la contraint UNIQUE, sólo puede tener UNA fila con el valor NULL en el campo que se aplicó dicha restricción.
VoF? Si una columna posee una constraint UNIQUE, entonces una sola fila cómo máximo puede contener NULL en dicha columna.
V. NULL es el único valor NULO que puede tener toda la tabla para esa columna.
VoF? La ejecución de una query sin filas de resultado dentro de un trigger genera la cancelación de la transacción.
F. No necesariamente. Si haces un BEFORE, se va a ejecutar el trigger independientemente del resultado. al igual que el AFTER.
VoF? Una subconsulta ubicada en un WHERE siempre debe retornar al menos una fila.
F. Si no retorna filas se lo toma como un NULL, y se puede hacer alguna operación de comparación.
VoF? Dada una tabla que tiene un trigger de INSERT; Si al insertar una fila sin ninguna transacción iniciada en la tabla, la acción disparada por el trigger falla, el insert de la fila no se inserta en la tabla. (Quedó medio chota, por eso en el final el profesor aclaró que la afirmación se refiere a que no se insertan datos en la tabla).
V. Si falla el trigger, tambien fallará el insert original.
VoF? La única manera para asegurar unicidad de los campos es con una Primary Key o con UNIQUE.
F. Se podría asegurar la unicidad de los campos por medio de un Trigger, aunque no sería la mejor opción. De todos modos, hace que la premisa sea falsa ya que no sería la única forma.
VoF? La siguiente consulta retorna como máximo 1 fila: SELECT distinct 1 FROM tabla1 WHERE campo1 = 1 UNION all SELECT distinct 1 FROM tabla1 WHERE campo2 = 2.
F. Por el hecho de poner SELECT … 1, hace que siempre retorne UNA fila en caso de cumplirse la o las condiciones del WHERE, pero por el hecho de hacer un UNION ALL, hace que los resultados por separado de los SELECT se unan, haciendo que retorne como máximo dos filas. El DISTINCT lo que hace es filtrar los resultados repetidos de cada subconsulta, que en este caso no hace nada, pero no aplica en la UNION de las dos consultas.
VoF? La ejecución sin filas de resultado de una query dentro de un trigger siempre genera la cancelación de la transacción.
F. La transacción no depende del resultado del trigger, sino que se ejecuta independientemente de la misma, debido al evento obtenido.
VoF? Si existe un select dentro de una cláusula HAVING, este debe devolver 1 fila y 1 columna.
F. El Having se usa para hacer condiciones con funciones agregadas (por ejemplo el COUNT). Entonces, podrías hacer una consulta ya filtrada y agrupada y decir “HAVING COUNT(campo) > 10)”, por lo que devolverá TODOS los campos que cumplan dicha condición, que pueden ser más de uno, independientemente de la cantidad de columnas.
VoF? Si se desea que no se puedan eliminar registros de una tabla de auditoría, una opción es crear un trigger que lo impida.
V. Es una opción rebuscada, pero cierta, dado que podes hacer un INSTEAD OF en el momento que se genere el evento DELETE sobre la tabla de auditoría.
VoF? Si se desea ocultar columnas de una tabla a una aplicación el mejor objeto de DB que podemos usar es un sinónimo.
F. El mejor objeto que se puede usar para ocultar una tabla a una aplicación es la VIEWS, dado que encapsula consultas de una o más tablas y las muestra de tal manera que la aplicación puede aprovecharlo mejor.
VoF? Las siguientes consultas nunca dan el mismo resultado a excepción que la primer consulta no devuelva filas:
◦ SELECT 1 FROM tl_tablita WHERE campo1 = 1 OR campo2 = 2
◦ SELECT 1 FROM tl_tablita WHERE campo1 = 1 UNION SELECT 1 FROM tl_tablita WHERE campo2 = 2.
F. La primer consulta, al tener en el WHERE el OR. Hace que en caso de que se cumpla una u otra, devuelva un 1, por cada condición cumplida y por el SELECT 1. En la segunda consulta, por tener el WHERE del campo1 y el UNION con el WHERE del campo2, hace que siempre devuelva devuelva una row por cada vez que se cumple la condición de cada subconsulta y las une, generando 2 filas. Pudiendo hacer que devuelvan el mismo resultado.
VoF? Siempre es conveniente tener una tabla indexada por su primary key.
F. No siempre. Los índices son ventajosos en las columnas que se usan para hacer JOIN, WHEREs y ORDER BY, que no necesariamente son las que tienen la constraint PRIMARY KEY.
VoF? Una constraint es más eficiente que un trigger para validar el dominio de un atributo.
V. Dado que el trigger se ejecuta ante la aparición de un evento, esto genera un overhead que no genera la constraint.
VoF? Se puede ejecutar un store procedure en una consulta SELECT.
F. Para ejecutar un STORE PROCEDURE, es necesario hacer un EXEC, cosa que no es posible.
VoF? No se pueden crear índices en las vistas.
V. Por más que algunos motores de DB permite crear índices sobre las VIEWS, como el MSSQL, los indices son al modelo físico, las vistas no son físicas. Por ende la premisa es Verdadero, y no se pueden crear índices sobre las vistas.
VoF? Luego de ejecutar la siguiente sentencia DDL:
CREATE TABLE tablitaFinal (campo1 VARCHAR2(5), campo2 VARCHAR2(5))
Y poblar la tabla; la siguiente igualdad se da para cualquier set de datos posibles:
SELECT COUNT(campo1) from tablitaFinal = SELECT COUNT(campo2) from tablitaFinal.
F. El count sobre un campo de la tabla, cuenta los valores NO NULOS, por ende, si ponés valores nulos en el campo 2, y valores no nulos en el campo1, o viseversa, el valor del count va a cambiar.
Defina el concepto de Transacción. Cite un ejemplo cuando el motor de base de
datos ejecutaría un rollback en una transacción abierta.
Conjunto de operaciones que se ejecutan atomicamente, o sea que se hacen todas o ninguna. En caso de fallar una operacion, se hace un rollback volviendo al estado original.
Un rollback se puede dar ante una falla, por ejemplo no encontrar un PK, o perdida de conectividad.
Para qué utilizarías conceptualmente una vista y un snapshot y diferencias principales entre esos objetos.
Un Snapshot es una vista materializada, es una estructura el cual se guarda fisicamente los valores obtenidos en las consultas, por lo que si las tablas originales modifican dichos valores o agregan o eliminan, el snapshot no va a cambiar, quedando desactualizado.
Las vistas son un objeto de DB que encapsula una consulta, de una o más tablas, no quedan fisicamente guardados los datos, por lo que si actualizan la info de las tablas involucradas, las vistas estarán actualizadas.
Defina el concepto de lectura sucia, no repetible y fantasma.
Lectura sucia: Se da cuando una transacción A modifica un valor, y luego una transacción B, lee dicho valor, pero la transacción A falló, y no commiteó el valor, por ende se rollbackea, quedando la transacción B con un valor sucio.
Lectura no repetible: Se da cuando una transacción A lee un valor, luego una transacción B modifica dicho valor, y la transacción A vuelve a leer el mismo valor, va a ser diferente, no se va a repetir.
Lectura fantasma: Es una anomalia de la lectura no repetible. Se da cuando una transacción A lee un rango de valores y una transacción B inserta valores, la transacción A va a leer los valores insertados por B, pero si este no commitea, se va a rollbackear, por lo que la transacción A va a quedar con elementos que ya no se encuentran en la tabla .
Qué es un DataMart. Explique por qué motivo posee datos denormalizados.
Un DM es un subconjunto de un DW, donde la información se relaciona con un area de negocio. Los datos están desnormalizados para poder hacer más rápidas las consultas, lo que genera un costo ocupacional alto debido a la redundancia de datos.
Si tuviera que elegir un método de creación de índices, entre Hashing y Árbol-B, cuándo usaría cada uno de ellos y por qué.
En caso de tener consultas secuenciales por rangos, utilizaria B tree, debido a que es más óptimo para cargar, dado que mantiene un ordenamiento.
En caso de tener consultas con accesos directos a los datos, utilizaría Hashing, dado que es más optimo para dicho propósito.
Explicar los conceptos de ETL y Staging Area en un Datawarehouse.
ETL: Extraer, transformar y cargar. Es el proceso por el cual los datos se extraen de sus DB originales, se transforman para poder ser cargados en la DB. Esto se da en el staging area.
Staging Area: Es un lugar donde se almacenan los datos previos a los datos del datawarehose, donde se filtra la información sensible y se depura, para luego pasarla al DW.
Explique los conceptos de Fact Table y Dimension Table en DW.
Fact Table (Tabla de hechos): Es una tabla que representa una relación muchos a muchos y contiene un conjunto de dos o mas FK que hacen referencias a las tablas de dimensión. Es la tabla primaria orientada a obtener medidas del negocio Dimension Table (Tabla de dimensión): Restringe los criterios de selecci on de los datos de la fact table. Cada tabla contiene una PK que siver de integridad referencial con la fact table y que hace joins con la fact table. Muchas tablas de dimensión contienen atributos textuales que son la base para restringir y agrupar consultas sobre el DW. Dependiendo de cómo se organice el DW, una tabla de dimensión puede almacenar información de uno o mas atributos relacionados (Puede estar normalizado o desnormalizado dependiendo del modelo copo de nieve o star).
Describa los diferentes conceptos que se relacionan directamente con la funcionalidad de concurrencia
ACID: Dado que las transacciones son un conjunto de operaciones que se ejecutan de manera atómica, puede pasar que ambas transacciones escriban y lean concurrentemente un mismo valor. Por ende una DB debe garantizar la Atomicidad, Consistencia, Aislamiento (Isolation) y Durabilidad de sus transacciones.
El Aislamiento se puede configurar, y consta de 4 niveles. Cada nivel genera más o menos bloqueos para poder manejar las lecturas sucias, lecturas no repetibles y lecturas fantasma. Los niveles de aislamiento son READ UNCOMMITED, READ COMMITED, REPEATABLE READ, SERIALIZABLE.
ACID: Dado que las transacciones son un conjunto de operaciones que se ejecutan de manera atómica, puede pasar que ambas transacciones escriban y lean concurrentemente un mismo valor. Por ende una DB debe garantizar la Atomicidad, Consistencia, Aislamiento (Isolation) y Durabilidad de sus transacciones.
El Aislamiento se puede configurar, y consta de 4 niveles. Cada nivel genera más o menos bloqueos para poder manejar las lecturas sucias, lecturas no repetibles y lecturas fantasma. Los niveles de aislamiento son READ UNCOMMITED, READ COMMITED, REPEATABLE READ, SERIALIZABLE.
Se puede implementar por medio de los Databases Links, el cual provee el acceso a las tablas de bases de datos remotas.
Determinar qué recursos brindan en líneas generales los motores de base de datos para optimizar la performance de las querys.
Los motores de DB brindan índices que permiten optimizar la performance de las query que tienen JOINs, WHEREs, y ORDER BY. Tambien proveen vistas el cual se genera un plan de ejecución para la optimización de las querys.
En qué consiste el Data Mining y en qué se utiliza.
Data mining es una técnica de explotación de grandes volúmenes de datos con el fin de conseguir indicadores técnicos para la toma de decisiones. Algunos algoritmos utilizados son los algoritmos genéticos, redes neuronales, arboles de desición, entre otros. Se utiliza en los Datawarehouses.
Relacione y explique los conceptos de Transacción, Lockeos y Aislamiento.
Una transacción es un conjunto de operaciones que se hacen de manera atómica. Esto quiere decir que se hace todas o ninguna de las operaciones. Cuando se generan transacciones concurrentes, puede pasar que ambas quieran leer y escribir un mismo dato, lo que va a generar algunos problemas conocidos como lecturas sucias, lecturas no repetibles y lecturas fantasmas. Para evitar dichos problemas, se utilizan distintos niveles de ailamiento, que pueden ser READ UNCOMMITED, READ COMMITE, REPETABLE READ y SERIALIZABLE. Cada nivel de aislamiento va a lockear (Bloquear) de diferente manera los datos a acceder según sea el caso.
Explique la arquitectura interna de un Sistema de Base de Datos.
ANSI/SPARC. Consta de 3 niveles, El nivel interno (físico), que se ocupa de la manera que se almacenan los datos físicamente, el nivel conceptual (lógico), que se ocupa que una sola vista agrupe todas siendo mediador entre la capa externa e interna, y el nivel externo(vistas), que se ocupa la forma como los usuarios individuales percibirán los datos.
Cuál es el concepto, la funcionalidad y para qué se utilizan los TRIGGERS en una Base de Datos relacional.
Un Trigger es un objeto de DB, que se attacha (o ancla) a un evento de determinada tabla, el cual ejecuta ciertas operaciones (tambien puede ejecutar store procedures).
Ante algun evento de tipo INSERT, UPDATE, o DELETE, puede ejecutarse el trigger de modo BEFORE (antes), AFTER(despues), FOR EACH ROW (por cada fila), INSTEAD OF (en vez de), entre otras.
Se puede utilizar para hacer logs de auditorías, chequeos a nivel reglas de negocio, agregar seguridad, etc.
Indicar que hace que un DBMS sea transaccional.
Un DBMS es transaccional cuando la información está normalizada, se hacen muchas operaciones sobre la misma, la información de la DB es relativamente pequeña y específica. Los datos son volátiles dado que cambia todo el tiempo. Se manejan cientos de transacciones diarias, etc.
Explique que es una transacción en un Sistema de Base de Datos.
Una transacción es un conjunto de operaciones que se ejecutan como una unidad. Deben cumplir con la siga ACID (Aislamiento, Consistencia, Isolation, Durabilidad).
Explique la relación existente entre las vistas, los triggers y la funcionalidad de seguridad para un motor de base de datos
Las vistas y los triggers son objetos de base de datos que sirven, entre otras cosas para añadir seguridad a la DB. Las vistas encapsulan consultas de una o más tablas, lo que hace que se esconda la estructura real de las tablas y hasta se le pueden cambiar los nombres, por eso en caso de ataques de seguridad (por ejemplo, SQL INJECTION), puede prevenir que se obtenga información específica de las tablas involucradas.
Los triggers se attachan ante un evento y ejecutan operaciones o procedimientos cuando dicho evento ocurre. Se puede usar para seguridad dado que podes Auditar los cambios sobre una tabla o cambiar la acción proveniente de dicho evento, por ejemplo, si se hace un DELETE, podes hacer un trigger que haga un INSTEAD OF, y no haga dicho delete, solo audite que X usuario hizo un delete sobre Y tabla.
¿En qué consiste el Data Mining? Para qué se utiliza e indique algunas técnicas aplicadas en el mismo.
Consiste en la extracción de información de grandes bases de datos para la toma de decisiones ya que predicen futuras tendencias y comportamientos. Algunas técnicas aplicadas son redes neuronales, algoritmos genéticos, árboles de decisión.
Defina concepto, funcionamiento, variantes y modo de ejecución de los TRIGGERS.
Un Trigger es un objeto de DB que se attacha a un evento (INSERT, UPDATE, DELETE), para luego ejecutar operaciones. La forma (o el modo) en que se ejecutan dichas operaciones (y tambien ejecutar Store Procedures) ante el evento ocurrido pueden ser configuradas, entre ellas pueden ser BEFORE (que se ejecuta antes de que se haga la operacion, util para hacer algún checkeo), AFTER (que se ejecuta luego de que se haga la operación original, util para hacer log de auditoria), FOR EACH ROW(se ejecuta en cada una de las filas, util para hacer algun checkeo por cada fila), INSTEAD OF (Cambia la operación original por la que le digas, util para manejar los datos de forma distinta).
¿Cuáles son las características diferenciales de un DW respecto a un modelo transaccional tradicional?
Un DW es un almacén de datos donde la información se encuentra desnormalizada y proviene de uno o más sistemas (internos o externos) con el fin de tomar deciciones mediante indicadores encontrados por la explotación de dichos datos (datamining). A diferencia de un DB operacional que se dedica al cambio constante de la información que maneja, el DW en general solo se insertan los datos y se le hacen consultas, en cambio la DB operacional tiene un cambio constante de los datos. El DW es conveniente que tenga la información desnormalizada para obtener consultas más velozmente, mientras que la DB operacional es conveniente la normalización de los datos. el DW maneja tiempos de consultas mucho más altas que la DB operacional. el DW, al tener la info desnormalizada, ocupa muchisimo más espacio que la DB operacional.
Describa el objeto TRIGGER y 4 casos posibles de utilización
Un Trigger es una acción hookeada a un evento, que se disparará justamente cuando ocurra dicho evento. Los eventos pueden ser INSERT, UPDATE, DELETE, y ante dichas acciones se puede anclar el trigger para que trabaje de distintas formas, por ejemplo, BEFORE (antes), AFTER(después), FOR EACH ROW(por cada fila), INSTEAD OF(en vez de), y luego hacer algún conjunto de operaciones o ejecutar algún procedure.
Los posibles casos de utilización de un TRIGGER (entre otros) pueden para:
Logs de auditoría
DELETE en cascada
Seguridad en el manejo de ciertos datos
Chequeos como si fueran constraints (Por ejemplo unicidad, aunque es conveniente usar constraint UNIQUE).
Defina claramente el concepto y cuando implementaría una función (function), un procedimiento (store procedure) y/o disparador (trigger).
Una función es un conjunto de operaciones que aceptan parámetros de entrada y devuelve un resultado como salida. Una limitación es que no tiene efecto colateral, o sea no puede modificar la DB, solo puede consultarla. La implementaría cuando necesito hacer una operación sobre alguna consulta de una tabla o como una constraint que haga ciertas validaciones.
Un procedimiento es un conjunto de operaciones que aceptan parámetros de entrada y no devuelven resultado de salida. Los procedimientos no son llamados, sino que son ejecutados y no se pueden usar en consultas o contraints. Lo utilizaría para hacer operaciones complejas sobre la DB
Un Trigger es un conjunto de operaciones que se disparan al momento de que algún evento ocurra. Dicho evento puede ser un INSERT, DELETE o UPDATE. No tienen parámetros de entrada y no se devuelve un resultado. Pueden ejecutar procedimientos, por lo que puede tener efecto de lado. Lo utilizaría para hacer DELETE en casacada o logs de auditoria.
En qué consiste la integridad relacional y de qué formas puede implementarse sobre un DBMS.
La integridad referencial es usada para asegurar coherencia entre los datos. Se puede implementar por medio de las constraints PRIMARY KEY y FOREIGN KEY.
Defina conceptos de DW y DM, y su utilización.
DW es un almacén de datos donde la información se almacena de forma desnormalizada, pudiendo ser la misma del propio sistema o de sistemas externos. Sirve para el análisis por medio del datamining y así tomar decisiones en base a la obtención de ciertos indicadores. El DM (DataMart) es un componente específico de un DW orientado a un área específica de la empresa, pero tiene un alcance mucho más limitado por la información que maneja (es un subconjunto de DW). Generalmente son DB Multidimencional, a diferencia del DW que se usan DB relacional.
Describir lo que es un Datawarehouse. Indicar qué papel juega la desnormalización en el mismo.
Datawarehouse es un almacén de información donde la misma se guarda de forma desnormalizada. La información proviene de distintas partes de un sistema e incluso desde sistemas externos. La idea es poder explotar la información mediante el datamining y de esta forma obtener indicadores para la toma de decisiones. Los diferentes modelos de construcción son MOLAP (multidimensional), ROLAP (relacional), HOLAP (Hibridos).
Los DW son:
orientados a sujetos: clientes, vendedores, actividades, etc
integradas: la forma de exponer la info de sexo puede ser m o f, pero también 0 o 1, etc,
variantes en el tiempo: se hacen de un histórico y no se hacen updates. Sirven a futuro
simples de utilizar: Como unicamente ocurren dos operaciones, que son carga inicial y consulta, no hay mayores inconvenientes. Simples para hacer backups
no volátiles: la información útil es únicamente cuando es estable.
Al ser una base de datos desnormalizada, hace que se obtenga rápido acceso y se obtengan consultas velozmente, dado que no es necesario hacer joins y recalcular datos en cada acceso, pero genera un costo ocupacional muy alto debido a la redundancia de datos.
Indica que es un plan de ejecución y cual es su finalidad.
Un plan de ejecución es el conjuntos de pasos que el motor de base de datos va a ejecutar para llevar a cabo la consulta. La finalidad es poder optimizar la consulta para que sea lo más performante posible.
¿Cuál es el objetivo de usar índices? Describa un ejemplo práctico de un índice compuesto.
El objetivo de crear índices es permitir el acceso más rápido a una tabla y generar unicidad de los campos. Un ejempo sería crear un indice entre los campos customer_number, last_name, first_name lo que mejoraría la performance de los JOIN, WHERE y ORDER BY de la tabla con dichos campos involucrados.
Describir el algoritmo de HeapSort
Genera un árbol binario aprovechando los mónticulos binarios, y va recorriendo dicho arbol desde las hojas hasta la raiz, comparando los valores de las hojas con la raiz de cada subarbol. Si las hojas son mayores que la raiz, entonces intercambia dichos nodos. Hace esto de forma recursiva hasta obtener el mayor valor en la raiz del arbol principal, para luego sacar dicho nodo y ponerlo como último elemento del array ordenado. En reemplazo de este nodo sacado, se pone el último nodo hoja en la raiz. Se repiten estos pasos hasta obtener el array ordenado.
Desarrolle el concepto de TRIGGER en un DBMS. Explique cuándo lo utilizaría y Por qué.
Mecanismo que ejecuta una sentencia SQL cuando algún evento ocurre. Dicho evento puede ser INSERT, UPDATE (único evento en que se puede hacer referencia a la columna), DELETE; y la acción a ejecutar puede ser un INSERT, UPDATE, DELETE, un Store Procedure o un código procedural. Los triggers se pueden ejecutar en diferentes momentos, como ser BEFORE, AFTER, INSTEAD OF, FOR EACH ROW.
Un ejemplo de cuándo usarlo es para los DELETE en cascada, dado que si existen claves foraneas, dicha contraint obliga a primero eliminar las claves foraneas antes de eliminar la fila que contiene dicha clave, por ende con un trigger se puede hacer que primero elimine dicha clave foranea antes de eliminar la fila.
Objetos que se usan para asegurar integridad.
Los objetos que se usan para mantener la integridad de entidad son las restricciones PRIMARY KEY o la
combinación de NOT NULL + UNIQUE o el uso de TRIGGERs.
Los objetos que se usan para mantener la integridad de referencia son las restricciones FOREIGN KEY o
el uso de TRIGGERs.
Los objetos que se usan para mantener la integridad de semántica son las restricciones NOT NULL,
DEFAULT, CHECK, UNIQUE o TRIGGERs. También se podría pensar que limitar el acceso a las tablas de
la BD mediante procedimientos almacenados, podría brindar integridad de semántica.
Plan de Ejecución de un SELECT.
Antes de ejecutar una consulta, el motor de base de datos la optimiza. El resultado de esa optimización es lo que se conoce como plan de ejecución. Las decisiones que toma el motor para optimizar incluyen: qué algoritmo de join usar, qué algoritmo de ordenamiento usar, qué algoritmo de agrupación usar o si recorrer la tabla de forma secuencial o usando índices. Todas estas decisiones mejoran la performance de la consulta. Por ejemplo, no es lo mismo utilizar un algoritmo de join especializado para tablas de tamaño pequeño que usarlo para tablas de tamaño mayor.
Tipos de JOIN.
- INNER JOIN (unión simple): devuelve todas las filas cuando hay al menos una coincidencia en AMBAS tablas.
- LEFT JOIN: devuelve todas las filas de la tabla de la izquierda y las filas coincidentes de la tabla de la derecha.
- RIGHT JOIN: devuelve todas las filas de la tabla derecha y las filas coincidentes de la tabla izquierda.
- FULL JOIN: devuelve todas las filas cuando hay una coincidencia en UNA de las tablas.
Definición de ETL.
Extract, Transform and Load(«extraer, transformar y cargar») es el proceso que permite a las organizaciones mover datos desde múltiples fuentes, reformatearlos y limpiarlos, y cargarlos en otrabase de datos,data mart, odata warehousepara analizar, o en otro sistema operacional para apoyar unproceso de negocio.
¿Por qué se establece que las Reglas del Negocio deben estar en el Motor de Base de Datos y no en la aplicación cliente?
- Reglas de negocio: cada aplicación debe reflejar las restricciones que existen en el negocio dado, de modo que nunca sea posible realizar acciones no válidas.
- La información puede ser manipulada por muchos programas distintos que podrán variar de acuerdo a los departamentos de la organización, los cuales tendrán distintas visiones y necesidades pero que en cualquier caso, siempre deberán respetar las reglas de negocio.
- Es por lo anterior expuesto que las reglas del negocio deben estar en el motor de base de datos.
¿En qué consisten, para qué se utilizan y cómo pueden implementarse las tecnologías OLAP? Ejemplifique.
- Proporciona información fiable sobre los indicadores clave del funcionamiento de una organización para los sectores que toman decisiones.
- A diferencia de los sistemas transaccionales, OLAP procesa información y aplica inteligencia.
- Un sistema OLAP se alimenta de uno o varios OLTP que lo proveen de datos.
- Todos los campos son calculados.
- Se usa para tomar decisiones.
- Se basa en patrones de interés.
- OLTP DTS OLAP. El DTS se ejecuta periódicamente para generar información.
- Se implementa con distintas tecnologías: MOLAP (bases de datos multidimensionales), ROLAP (bases de datos relacionales), HOLAP (bases de datos híbridas).
- MOLAP: ya no se trabaja con el concepto de filas y columnas sino dimensiones. Técnicas de hipercubo (hay dispersión) y multicubo (se saltan los cubos que no contienen información).
- ROLAP:
Explique el Modelo Star para el armado de una DataWarehouse. Ejemplifique.
- Es un esquema relacional orientado a la representación de dimensiones que convergen sobre un hecho común o un valor cuantificable.
- De esta forma se logra implementar en un sistema de base de datos tradicional el concepto de cubos multidimensionales.
- Existe una tabla central denominada “tabla de hechos” que representa el atributo cuantificable.
- Alrededor de esta tabla central se definen otras tablas ligadas a esta mediante claves foráneas, y se denominan tablas de dimensiones y son aquellas que definen cualidades del atributo representado por la tabla de hechos.
- La clave primaria de la tabla de hechos será una clave compuesta por todas las claves foráneas que representan las claves primarias de cada una de las dimensiones asociadas.
Enumere y explique al menos 3 algoritmos de clasificación que conozca.
- Dicotómico o burbuja: funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado. Es necesario revisar varias veces la lista hasta que no se necesiten más intercambios, lo cual significa que la lista está ordenada.
- Quicksort: elegir un elemento de la lista a ordenar (pivote). Resituar los demás elementos de la lista a cada lado del pivote, de un lado los menores y del otro los mayores (en este momento el pivote está ordenado). Se repite el proceso de forma recursiva para las dos sublistas mientras éstas contengan más de un elemento. Una vez terminado el proceso todos los elementos estarán ordenados. Eficiencia promedio nxlog(n); en el peor de los casos n2.
- Heapsort: el algoritmo consiste en almacenar todos los elementos del vector a ordenar en un montículo (heap), y luego extraer el nodo que queda como nodo raíz del montículo (cima) en sucesivas iteraciones obteniendo el conjunto ordenado. Basa su funcionamiento en una propiedad de los montículos por la cual la cima contiene siempre el menor elemento (o el mayor, según se haya definido) de todos los elementos almacenados en él.
Enumere ventajas, desventajas y diferencias entre una Base de Datos Orientada a Objetos y una Base de Datos Relacional.
Ventajas BDOO:
• Simplifica la programación.
• Flexibilidad: uso de sub-clases que permiten la herencia de atributos, esto permite que una BDOO puede ajustarse a usar siempre el espacio de los campos que son necesarios, eliminando el espacio desperdiciado en registros con campos que no se usan.
• Manejo de datos complejos: manipula datos complejos de forma rápida y ágil. La estructura de la BDOO está dada por referencias (apuntadores lógicos) entre objetos.
Desventajas BDOO:
• Baja performance.
• Inmadurez del mercado de BDOO.
• Falta de estándares en la industria orientada a objetos.
¿Qué entiende por diccionario de datos, catálogo de datos o metadata?
- Para representar una base de datos relacional, necesitamos almacenar no sólo las relaciones mismas, sino también una cantidad de información adicional acerca de las relaciones.
- El conjunto de tal información se llama diccionario de datos o metainformación.
- El diccionario de datos debe contener información como: nombre de las relaciones en la base de datos; nombre de los atributos de cada relación; dominio de cada atributo; tamaño de cada relación; método de almacenamiento de cada relación; claves y otras restricciones de seguridad; nombres y definiciones de vistas.
- Además debe contener información sobre los usuarios de la base de datos y los poderes que éstos tienen: nombre de los usuarios; costo del uso efectuado por cada usuario; nivel de privilegio de cada usuario.
- Es de notar que el diccionario de datos no es más que una base datos acerca de la base de datos, y puede almacenarse y manejarse con los mismos métodos.
¿Qué beneficios brinda la aplicación de la normalización al diseño de un modelo de base de datos?
- Elimina la redundancia de datos.
* Mejora la performance.
Defina los conceptos de Data Warehouse y Datamart. Especialmente similitudes y diferencias.
- DataWarehouse: YA ESTÁ EXPLICADO.
- DataMart: podemos entender un Data Mart como un subconjunto de los datos del Data Warehouse con el objetivo de responder a un determinado análisis, función o necesidad y con una población de usuarios específica. La diferencia entre un DataWarehouse y un DataMart es que el data mart está pensado para cubrir las necesidades de un grupo de trabajo o de un determinado departamento dentro de la organización. Es el almacén natural para los datos departamentales. En cambio, el ámbito del data warehouse es la organización en su conjunto. Al igual que en un data warehouse, los datos están estructurados en modelos de estrella o copo de nieve y un data mart puede ser dependiente o independiente de un data warehouse. Los orígenes de datos son homogéneos a diferencia del DW.
Describa y cite al menos un ejemplo de una representación computacional que permite representar computacionalmente un grafo irrestricto.
- De manera estática: con una matriz de adyacencia nxn (n: cantidad de nodos del grafo), en donde un 1 en una posición ij representa la existencia de una flecha del nodo i hacia el nodo j. Presenta el problema de ocupar mucho espacio para representar lo que realmente existe ya que se reserva espacio para lugares que no tienen datos.
- De manera dinámica: utilizando una lista o vector de punteros donde se guardan los nodos que participan del grafo con sus correspondientes datos. Cada elemento contiene un puntero a una lista adicional que contiene “las flechas que salen” del nodo que representan. No se guarda el dato en la lista adicional, guarda los punteros a datos.
¿Cuál es la diferencia entre la utilización de Multicubos e Hypercubos para la implementación de bases de datos multidimensionales?
Hipercubos:
• Se guardan todas las dimensiones en un cubo.
• Cada intersección del cubo es otro cubo y así sucesivamente.
• Se pueden agregar dimensiones pero es estático porque no se puede variar la dimensión del cubo.
• Hay dispersión de datos porque los datos no están compactos por el hecho de que puede haber muchos datos vacíos.
Multicubos:
• Se genera una lista con los cubos que tienen información, es decir se saltea los cubos vacíos.
Desde el punto de vista de la performance, ¿en qué consiste el armado de un plan de consulta?
- El optimizador de consultas es el componente del sistema de gestión de base de datos que intenta determinar la forma más eficiente de ejecutar una consulta SQL.
- Se decide cuál de los posibles planes de ejecución de una consulta dada es el más eficiente.
- Los optimizadotes basados en costos asignan un costo (operaciones de E/S requeridas, CPU, etc.) a cada uno de esos planes y se elige el que tiene menor costo.
- El optimizador no puede ser accedido directamente por los usuarios, sino que, una vez enviadas las consultas al servidor, pasan primero por el analizador y recién entonces llegan al optimizador.
- Una consideración muy importante es el orden de los “join”.
Describa los componentes básicos de un DBMS. Teniendo en cuenta la administración de datos, la interfaz con el usuario y el procesamiento cliente-servidor
- Dos lenguajes: DML y DDL.
- 3 capas: externa (usuario), lógica (conceptual) e interna (física).
- Disk manager (recibe peticiones del file manager y las envía al SO), file manager (decide que página contiene el registro deseado y la solicita el disk manager) y user manager (permite la interacción con el usuario).
- Arquitectura cliente-servidor: las aplicaciones corren en el cliente y generan solicitudes para y reciben respuestas del servidor. El servidor realiza el procesamiento de datos y aplica las reglas de negocio establecidas.
- Clustering: es la forma de agrupar la información. Hay dos formas, intra-file clustering (todas las tablas conviven con sus elementos) e inter-file clustering (se guarda cada objeto con sus relaciones).
VoF? Un modelo OLAP, posee al menos una tabla de hechos (FACT TABLE),
con campos precalculados.
Creo que es FALSO porque una implementación ROLAP tiene tabla de
hechos (en el modelo de datos de estrella o copo de nieve) pero en
MOLAP la información se almacena en hipercubos o multicubos y en estos
modelos no se utiliza la tabla de hechos (Según tengo entendido).
VoF? Las técnicas más comunes utilizadas en DATAMINING son las redes
neuronales, los árboles de decisión y las reglas de inducción.
Según el apunte las técnicas mas comúnmente usadas en Data Minig son:
- Redes neuronales o artificiales
- Regresión Lineal
- Árboles de decisión
- Algoritmos genéticos (funcionan con evolución y descarte de los individuos menos capaces de una población según un criterio (generaciones = iteraciones sobre una cadena con la población))
- Método del vecino más cercano
- Reglas de inducción
VoF? Todos los motores de Bases de Datos utilizan el método de Hashing
para el armado de sus índices.
FALSO: también pueden utilizar árboles b
VoF? En un modelo OLAP no es aplicable la normalización de datos.
FALSO: Dentro de los ROLAP, los que utilizan un modelo de copo de
nieve las tablas de dimensión están normalizadas hasta 3FN(creo)
VoF? No es posible obtener el mismo resultado de una consulta OLAP a
partir del OLTP que dio origen al mismo
FALSE. La OLAP tiene la misma información, pero organizada de manera de agilizar las consultas de grandes cantidades de datos.
VoF? En la implementación de un Árbol B, todos los nodos de datos que
contienen claves, se encuentran en el mismo nivel.
VERDADERO: todos los nodos HOJA aparecen en el mismo nivel (y en inserciones o eliminaciones se rebalancea para mantenerse asi).
VoF? Un árbol siempre tiene más punteros que elementos de datos.
FALSO, si un arbol posee los elementos de datos en cada nodo entonces es igual.
VoF? Los árboles B garantizan un número de niveles menor que otros árboles.
Es balanceado, con lo que asegura que sea menor o IGUAL. FALSO
VoF? El método de Árbol B no es aplicable a archivos con gran
volúmenes de datos.
F (es mejor que Hashing, conviene q sea arbol B)
VoF? En un modelo OLAP se puede aplicar normalización en cualquier
tabla que no sea la Tablas de Hechos.
Falso, coincido. Todas las tablas de dimensián (tablas satélites de la/las tabla/s de hecho SIEMPRE están desnormalizadas.
VoF? Las dimensiones en una base de datos multidimensional indican
la forma de acceder a la información que se encuentra en la intersección
de dichas dimensiones.
V
VoF? El checksum es una de las técnicas utilizadas para corroborar la
integridad de los datos.
V
VoF? La técnica de Hash puede generar muchas lecturas secuenciales
para un valor clave hash cuando hay alto grado de repetición de claves de usuario.
V
VoF? Las foreing keys eliminan redundancia de datos.
F, la redundancia las da la normalizacion. Aseguran la integridad referencial.
VoF? Para poder realizar UNION entre dos consultas, las mismas deben tener la misma cantidad de columnas en el mismo orden e igual tipo de dato
por cada una.
V
VoF? Un select con tres tablas en el from consume igual recursos que tres select con una tabla cada una.
F (la unicidad de una consulta hace a la diferencia, 3 consultas consumen MAS).
VoF? Las BDOO persiguen integrar en la misma plataforma el Modelo lógico y físico sin que el paso de uno a otro traiga modificaciones en el Modelo de Datos.
V, permite q no haya alteraciones entre los modelos y reduce el costo de trabajo al programador, osea le simplifica la vida.
VoF? Una vista en un RDBMS permite restringir el acceso a modelo y tener una vista simplificada del mismo.
F. No del modelo, de alguna tabla o mix de tablas.
Aparte no es una simplificación, sino es una sección determinada.
Explicar Clave Primaria, Foránea, Candidata y dominio de los datos.
- Clave Primaria: es un campo o combinación de campos que identifica de forma única a cada fila de la tabla.
- Clave Foránea: identifica una columna o grupo de columnas en una tabla que se refiere a una columna o grupo de columnas en otra tabla.
- Clave Candidata: son claves que podrían servir como clave primaria.
- Dominio de los Datos: un dominio describe un conjunto de posibles valores para cierto atributo.
Explique el concepto de Dimensiones en un Data Warehouse.
Dimensiones en DW: llamamos dimensiones a aquellos datos que nos permiten agrupar o filtrar información. Existe una Dimensión Table que restringe los criterios de selección de la Fact table. Cada dimensión está definida por su clave primaria que sirve como base para la integridad referencial con la fact table.
Determine los componentes y las variables que intervienen en el diseño de un modelo OLAP.
◦ Proporciona información fiable sobre los indicadores clave del funcionamiento de una organización para los sectores que toman decisiones.
◦ A diferencia de los sistemas transaccionales, OLAP procesa información y aplica inteligencia.
◦ Un sistema OLAP se alimenta de uno o varios OLTP que lo proveen de datos.
◦ Todos los campos son calculados.
◦ Se usa para tomar decisiones.
◦ Se basa en patrones de interés.
◦ OLTP → DTS → OLAP. El DTS se ejecuta periódicamente para generar información.
◦ Se implementa con distintas tecnologías: MOLAP (bases de datos multidimensionales), ROLAP (bases de datos relacionales), HOLAP (bases de datos híbridas).
◦ MOLAP: ya no se trabaja con el concepto de filas y columnas sino dimensiones. Técnicas de hipercubo (hay dispersión) y multicubo (se saltan los cubos que no contienen información).
◦ ROLAP
Que características de funcionamiento tiene y que variantes existen del método quicksort de clasificación.
Es un método de fácil implementación y poco consumo de recursos. Es recursivo pero se usan versiones iterativas para mejorar su rendimiento, también es in-situ, ya que usa solo una pila auxiliar.
El QuickSort está basado en la idea de divide y vencerás, en el cual un problema se soluciona dividiéndolo en dos o más subproblemas, resolviendo recursivamente cada uno de ellos para luego juntar sus soluciones para obtener la solución del original.
Indique por que un índice conformado por una clave numérica corta es más rápido en el acceso a los datos que un índice compuesto o conformado con un string largo.
Al ocupar más espacio cada nodo del árbol supera el tamaño de una página del File System, de esta forma el Sistema Operativo debe leer varias páginas para levantar un nodo, por eso es mas lento.
Cual es el objetivo de un Trigger.
Es mantener la integridad referencial entre tablas.
¿Qué características distintivas brinda un DBMS?
Sistema de Administración de Bases de Datos (DBMS): Construido sobre sus capacidades en vez de las simples funciones de recuperación y almacenamiento de datos. Estos productos comúnmente incluyen grandes capacidades de back-up y recuperación de datos, ingreso al sistema, control de concurrencia y bloqueo, y mecanismos de seguridad.
A la hora de elegir un Motor de Bases de Datos determinado, que características tendría que analizar para su elección?
Costo, Volumen de datos, tiempo de respuesta, control de acceso concurrente y seguridad, redundancia y recuperación de datos.
Desde el punto de vista de la Performance, en que mejora el armado de un Modelo OLAP.
OLAP: En el análisis multidimensional, los datos se presentan mediante dimensiones como producto, territorio y cliente. Por lo regular las dimensiones se relacionan en jerarquías, por ejemplo, ciudad, estado, región, país y continente, o estado, territorio y región.
Al procesamiento analítico o análisis multidimensional se le conoce también como procesamiento analítico en línea (OLAP). Se procesa en una visión multidimensional de los datos empresariales en el Data Warehouse y puede tener un motor de depósito de base de datos multidimensional. De esta forma, dentro de un Data Warehouse existen dos tecnologías complementarias, una relacional para consultas y una multidimensional para análisis. Este concepto nace ante la debilidad fundamental de las bases de datos relacionales para proveer capacidad de análisis y sistemas de soporte a las decisiones.
La siguiente definición muestra las mejoras que provee un Modelo Olap:
Fast (Rápido), significa que el sistema está orientado a tener tiempos de respuesta de 5 segundos, con respuestas de 1 segundo a consultas sencillas y, algunas más complejas, con respuestas de hasta 30 segundos . En situaciones típicas, si las respuestas toman más tiempo, el usuario perderá la concentración en lo que busca analizar.
Analysis (Análisis), lo que indica que al usuario debe proporcionársele suficiente funcionalidad para resolver sus problemas, sin la necesidad de contar con el apoyo de sistemas o de una pre-programación. De esta forma, se podrán realizar consultas no definidas, cálculos de diferencias, variaciones y tendencias, consolidar y llevar a cabo análisis de sensibilidad y de búsqueda de metas.
Shared (Compartida), significa que debe haber facilidad de acceso simultáneo, tanto de lectura como de escritura, aunado a un esquema de seguridad adecuado, con el objeto de guardar la confidencialidad (probablemente a nivel de celda).
Multidimensional, ha sido y continuará siendo un requisito, con la habilidad de manejar múltiples jerarquías y dimensiones.
Information (Información), son todos los datos y la información derivada, cuando y donde sea necesaria, en su contexto, tanto de información “suave”
como información “dura”, interna o externa.
Qué se entiende por DTS?
Son herramientas y objetos que permiten mover datos entre varios orígenes de datos diferentes o iguales. Un DTS puede realizar las siguientes tareas:
- Importación y exportación de datos entre dos orígenes de datos.
- Transformación de datos.
- Copia de objetos de base de datos : tablas, índices, etc.
- Ejecución de instrucciones de Transact-SQL.
DTS tiene una arquitectura OLE DB por lo que puede copiar y transformar múltiples orígenes de datos, entre ellos: SQL Server, Oracle.
VoF? La estructura de ABB (árbol binario de búsqueda) es un árbol completo.
F, el siguiente ABB no es completo:
33
/ \
17 35
/ \ \
15 28 42VoF? El árbol B+ nunca puede quedar lleno.
FALSO. Usando Load Factor al 100% puede que los nodos queden llenos.
VoF? Dado el grafo G(P,E) donde P={(a)} y E={(a,a)} decimos que es el mismo árbol.
FALSO. Dicho grafo no es un árbol, ya que para que sea árbol la suma de los nodos
debe ser igual a la suma de arcos más uno.
VoF? Configurando el Read Commited Isolation Level al ejecutar una transacción, se evita que otras transacciones modifiquen las filas que han sido leídas por la transacción actual.
VERDADERO. Read commited lee las filas y libera el lockeo.
VoF? Si un árbol es completo, la cantidad de arcos es par.
Contraejemplo:
O
/ | \
O O O
VoF? Si un árbol B tiene N claves entonces el grado es N+1.
FALSO. Un árbol de dos nodos puede solo tener un arco, por lo cual es de grado uno.
VoF? Una primery key y una foreign key son restricciones al modelo físico.
VERDADERO. ambas son restricciones, la PK de unicidad y la FK de restricción referencial.
VoF? Las únicas restricciones posibles a aplicar en el modelo relacional son por tabla.
FALSO. Existen restricciones a nivel de data type. Validaciones a nivel de campo, por ej, constraint de dominio.
VoF? La técnica de Hash abierto puede generar muchas lecturas secuenciales para un valor “clave hash” cuando hay alto grado de repetición de claves de usuario.
V
VoF? La compactación por algoritmo de Huffman permite redefinir el almacenamiento lógico de símbolos de tal manera que la pérdida de información sea despreciable.
FALSO. A diferencia de otros algoritmos de compactación (jpeg, divx,
mp3), Huffman no genera pérdida de información.
VoF? En PL-SQL, la única diferencia entre una función y un store procedure es que puede retornar valores.
F
VoF? Si en una consulta SELECT, hay al menos una función de grupo (COUNT, SUM, AVG, etc.) siempre debe colocarse la cláusula GROUP BY en dicho SELECT.
FALSO. La función de grupo puede ser aplicada a todo el set de datos que devuelve el select.
VoF? Una tabla no puede tener 2 claves foráneas que referencian a la misma tabla.
F
VoF? La implementación de una tabla de Hash es utilizada para recuperar datos por medio de una clave permitiendo un acceso de alta velocidad a los datos.
VERDADERO, justamente está describiendo el objetivo de una tabla de hash.
VoF? En un motor de base de datos relacional, una función creada por el usuario puede modificar el contenido de una tabla de la base donde fue creada.
FALSO. Una función no permite hacer modificaciones a los datos, solamente consultarlos. Esa es una de las diferencias entre los SP y las funciones.
VoF? Datamining son las técnicas y algoritmos utilizados para encontrar información y relaciones ocultas en un Datawarehose.
VERDADERO. Data Mining, la extracción de información oculta y predecible de grandes bases de datos, es una poderosa tecnología nueva con gran potencial para ayudar a las compañías a concentrarse en la información más importante de sus Bases de Información (Data Warehouse).
VoF? En un índice de un DBMS, armado en un árbol B, el tiempo de acceso a la información depende en parte del tamaño de la clave almacenada.
FALSO. En el peor de los casos, el camino de búsqueda termina en el nodo de la hoja más profunda, por lo tanto el tiempo de ejecución en el peor de los casos esta determinada por la altura del árbol-B.
VoF? En un modelo OLAP se puede aplicar normalización en cualquier tabla de dimensión.
FALSO. Si ya que están totalmente renormalizadas pero pierde el modelo de STAR.
VoF? La compresión que se logra mediante el algoritmo de Huffman es mayor cuando la variedad de caracteres diferentes que aparecen es menor.
VERDADERO. Ya que cuenta las repeticiones de cada carácter.
VoF? La técnica de Hash no puede ser implementada para uso de caché, ya que no garantiza el acceso de alta velocidad..
F
VoF? No es posible obtener el mismo resultado de una consulta OLAP a partir del OLTP que dío origen al mismo.
VERDADERO. Le da un tratamiento totalmente diferente a los datos y tiene a su vez orientaciones totalmente diferentes un OLAP está orientado al análisis empresarial, en cambio OLTP esta restringido a tareas específicas. Por lo tanto los resultados no serán los mismos.
VoF? Una vista es el equivalente a una consulta estática de una o más tablas.
FALSO. Desde el lado del resultado es el mismo, pero por otro lado la Vista guarda el “programa de ejecución” de la consulta, lo cual la hace más rápida a la hora de ejecutarce.
Comparación entre OLTP y OLAP
Imagen
