Gestión de Datos - UTN-FRBA - Información de la cátedra

Gestion de Datos
Objetivos de la materia
Desarrollar los conceptos de estructuración de los datos en dispositivos de
almacenamiento.

· Describir metodologías para el modelado de datos.

· Conocer modelos actuales para la persistencia de grandes volúmenes de datos

· Desarrollar los conceptos relacionados con la consistencia, integridad y seguridad de

la información.

· Aplicar técnicas y métodos para el tratamiento concurrente de los datos.

Programa Sintético
· Bases de Datos: Conceptos básicos, arquitectura, componentes.

· Sistemas de Archivos.

· Modelos Conceptuales Básicos (Jerárquico, Red, Relacional, Objetos)

· Seguridad, Privacidad y Concurrencia.

· Modelos Conceptuales de Datos.

· Álgebra y Cálculo Relacional.

· Lenguajes de Definición y Manipulación de Datos (SQL, QBE)

· Normalización.
· Integridad de Datos, transacciones

UNIDAD TEMÁTICA 1: ESTRUCTURAS DE DATOS

Concepto de Nodo y Relación. Relaciones Algebraicas. Tipos de Relaciones. Grafos.

Grafos restríctos e irrestrictos. Representación de grafos. Matriz de Adyacencia.
Estructura de Pfaultz. Estructura de Graal. Álgebra relacional. Concepto de paso y
camino. Algoritmos de búsqueda de paso. Estructuras de datos básicas. Pilas, colas,
listas, arboles. Aplicaciones. Representación computacional de las estructuras de
datos. Representación estática. Representación dinámica.

UNIDAD TEMÁTICA 2: MANIPULACIÓN DE DATOS

Algoritmos de Clasificación. Algoritmos de Búsqueda. Métodos de Ordenamiento.

Árboles Binarios. Árboles n-arios. Árbol B. Hashing. Algoritmos de Compactación.
Algoritmos de encriptamiento de datos.

UNIDAD TEMÁTICA 3: DISEÑO DE DATOS

Modelo Semántico. Análisis de Datos. Modelo de Datos. Entidad-Relación.

Identificadores y atributos. Definición de claves. Redundancia y consistencia.
Dependencia Funcional. Normalización de Datos. Arquitectura de Datos. Nivel externo.
Nivel conceptual. Nivel interno. Concepto Cliente Servidor. Modelo de Objetos.
Propiedades de los objetos. Análisis de Datos Orientado a Objetos.

UNIDAD TEMÁTICA 4: BASES DE DATOS

Concepto de Base de Datos. Tipos de Bases de Datos. Modelo en Red (IDMS). Modelo
Jerárquico (IMS). Modelo de lista invertida (DATACOM/DB). Modelo Relacional. Modelo
orientado a objetos. Concepto de SQL. Concepto de PL-SQL. Recuperación y
Concurrencia, Seguridad e integridad de los datos. Aplicaciones con SQL y PL-SQL.

Bibliografía
· Estructuras de Datos y Algoritmos. Aho

· Estructuras de Datos. Cairo

· Estructuras de Datos en C. Tenenbaum

· Algorítmos y Estructuras de Datos. Wirth.

· Design & Analysis Comput Algorithms. Aho

· Foundation for Object-relational Databases. Date

· Relational Databases. Date

· Database Models, Languages, Design. Johnson

· Principles of Database & Knowledge-base Systems I. Ullman

· Principles of Database & Knowledge-base Systems I. Ullman

· Diseño de Bases de Datos Relacionales. De Miguel

· Sistemas de Bases de Datos. Elsmari

· Data Warehousing. Gill

· Bases de Datos Relacionales. Mayne

UNIDAD I - ESTRUCTURAS DE DATOS
Grafos:
Los grafos permiten modelizar matemáticamente una estructura de datos.
G=(V,A)
V= Vertice ó nodo
A= Aristas ó arcos que conectan nodos, es un conjunto de par ordenado {a, b} ó ab.

Sobre las aristas o arcos:

Aristas Adyacentes: Se dice que dos aristas son adyacentes si convergen en el mismo
vértice.

Aristas Paralelas: Se dice que dos aristas son paralelas si el vértice inicial y el final son
el mismo.

Aristas Cíclicas: Arista que parte de un vértice para entrar en el mismo.

Sobre los vértices o nodos:

Vértices Adyacentes: si tenemos un par de vértices de un grafo (U, V) y si tenemos un

arista que los une, entonces U y V son vértices adyacentes y se dice que U es el vértice
inicial y V el vértice adyacente.

Vértice Aislado: Es un vértice de grado cero.

Vértice Terminal: Es un vértice de grado 1.

Jerarquía de un grafo: para soportar una relación jerárquica el grafo debe incluir sentido de
dirección en sus arcos o aristas para indicar el sentido de la dirección de la relación.

Grado (v) de un vértice o nodo: para un grafo no orientado el grado será igual a la cantidad
de aristas que tocan el nodo.
Para el caso de un grafo orientado, el grado puede ser positivo o negativo y será igual a la
cantidad de aristas que salen o llegan a él respectivamente.

Camino: cuando existe por lo menos 1 arco (o arista) que une dos nodos a y b se dice que
existe un camino entre ellos, notar que aquí no importa si el grafo está dirigido o no. Dos nodos
están conectados si existe un camino entre ellos.

Paso: es un concepto sólo relevante en grafos dirigidos, dado que el paso entre dos nodos a y
b es un camino con un sentido preestablecido, es decir, partiendo del nodo a y siguiendo el
sentido del arco se llega al nodo b.

Ciclo: es una sucesión de arcos adyacentes donde recorriendo cada arco solo 1 vez se puede
llegar al punto inicial. Todo ciclo es un camino hamiltoniano.

Camino Hamiltoniano: es aquel ciclo que recorre todos los nodos del grafo, y en el que cada
nodo se recorre sólo una vez (a excepción del nodo inicial del cual parte y al cual llega). En la
actualidad solo existen métodos para hallar ciclos hamiltonianos en grafos pequeños, para
grafos grandes solo resta la fuerza bruta u otros métodos costosos.

Longitud de paso: es la cantidad de arcos involucrados.

Tipos de Grafos
Grafos simples: es aquel en el que, cualquier par de nodos está unido a lo sumo por
únicamente un arco. Un grafo que no es simple se denomina complejo o multigrafo.
Grafos Conexos: es aquel en el que cada par de nodos está conectado por un camino (existe
un camino para llegar a cualquier nodo). Un grafo es fuertemente conexo si cada par de nodos
está conectado por al menos dos caminos disjuntos (existe más de un camino para llegar a
cualquier nodo) tal que al eliminar un nodo del grafo no quede disconexo.
Es posible determinar si un grafo es conexo utilizando los siguientes algoritmos:
- Búsqueda en anchura o amplitud (BFS - Breadth-first search)
- Búsqueda en profundidad (DFS - Depth-first search)

Grafos Completos: un grafo simple es completo si todos los pares posibles de nodos están
unidos por arcos (es un todos con todos). Un grafo completo de “n” nodos (vértices) tendrá
𝑛(𝑛−1)
exactamente 2
arcos (aristas).

Grafos Bipartitos: un grafo bipartito puede expresarse como 𝐺 = {𝑉1 ∪ 𝑉2, 𝐴}, es decir es la

unión de dos grupos de vértices tal que cumplen las siguientes condiciones:
- 𝑉1, 𝑉2 son disjuntos y no vacíos
 - Cada arista A une un vertice 𝑉1 con un vertice de 𝑉2

- No existen aristas uniendo dos elementos de 𝑉1, analogamente para 𝑉2

Grafo Ponderado: Un grafo ponderado, pesado o con costos es un grafo donde cada arista
tiene asociado un valor o etiqueta, para representar el costo, peso, longitud. Formalmente es
un grafo con una función 𝑣: 𝐴 → 𝑅 +, es decir que cada arista tiene asociado un valor
numérico real positivo.

Clasificación de los grafos

Según la presencia de direccion:
• Grafos Dirigidos: son aquellos en los cuales los arcos que vinculan a los vértices
tienen una dirección definida, la cual marca una jerarquía en la relación modelizada.
• Grafos No dirigidos: son aquellos donde los arcos no tienen una dirección definida que
marque propiedad en la relación modelizada.

Según las restricciones de sus relaciones:

 • Grafos Restrictos: son aquellos en los cuales la relación modelizada no debe cumplir
las propiedades de reflexividad, simetría y transitividad. De esta forma al
modelar una relación nos garantizamos que el grafo no contiene bucles, porque debido
a que debe ser anti-reflexivos ningún vértice está relacionado consigo mismo,
tampoco pueden existir ciclos simples, dado que al ser antisimétricos un vértice
no puede relacionarse con otro y este a su vez con el primero y por último al ser
anti-transitivo se disminuyen los diferentes caminos posibles entre cualquier par de
nodos. Por todo ello los grafos restrictos son más fáciles de administrar y operar,
es por ello que los diseñadores que utilizan grafos para modelar problemas tratan
de restringir lo más posible las relaciones que se representan a través de ellos.

• Grafos Irrestrictos: son aquellos que pueden modelizar cualquier relación

independientemente de las propiedades que cumpla o no.

Representación Computacional de los Grafos

Dinamica
Una representación es dinámica, cuando el espacio consumido para representar
computacionalmente al grafo, concuerda exactamente con la cantidad de nodos y
vértices a representar, esto es que no se consideran todas las posibilidades de relación
posibles, sino que solo se representa lo que ocurre en este momento.
De esta forma la representación sigue la “dinámica” de la estructura y es por ello
que las denominamos representaciones dinámicas.
Dinámicamente un grafo irrestricto puede representarse a través de varias
estructuras linkeadas, dentro de ellas encontramos a las Listas de Adyacencia, la
Estructura de Graal y la Estructura de Pfaltz.

Estatica
Una representación computacional se denomina estática, cuando el espacio
consumido para representar computacionalmente al grafo es invariable y fijo respecto a
la cantidad de nodos y vértices a representar, esto es que son consideradas todas las
ocurrencias de relaciones que puedan producirse entre todos los nodos, reservando el
espacio para dicha ocurrencia potencial.
De esta forma la representación no sigue la “dinámica” de la estructura, sino que
se mantiene fija y estática en el tiempo independientemente de las altas y bajas de arcos
o vértices que se produzcan en el grafo representado computacionalmente. Un gráfico
irrestricto puede representarse estáticamente mediante las siguientes:
- Matriz de adyacencia: es una matriz cuadrada 𝑀𝐴𝑛𝑥𝑛 donde “n” es el número de
vértices donde 𝑀𝐴𝑖𝑗 es el número de aristas que unen los vértices 𝑉𝑖 y 𝑉𝑗. La matriz será
binaria si el grafo es simple indicando con 1 si existe una relación y con 0 la ausencia de
la misma.
 - Matriz de incidencia: es una matriz de orden nxm, siendo n el número de vértices y m el
número de aristas 𝑀𝐼𝑛𝑥𝑚donde el elemento 𝑀𝐼𝑖𝑗 será 0 si la arista no incide en el vértice,
1 si la arista incide, y 2 si la arista incide dos veces (bucle).

Consumo de espacio y velocidad de representaciones Estáticas y Dinámicas

Las representaciones computacionales dinámicas no siempre ocupan menos espacio que las
representaciones computacionales estáticas, esto depende de la cantidad de relaciones o
arcos con que cuente el grafo en función de todas las relaciones posibles, de esta forma,
cuanto más arcos posea un grafo, menor será el espacio desperdiciado por las
representaciones estáticas y mayor será el desperdicio representado por los punteros en
las representaciones computacionales dinámicas.
En cuanto a la velocidad de operación, las representaciones computacionales
estáticas tienden a ser más rápidas que las dinámicas, esto se debe a que para
implementar nuevas relaciones no requieren realizar ningún alta en la representación,
debido a que a priori el espacio ya está dimensionado para la existencia de todas las
relaciones posibles, con lo cual se ahorra el tiempo involucrado en el pedido y
asignación de memoria para almacenar dicha relación que requiere la representación
dinámica. Sin embargo si la representación computacional estática es muy grande, está
velocidad de acceso disminuye por el gran espacio asignado y la dificultad de acceder
contiguamente a una posición determinada, siendo a veces más lenta que las
representaciones computacionales dinámicas.
Por lo visto se observa que ambos tipos de representaciones son válidos para ser
utilizados, normalmente se recomienda la utilización de representaciones
computacionales dinámicas para grafos grandes, con gran cantidad de vértices, lo cual
generaría en una representación estática un alto espacio ocupado, o también para grafos
dispersos, esto es, grafos con muchos nodos pero pocas relaciones entre ellos, mientras
que las representaciones computacionales estáticas se recomiendan para grafos más
pequeños donde pueda utilizarse la potencia de la velocidad de acceso de la
representación estática, o también para grafos densos, donde existe una gran cantidad de
relaciones definidas dentro de todas las posibles.
Resumiendo:
- Representación Dinámica: mejor para grafos grandes o dispersos.
- Representación Estática: mejor para grafos pequeños o densos.

Algoritmos de Búsqueda
Primero en Amplitud / anchura (BFS - Breadth-first search):
Es un algoritmo para recorrer o buscar elementos en un grafo (usado frecuentemente sobre
árboles).Intuitivamente, se comienza en la raíz (eligiendo algún nodo como elemento raíz en el
caso de un grafo) y se exploran todos los vecinos de este nodo. A continuación para cada uno
de los vecinos se exploran sus respectivos vecinos adyacentes, y así hasta que se recorra todo
el árbol. Nótese que cada nodo es puesto a la cola una vez y su lista de adyacencia es
recorrida una vez también.

- No utiliza backtracking, es decir no requiere retroceder.

- Utiliza una cola que se recorre tipo FIFO
- Se recomienda para problemas en los que se pide hallar la solución óptima entre varias
posibles

Primero en profundidad (DFS - Depth-first search):

Es un algoritmo que permite recorrer todos los nodos de un grafo o árbol de manera ordenada,
pero no uniforme. Su funcionamiento consiste en ir expandiendo todos y cada uno de los nodos
que va localizando, de forma recurrente, en un camino concreto. Cuando ya no quedan más
nodos que visitar en dicho camino, regresa (Backtracking), de modo que repite el mismo
proceso con cada uno de los hermanos del nodo ya procesado.

- Utiliza backtracking
- Utiliza una pila que se recorre tipo LIFO
- Esta técnica se utiliza cuando necesitamos encontrar respuesta a un problema
 sobre un grafo sin condiciones de optimización.

Video explicando la diferencia entre BFS - DFS

UNIDAD II - MANIPULACIÓN DE DATOS

Arboles

Desde el punto de vista conceptual, un árbol es un grafo que comienza con una raíz (root) y se
extiende en varias ramificaciones o líneas (branches), cada una de las cuales puede
extenderse en ramificaciones hasta terminar, finalmente en una hoja (leaves).

Un árbol es un grafo que cumple lo siguiente:

- Es acíclico
- Sumatoria de nodos = Sumatoria de arcos + 1 , o dicho de otra forma, si hay N
nodos tendrá N-1 arcos.
- Es dirigido
- Existe un camino único para todo par de nodos

Grado:
- De un nodo: es el número de descendientes directos de un determinado nodo.
- De un árbol: es el máximo grado de todos los nodos del árbol.

Nivel: el nivel de un nodo es la longitud del camino que va desde la raíz hasta ese nodo.
Dicho de otra forma es el número de arcos a ser recorridos para llegar a determinado nodo.
Considerando que el nivel de la raíz es 0, y la de cualquier otro nodo sería la de su padre + 1.
Profundidad o altura de un árbol: es igual a la cantidad de niveles del árbol.

Tamaño de un nodo: es el número de nodos descendientes más el nodo mismo. El tamaño del
árbol es igual al tamaño de su raíz.

Cardinalidad o tamaño del árbol: es el número máximo de nodos que puede tener un árbol
𝑛𝑖𝑣𝑒𝑙𝑒𝑠
𝑔𝑟𝑎𝑑𝑜

Raíz: también llamado minimal, es aquel que no tiene flechas entrantes, su nivel es 0.
Hojas: también llamado maximal, nodo terminal o nodo exterior, es aquel que no tiene flechas
salientes.
Nodo Rama: también llamados nodos interiores, son aquellos que no son hojas ni raíz.

Propiedades
• Dados dos nodos cualesquiera de un árbol, existe exactamente un camino que los
conecta. Una consecuencia importante de esta propiedad es que cualquier nodo puede
ser raíz, ya que, dado cualquier nodo de un árbol, existe exactamente un camino que lo
conecta con cualquier otro nodo del árbol.
• Un árbol con N nodos debe tener N − 1 aristas porque a cada nodo, excepto la raíz, le
llega una arista.
• La altura de cualquier nodo es 1 más que la mayor altura de un hijo suyo.
• Un árbol N-­ario con n ≥ 0 nodos internos, contiene ( 𝑁 − 1) 𝑛 + 1 nodos externos.
ℎ
• Un árbol N­-ario de altura h ≥ 0 tiene como máximo 𝑁 hojas.
Tipos de Árboles

Árbol binario
Un árbol binario es un árbol en el que ningún nodo puede tener más de dos hijos, se los
distingue como izquierdo y derecho, o subárbol izquierdo y derecho.

Árbol binario lleno

Es un árbol binario en el que cada nodo tiene 0 o 2 hijos.

Siendo:
● i = número de nodos internos
● n = número total de nodos
● l = numero de hojas
● h = número de niveles

Se cumplen los siguientes teoremas:

El número de nodos hoja se puede calcular como:
𝑛+1
𝑙= 𝑖+1 o 𝑙= 2
El número total de nodos se puede calcular como:
𝑛 = 2𝑖 + 1 o 𝑛 = 2𝑙 − 1
El número de nodos internos se puede calcular como:
𝑛−1
𝑖 = 2
o 𝑖=𝑙−1
ℎ−1
Un árbol lleno tendrá a lo sumo 2 hojas.
Árbol completo
Es aquel en el que todos sus nodos no maximales (nodos que No son hojas) tienen igual grado.

Arbol Lleno
Un árbol está lleno cuando es completo y sus nodos maximales se encuentran a la misma
profundidad / nivel.

Árbol binario completo

Un árbol binario completo es aquel en el que todos los niveles están llenos, a excepción
posiblemente del último nivel el cual es completado de izquierda a derecha. Es decir, los nodos
del último nivel pueden permitirse que falte un nodo, a condición de que el nodo que falta sea el
de la derecha.
El número máximo de nodos de un árbol binario completo con altura ℎ (ℎ𝑒𝑖𝑔ℎ𝑡) se puede
calcular como:
ℎ
𝑛ú𝑚𝑒𝑟𝑜 𝑚á𝑥𝑖𝑚𝑜 𝑑𝑒 𝑛𝑜𝑑𝑜𝑠 ≤ 2 − 1
Árbol Binario Perfecto
Es aquel en el que todos los nodos tienen el mismo grado o son hojas, y las hojas están al
mismo nivel.
Es un árbol binario 𝑇 con altura ℎ ≥ 0, tal que:
𝑇 = {𝑟, 𝑇𝐿, 𝑇𝑅}.
Donde r es la raíz, TL es Tree Left, TR es Tree Right.

Cumple las siguientes propiedades

- Si ℎ = 0 entonces 𝑇𝐿 = 𝑣𝑎𝑐𝑖𝑜 y 𝑇𝑅 = 𝑣𝑎𝑐𝑖𝑜
- Si ℎ > 0 entonces TL y TR son árboles binarios perfectos de altura ℎ − 1

El número total de nodos en este tipo de árboles será exactamente de:

ℎ
𝑛𝑢𝑚𝑒𝑟𝑜 𝑑𝑒 𝑛𝑜𝑑𝑜𝑠 = 2 − 1

Árbol Balanceado
Un árbol está balanceado si todos los subárboles desde la raíz pesan los mismo o sea tienen la
misma cantidad de elementos o una diferencia indivisible.
Árbol Binario Balanceado
Un árbol binario está balanceado si la altura de sus subárboles izquierdo y derecho difiere a lo
sumo en 1.

Un árbol binario está perfectamente balanceado si el camino desde la raíz a cualquier hoja
tiene la misma longitud. Los únicos árboles que están completamente balanceados son los
árboles binarios perfectos. En estos árboles todas las hojas están al mismo nivel.

Árboles de Expresión
Tomamos como ejemplo la expresión 𝑎 / 𝑏 + (𝑐 − 𝑑 ) 𝑒. Los nodos terminales (hojas) de un
árbol de expresión son las variables o constantes en la expresión (a, b, c, d, y e). Los no
terminales son los operadores (+,­× y ÷). Los paréntesis de la ecuación no aparecen en el árbol,
ya que justamente las posiciones de los operadores en el árbol son los que le asignan
prioridades. Para imprimir se usa el recorrido inorden y se utiliza el siguiente procedimiento:
Si se encuentra un nodo terminal, se lo imprime. De lo contrario, se hace lo siguiente:
1. Imprimir un paréntesis izquierdo
 2. Recorrer el subárbol izquierdo
3. Imprimir la raíz
4. Recorrer el subárbol derecho.
5. Imprimir el paréntesis derecho.

Lectura Inorden: 3+ 5*8 - 4*2

Arboles de Busqueda
Soporta las operaciones de búsqueda, inserción y eliminación de forma eficiente.
Las claves no aparecen en los nodos de forma arbitraria, sino que hay un criterio de orden (o
relación de orden) que determina donde una determinada clave puede ubicarse en el árbol en
relación con las otras claves en ese árbol. Dicho de otra forma, debe haber una forma de
ordenar los elementos y estos deben ser comparables.
Ejemplos:

De la misma forma si se quisiera encontrar un elemento en dicho árbol, la búsqueda se realiza

por niveles y no por elementos de forma tal que para encontrar cualquier elemento a lo sumo
realizaremos tantas preguntas como niveles tenga el árbol.

Árboles Binarios de Búsqueda

Un árbol binario con raíz R es de búsqueda si no es vacío y:
- Si tiene un subárbol izquierdo este es de búsqueda y su raíz es menor a R.
- Si tiene un subárbol derecho este es de búsqueda y su raíz es mayor a R.
Si a este tipo de árbol se lo recorre en inorden se muestran los elementos ordenados de
forma ascendente: 3 - 7- 8 - 13 - 16 - 19 - 21 - 24
Notar además que el ABB no es necesario que esté completo aunque sí podría darse el caso
que lo este, por ejemplo, si en el gráfico anterior se eliminan los nodos del último nivel nos
quedaría un ABB completo.

La complejidad temporal de búsquedas en un Árbol Binario de Búsqueda es directamente

proporcional a la altura del árbol. Dicho de otro modo, el costo de las operaciones en un árbol
binario de búsqueda es proporcional al número de nodos consultados durante la operación.
El costo de acceso a cada nodo es de 1 más su profundidad.
En un árbol binario de búsqueda que se encuentre balanceado el costo de los accesos es
logarítmico 𝑂(𝑙𝑜𝑔 𝑁). En el peor de los casos, en un árbol binario de búsqueda no balanceado
será de 𝑂(𝑛), es decir, será lineal, ya que hay N nodos por recorrer hasta el nodo de mayor
profundidad.

Operaciones
- Búsqueda: se utiliza para localizar elementos a partir de su clave, por ejemplo para
verificar si una clave está presente en el árbol o para obtener el nodo con el valor que
pedimos. Para ello comenzamos por la raíz y preguntamos si su valor es igual al valor
que buscamos, si no lo es repetimos la operatoria de forma análoga y utilizando
recursividad sobre los subárboles izquierdo y derecho.
 - Inserción: es necesario introducir los elementos de forma ordenada y además, si el
árbol permite duplicados se puede mantener un contador que mantenga el número de
incidencias. Las reglas serían:
- Si el árbol está vacío: insertamos en la raíz.
- Si la raíz del árbol es igual al elemento a insertar y NO permitimos duplicados
emitimos un error de lo contrario aumentamos el contador.
- Si el elemento a insertar es menor a la raíz, insertamos en el subárbol izquierdo.
- Si el elemento a insertar es mayora la raíz, insertamos en el subárbol derecho.

- Eliminacion
- Si no tiene hijos puede eliminarse sin ajuste.
- Si tiene solo un subárbol, su hijo toma su lugar.
- si tiene dos subárboles, el menor de los hijos del subárbol derecho puede tomar el
lugar del padre.

Árbol Binario Balanceado AVL

Fue la primera variante de Árbol Binario de Búsqueda con autobalanceo. Se creó con la
intención de evitar que la altura del árbol crezca de forma descontrolada por las sucesivas
inserciones y eliminaciones arbitrarias lo que provocaba a su vez que empeore la complejidad
de las búsquedas.
Un árbol AVL cumple con la condición de que la diferencia entre las alturas de los subárboles
de cada uno de sus nodos es, como mucho de 1, si en cualquier momento esta propiedad se
incumple se efectúa un autobalanceo para recuperar la propiedad.
La denominación de árbol AVL viene dada por los creadores de tal estructura (Adelson-Velskii y
Landis).
Ofrece búsquedas, inserciones y eliminaciones en tiempo logarítmico 𝑂(𝑙𝑜𝑔 𝑛).
Árboles k-arios, n-arios o m-arios
Un árbol k-arios es un árbol de grado K. Donde cualquier nodo tiene entre 0 y K hijos.
Puede ser:
- Completo: si todos los niveles están llenos a excepción del último el cual tiene sus
hojas pegadas a la izquierda.
- Lleno (Full): si todos los nodos tienen 0 o K hijos.
- Perfecto: si a parte de estar lleno todas sus hojas están al mismo nivel.
Usos:
- Extiende el concepto de árbol binario de búsqueda y lo aplica a árboles B.
- Muy extendidos en bases de datos y sistemas de archivos.

Árboles m-arios de Búsqueda

Si se tiene un conjunto de datos muy grande que no podemos colocar en la memoria principal,
nos veríamos obligados a implementar el árbol de búsqueda en un almacenamiento
secundario, como el disco. Las características de un disco a diferencia de la memoria principal
hacen que sea necesario utilizar valores de M más grandes para poder implementar estos
árboles de búsqueda de forma eficiente. Al elegir un valor de M grande, podemos arreglar para
que un nodo de un árbol M-­ario pueda ocupar un bloque de disco completo. Si cada nodo
interno en el árbol M-ario tiene exactamente M hijos, puedes usar el siguiente teorema:
ℎ ≥ [𝑙𝑜𝑔 𝑏𝑎𝑠𝑒(𝑀) (( 𝑀 − 1) 𝑛 + 1)] − 1
Donde n es el número de nodos internos de un árbol de búsqueda.
En resumen:
- Rara vez va a caber el contenido de un árbol binario en memoria
- Lo normal en estos casos es tener un árbol M-ario en memoria secundaria (disco)
y cargarlo parcialmente.
- Como la memoria secundaria es lenta nos interesa reducir el número de accesos.

Árboles B - (B-Trees)

Son árboles M-arios balanceados de manera tal que se garantice que la búsqueda, la
inserción y la eliminación sean todos de tiempo logarítmico 𝑂(𝑙𝑜𝑔 𝑛 ).
Se utilizan para grandes volúmenes de datos que no caben en memoria, por lo tanto se
almacenan en disco y se lee en la forma de bloques (es por eso que se trata de elegir un valor
de M grande y correlativo al tamaño del bloque).
El secreto es entonces disminuir el número de accesos a disco. La mayoría de operaciones
(búsqueda, inserción, eliminación, etc) requiere 𝑂(ℎ) accesos a disco donde h (height) es la
altura del árbol.
Se intenta mantener baja la altura del B-Tree almacenando en cada nodo tantas claves como
sea posible. Generalmente el tamaño de cada nodo se mantiene igual al tamaño de bloque.
Si se lo compara con Árboles Binarios de Búsqueda o AVL Trees la mayoría de operaciones en
un B-Tree se realizan con mejores resultados ya que este último por todo lo anterior
comentado, tendrá una altura menor y por consiguiente menor será la cantidad de accesos a
disco necesarios para realizar una operación.

En un nodo de B-tree hay un número K de claves y un número K+1 (se suele denotar M por el
grado) de hijos (punteros).
En B-Tree todas las hojas están al mismo nivel.
Las claves de la izquierda son menores que las de la derecha. Es decir, van en orden creciente
o ascendente ( 𝑘𝑖 < 𝑘𝑖+1)
Cada nodo hijo contiene claves que son mayores a su clave izquierda y menores a la clave
derecha. Ejemplo, el hijo (puntero) entre K1 y K2 contendrá claves menores a K2 y mayores a
K1.

Factor de ramificación: cuanto más claves podemos representar dentro de un nodo mayor
será el factor de ramificación.
Esto es positivo porque significa que desde un nodo podemos viajar a muchos otros y esto a su
vez reduce el número de accesos de disco.

Factor de Carga: El factor de carga es un porcentaje de carga de los nodos de un árbol B, el

cual se aplica solo en el proceso de carga inicial del árbol.
Un factor de carga al 100% se utiliza cuando el Árbol B representa un índice asociado a una
tabla que sea de consulta con pocas actualizaciones o que sea histórica.
Un factor de carga al 75% - 85% se utiliza cuando el Árbol B representa un índice asociado a
una tabla que tenga muchas actualizaciones (inserts, updates, deletes) en forma online.

Grado del arbol:

El B-Tree se define por el grado mínimo M. Donde M es un valor que depende del tamaño de
bloque en disco.
Cada nodo excepto la raíz debe contener al menos 𝑀 − 1 claves.
La raíz debe contener al menos 1 clave.
Todos los nodos, incluyendo la raíz, pueden contener como máximo 2 * 𝑀 − 1 claves.
El grado del árbol no depende solo del número de claves sino también del factor de carga.

Grado de un nodo:
análogamente a otros tipos de árboles representa el número de hijos que puede tener un nodo.
- Un nodo con K claves puede tener K+1 hijos.
- Dicho de otra forma, si tiene M hijos tendra M-1 claves.

Caracteristicas:
1. La raíz de T tiene al menos dos subárboles y a lo sumo M subárboles (hijos).
𝑀
2. Todos los nodos internos de T tienen entre 2
y 𝑀 hijos.
3. Todos los nodos externos (maximales) de T están al mismo nivel.

El punto 2 garantiza que el árbol no degenere en un simple árbol binario o ternario.

Operaciones
Soporta las operaciones habituales de búsqueda, insercion, eliminacion y recorrido más las
siguientes:
- Dividir: si un nodo ya está lleno y es necesario insertar un elemento es se debe
reestructurar el árbol.
- Reestructurar: al eliminar un nodo es necesario controlar que las propiedades o
características del árbol no se vean afectadas por lo que puede ser necesario
reestructurar.
- Inserciones: Suceden al nivel de los nodos hoja.
B-Tree Visualization

Árboles B+ (B+ Trees)

Es una variación del B-Tree muy utilizada en Índices de Bases de datos, sistemas de archivos
NTFS, etc. Tiene las siguientes características:
- Toda la información se guarda en las hojas.
- Los nodos internos sólo contienen claves y punteros.
- Los nodos hoja se encuentran unidos entre sí como una lista enlazada para permitir
búsqueda secuencial.

Altura:
Dado 𝑀 la cantidad de hijos de un determinado nodo se define como:
𝑛
- La altura ℎ en el peor caso será de: 𝑙𝑜𝑔 𝑀
𝑀 𝑛
- La altura ℎ en el mejor caso será de: 𝑙𝑜𝑔 ( 2
)
Este caso se debe a que si guardamos menos hijos en los nodos, se necesitarán más niveles
para almacenar todo.

Cantidad de claves:
Siendo ℎ la altura y 𝑛 el igual al grado del árbol.
ℎ
- El número máximo de claves está dado por: 𝑛 −1
𝑛 ℎ−1
- El número mínimo de claves está dado por: 2( 2 ) −1

B-Tree Vs B+ Tree

B-Tree B+Tree

Todos los nodos son puntos de datos Solo las hojas tienen datos

Como no todas las claves están disponibles Como toda la información está en las hojas y
en las hojas, las búsquedas suelen llevar están están linkeadas las búsquedas son
más tiempo más rápidas

No se mantienen claves duplicadas Se mantienen duplicados

La inserción lleva más tiempo Inserción más sencilla

Las eliminaciones son complejas Las eliminaciones son fáciles dado que todos
los nodos hojas tienen los datos

Los nodos hojas NO son linkeados mediante Los nodos hojas son linkeados mediante una
una lista enlazada lista enlazada

Sin claves redundantes Puede haber claves redundantes

Utilizados en Bases de Datos y Motores de Utilizados en índices de Bases de Datos o

Búsqueda. indexación en general.

Recorridos de los Árboles

Hay dos tipos de recorridos o barridos, primero en amplitud (BFS) y primero en profundidad
(DFS).
Primero en Profundidad (DFS):
En este método de recorrido es mejor considerar los nodos izquierdo y derecho como
subárboles.

Se deben procesar la raíz del subárbol izquierdo y el derecho y dependiendo del orden en que
se procesen tendríamos las siguientes configuraciones:
- Preorden: El recorrido en preorden puede ser definido recursivamente de la siguiente
manera:
En el caso de un árbol binario, el algoritmo resulta:
1. Visitar primero la raíz
2. Recorrer el subárbol izquierdo
3. Recorrer el subárbol derecho.

- Postorden: A diferencia del preorden donde se visita primero a la raíz, en el recorrido

en postorden se visita la raíz a lo último.
En el caso de los árboles binarios:
1. Recorrer el subárbol izquierdo
2. Recorrer el subárbol derecho.
3. Visitar por último la raíz.

- Inorden (Simétrico): El recorrido inorden solo puede ser usado en árboles binarios.
En este recorrido, se visita la raíz entre medio de las visitas entre el subárbol izquierdo y
el derecho.
1. Recorrer el subárbol izquierdo
2. Visitar la raíz
3. Recorrer el subárbol derecho.

Ejemplo de recorridos del árbol de la figura:

 Preorden 8-3-7-4-5-22-14-13-11-9-45

Postorden 5-4-7-3-9-11-13-14-45-22-8

Inorden 3-4-5-7-8-9-11-13-14-22-45

Los algoritmos de barrido son siempre iguales, dado que un árbol se basa en la recursividad, lo
único que se modifica es el momento en que se lee el nodo.

Primero en Amplitud o Anchura (BFS):

En primero en anchura se visitan los nodos en el orden de su profundidad en el árbol. Primero
se visita todos los nodos en la profundidad cero (la raíz), y después todos los de profundidad
igual a uno, etc. Para poder realizar una búsqueda de primero en anchura es necesario valerse
de una estructura de datos auxiliar, la cola.
1. Poner en la cola la raíz.
2. Mientras que la cola no esté vacía
3. Quitar primero de la cola y asignarlo a una variable auxiliar, Nodo.
4. Imprimir el contenido de Nodo.
5. Si Nodo tiene hijo izquierdo, poner al hijo izquierdo en la cola.
6. Si Nodo tiene hijo derecho, poner al hijo derecho en la cola.

Crecimiento de los Árboles

El crecimiento de un árbol es exponencial en función del grado del mismo, o sea, que en
cada nivel puede crecer en función del grado definido.
La máxima cantidad de elementos posibles de un árbol está dada en función de la siguiente
fórmula:
𝑛𝑖𝑒𝑣𝑒𝑙𝑒𝑠
𝑚𝑎𝑥 𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑜𝑠 = 𝑔𝑟𝑎𝑑𝑜 −1

Si tomamos la fórmula de crecimiento y despejamos de ella la cantidad de niveles llegamos a la

siguiente fórmula de búsqueda que justifica que un árbol tiene una búsqueda logarítmica:

𝑛𝑖𝑒𝑣𝑒𝑙𝑒𝑠
𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑜𝑠 = 𝑔𝑟𝑎𝑑𝑜 −1
 𝑛𝑖𝑒𝑣𝑒𝑙𝑒𝑠
𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑜𝑠 + 1 = 𝑔𝑟𝑎𝑑𝑜
𝑙𝑜𝑔 𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑜𝑠 + 1 = 𝑛𝑖𝑣𝑒𝑙𝑒𝑠 * 𝑙𝑜𝑔 𝑔𝑟𝑎𝑑𝑜𝑠
𝑛𝑖𝑣𝑒𝑙𝑒𝑠 = 𝑙𝑜𝑔 𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑜𝑠 + 1 − 𝑔𝑟𝑎𝑑𝑜𝑠

conclusion:
𝑛𝑖𝑣𝑒𝑙𝑒𝑠 > 𝑙𝑜𝑔 𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑜𝑠

Ejemplo:
Una estructura de datos básica como por ejemplo una lista tiene una búsqueda secuencial, por
lo tanto, si tengo 10 elementos a lo sumo debería realizar 10 preguntas para encontrar un
elemento. En un árbol esa búsqueda no es lineal, sino que es logarítmica.

Clasificación de Algoritmos
Estabilidad: Un ordenamiento se considera estable si mantiene el orden relativo que tenían
originalmente los elementos con claves iguales. Si se tiene dos registros A y B con la misma
clave en la cual A aparece primero que B, entonces el método se considera estable cuando A
aparece primero que B en el archivo ordenado.
La mayoría de los métodos de ordenamiento simples son estables, pero gran parte de los
métodos complejos no lo son. Se puede transformar uno inestable en estable a costa de mayor
espacio en memoria o mayor tiempo de ejecución.
Una de las ventajas de los métodos estables es que permiten que un array se ordene usando
claves múltiples, por ejemplo, por orden alfabético del apellido, luego el nombre, luego el
documento, etc.
Ejemplo: tenemos el siguiente array de tuplas que se deben ordenar por el primer elemento de
cada tupla
(4, 1) (3, 7) (3, 1) (5, 6)

Un algoritmo con estabilidad nos retornaria: (3, 7) (3, 1) (4, 1) (5, 6)

Un algoritmo inestable retornaria: (3, 1) (3, 7) (4, 1) (5, 6)

In situ:
Los métodos in situ son los que transforman una estructura de datos usando una cantidad extra
de memoria, siendo ésta pequeña y constante. Generalmente la entrada es sobrescrita por la
salida a medida que se ejecuta el algoritmo.
Por el contrario, los algoritmos que no son in situ requieren gran cantidad de memoria extra
para transformar una entrada.
Fundamental para optimización debido a que utilizar la misma estructura disminuye los tiempos
de ejecución, ya que no se debe utilizar tiempo en crear nuevas estructuras, ni copiar
elementos de un lugar a otro.

Clasificación interna y externa

Si el archivo a ordenar cabe en memoria principal, entonces el método de clasificación es
llamado método interno, por otro lado si ordenamos un conjunto de datos muy grande que no
cabe en memoria como archivos desde un disco u otro dispositivo, se llama método de
clasificación externo.
La diferencia radica en que el método interno puede acceder a los elementos fácilmente y de
forma aleatoria, mientras que el externo debe acceder a los elementos de forma secuencial o al
menos en grandes bloques de datos.

Complejidad
Trata de los recursos necesarios para resolver un problema. Normalmente se analizan los
siguientes.
- Tiempo: mediante una aproximación al número de pasos de ejecución de un algoritmo
para resolver un problema.
- Espacio: mediante una aproximación a la cantidad de memoria utilizada para resolver
un problema.

Big O notation: al hablar de costes de ejecución el número exacto de pasos depende de la

máquina en la que se implementa, del lenguaje utilizado y de otros factores. Para no tener que
hablar del costo exacto de un cálculo se utiliza esta notación que permite generalizar la noción
de coste independientemente del equipo utilizado.
Considerando a 𝑛 como el número de elementos a ordenar podemos hablar de:
 - Complejidad u orden constante: significa que el tiempo necesario para buscar un item
en la colección no depende de su tamaño y de hecho es constante.
𝑂(1)
- Complejidad u orden lineal: son los problemas que se resuelven en un tiempo que se
relaciona linealmente con su tamaño. Utilizando la big O notation se representa como
𝑂(𝑛)
- Complejidad u orden polinómico: se representa por una fórmula polinómica y se dice
que estos problemas se pueden resolver en tiempo polinómico. Son aquellos agrupados
en la clase de complejidad P.
- Complejidad u orden factorial o combinatorio: Estos problemas no tienen una
solución práctica, es decir, una máquina no puede resolverlos en un tiempo razonable.

Clases de complejidad
Los problemas de decisión se clasifican en conjuntos de complejidad comparable llamados
clases de complejidad.
La clase de complejidad P es el conjunto de los problemas de decisión que pueden ser
resueltos en una máquina determinista en tiempo polinómico, lo que corresponde intuitivamente
a problemas que pueden ser resueltos aún en el peor de sus casos. Problemas solubles.
La clase de complejidad NP es el conjunto de los problemas de decisión que pueden ser
resueltos por una máquina no determinista en tiempo polinómico. Todos los problemas de esta
clase tienen la propiedad de que su solución puede ser verificada efectivamente. Solución
verificable.
Los problemas NP-completos pueden ser descritos como los problemas en NP que tienen menos
posibilidades de estar en P y pueden ser considerados intratables.

Intratabilidad: Los problemas que pueden ser resueltos en teoría, pero no en práctica, se
llaman intratables. Qué se puede y qué no en la práctica es un tema debatible, pero en general
sólo los problemas que tienen soluciones de tiempos polinomiales son solubles.
Métodos de Ordenamiento.

Ordenamiento de la Burbuja (Bubblesort)

Uno de los más lentos y poco recomendables pero a la vez más sencillos de implementar.
Consiste en hacer N − 1 pasadas sobre los datos, donde en cada paso, los elementos
adyacentes son comparados e intercambiados si es necesario. Durante la primera pasada el
elemento más grande va “burbujeando” a la última posición del array. En general, luego de K
pasadas por el array, los últimos K elementos del array se consideran bien ordenados por lo
que no se los tendrá en cuenta.
Varios experimentos de ordenamiento de cadenas en Java hechos por Astrachan muestran que
el ordenamiento de burbuja es 5 veces más lento que el ordenamiento por inserción, y 40%
más lento que el ordenamiento por selección.
El tiempo de ejecución
2
- En general 𝑂(𝑛 )
- Mejor:
- Peor:

Nota: bubblesort siempre tendrá un rendimiento en orden de complejidad cuadrático sin

importar cómo vengan los datos (desordenados, semi-ordenados, etc).

Ordenamiento por Inserción (Insertion Sort)

Es in situ, sencillo de implementar y eficiente para ordenar arrays que tienen pocos elementos y
están semiordenados y, es más rápido en la práctica que otros algoritmos del mismo orden de
complejidad como Selection Sort y Bubble Sort.
Se basa en la idea del ordenamiento parcial, en el cual hay un marcador que apunta a una
posición donde a su izquierda se considera que están los elementos parcialmente ordenados.
El algoritmo comienza eligiendo el elemento marcado para poder insertarlo en su lugar
apropiado en el grupo parcialmente ordenado, para eso sacamos temporalmente al elemento
marcado y movemos los restantes elementos hacia la derecha. Nos detenemos cuando el
elemento a ser cambiado es más pequeño que el elemento marcado, entonces ahí se
intercambian el elemento que está en esa posición con la del elemento marcado.
El tiempo de ejecución:
2
- En general: 𝑂(𝑛 )
- Mejor: 𝑂(𝑛) (ya se encuentra ordenado y hace una sola pasada)
- Peor:
Ordenamiento por árbol binario (Binary Insertion Sort ó Binary Tree Sort)
Hace uso de un Árbol Binario de Búsqueda.
Se basa en ir construyendo poco a poco el árbol binario introduciendo cada uno de los
elementos, los cuales quedarán ya ordenados. Después, se obtiene la lista de los elementos
ordenados recorriendo el árbol en inorden.
Se lo puede comparar con Quicksort o HeapSort, pero como estos son in situ, ofrecen mejor
rendimiento que Tree Sort ya que no se ven penalizados por el espacio de memoria que Tree
Sort requiere.
El tiempo de ejecución:
- En general: 𝑂(𝑛 𝑙𝑜𝑔 𝑛)
- Mejor:
- Peor:

Ordenamiento por mezcla (Merge sort)

Diseñado por John Von Neumann en 1945. Conceptualmente, el ordenamiento por mezcla
utiliza un método del tipo “divide y vencerás” y funciona de la siguiente manera:
1. Si la longitud de la lista es 0 o 1, entonces ya está ordenada. En otro caso:
2. Dividir la lista desordenada en dos sublistas de aproximadamente la mitad del tamaño.
3. Ordenar cada sublista recursivamente aplicando el ordenamiento por mezcla.
4. Mezclar las dos sublistas en una sola lista ordenada.
El ordenamiento por mezcla incorpora dos ideas principales para mejorar su tiempo de
ejecución:
1. Una lista pequeña necesitará menos pasos para ordenarse que una lista grande.
2. Se necesitan menos pasos para construir una lista ordenada a partir de dos listas
también ordenadas, que a partir de dos listas desordenadas. Por ejemplo, sólo será
necesario entrelazar cada lista una vez que estén ordenadas.
Una de las desventajas de este algoritmo es que precisa de una cantidad de memoria
proporcional a la cantidad de elementos a ordenar, por otro lado, sus ventajas son estabilidad,
velocidad y no tolera “el peor de los casos”.
Al igual que Tree Sort se lo compara con QuickSort y HeapSort, y sufre de las mismas
debilidades debido que estos son in situ y no se ven penalizados por el espacio extra de
memoria que Mergesort requiere. Su principal ventaja frente a estos es que es estable.
El tiempo de ejecución:
- En general: 𝑂(𝑛 𝑙𝑜𝑔 𝑛)
- Mejor:
 - Peor:

Ordenamiento Shell (Shell Sort)

El Shell sort es una generalización del ordenamiento por inserción, teniendo en cuenta dos
observaciones:
1. El ordenamiento por inserción es eficiente si la entrada está "casi ordenada".
2. El ordenamiento por inserción es ineficiente, en general, porque mueve los valores solo
una posición cada vez.
El algoritmo Shell sort mejora el ordenamiento por inserción comparando elementos separados
por un espacio de varias posiciones. Esto permite que un elemento haga "pasos más grandes"
hacia su posición esperada. Los pasos múltiples sobre los datos se hacen con tamaños de
espacio cada vez más pequeños. El último paso del Shell sort es un simple ordenamiento por
inserción, pero para entonces, ya está garantizado que los datos del vector están casi
ordenados.
El tiempo de ejecución:
Existen muchas implementaciones que son diferentes.
1.25
- En general: 𝑂(𝑛 ) o 𝑂(𝑛 𝑙𝑜𝑔 𝑛)
- Mejor:
2
- Peor: 𝑂(𝑛 )

Ordenamiento por Selección (Selection Sort)

Es más rápido que Bubble Sort, y no es mucho más complejo.
Comienza buscando el elemento más pequeño del array y se lo intercambia con el que está en
la primera posición, luego se busca el segundo elemento más pequeño y se lo coloca en la
segunda posición. Se continua con este proceso hasta que todo el array está ordenado.
Los pasos son:
 ● Buscar el mínimo elemento de la lista
● Intercambiarlo con el primero
● Buscar el siguiente mínimo en el resto de la lista
● Intercambiarlo con el segundo
Generalizando:
● Buscar el mínimo elemento entre una posición 𝑖 y el final de la lista
● Intercambiar el elemento más pequeño con el elemento de la posición 𝑖

El tiempo de ejecución:
2
- En general: 𝑂(𝑛 )
- Mejor:
- Peor:

Ordenamiento por Montículo (Heap Sort)

Se basa en una estructura de datos llamada montículo binario (ver apunte de árboles), que es
una de las formas de implementar una cola de prioridad. Más precisamente un montículo
binario es un árbol binario completo representado mediante un array, en el cual cada nodo
satisface la condición de montículo. Para que se cumpla la condición de montículo la clave de
cada nodo debe ser mayor (o igual) a las claves de sus hijos, si es que tiene. Esto implica que
la clave más grande está en la raíz.
Este algoritmo no es recursivo y no requiere espacio de memoria adicional ya que es in situ.
Consta principalmente de dos etapas, carga del árbol y luego extracción de la raíz.
Vale mencionar que si los datos vienen semi-ordenados será notablemente más óptimo.
Se lo compara con QuickSort que también es in situ y tiene el mismo orden de complejidad,
aunque en la práctica este último suele ofrecer mejores resultados y también es más sencillo
de implementar. Heapsort será una mejor opción que quicksort solo en el caso de que los datos
vengan semi-ordenados.
También se lo compara con Mergesort ya que ronda el mismo orden de complejidad, aunque
este último no es in situ y requiere más espacio de memoria tiene la ventaja de que es estable
y en comparación con Heapsort, funciona mejor cuando la entrada está parcialmente ordenada.

El tiempo de ejecución:
- En general: 𝑂 (𝑛 𝑙𝑜𝑔 𝑛)
- Mejor: 𝑂 (𝑛 𝑙𝑜𝑔 𝑛)
- Peor: 𝑂 (𝑛 𝑙𝑜𝑔 𝑛)

Ordenamiento Rápido (Quicksort)

Es recursivo, no es estable y es in-situ. Precisa de una estructura de pila auxiliar.
Método de ordenamiento por intercambio con partición.
Descripción del algoritmo:
● Elegir un elemento del conjunto de elementos a ordenar, al que llamaremos pivote.
 ● Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un
lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al
pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de
la implementación deseada. En este momento, el pivote ocupa exactamente el lugar
que le correspondera en la lista ordenada.
● La lista queda separada en dos sublistas, una formada por los elementos a la izquierda
del pivote, y otra por los elementos a su derecha.
● Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan
más de un elemento. Una vez terminado este proceso todos los elementos estarán
ordenados.

El tiempo de ejecución:
- En general: 𝑂 (𝑛 𝑙𝑜𝑔 𝑛)
- Mejor: 𝑂 (𝑛 𝑙𝑜𝑔 𝑛)
2
- Peor: 𝑂(𝑛 ) listas semi-ordenadas o ordenadas

Algoritmos de Compactación

Algoritmo de Huffman
Creado en 1952 por David Huffman este algoritmo, utilizado para compresión y encriptación
de datos, toma un alfabeto de n símbolos, junto con sus frecuencias de aparición asociadas, y
produce un código de Huffman para ese alfabeto y esas frecuencias. Se utiliza un árbol binario
y una tabla de frecuencias.
El algoritmo consiste en la creación de un árbol binario que tiene cada uno de los símbolos por
hoja, y construido de tal forma que siguiéndolo desde la raíz a cada una de sus hojas se
obtiene el código Huffman asociado a él.
1. Se crean varios árboles, uno por cada uno de los símbolos del alfabeto, consistiendo
cada uno de los árboles en un nodo sin hijos, y etiquetado cada uno con su símbolo
asociado y su frecuencia de aparición.
2. Se toman los dos árboles de menor frecuencia, y se unen creando un nuevo árbol. La
etiqueta de la raíz será la suma de las frecuencias de las raíces (ahora hojas) de los dos
árboles que se unen, y cada uno de estos árboles será un hijo del nuevo árbol. También
se etiquetan las dos ramas del nuevo árbol: con un 0 la de la izquierda, y con un 1 la de
la derecha.
3. Se repite el paso 2 hasta que solo quede un árbol.
Con este árbol se puede conocer el código asociado a un símbolo, así como obtener el símbolo
asociado a un determinado código.

Características:
- El algoritmo identifica cada carácter del archivo a comprimir y le asigna un código de
longitud variable según su frecuencia.
- A más ocurrencias del carácter más pequeño será la longitud del código asignado.

Aplicaciones:
- Conveniente cuando la cantidad de espacio en disco es insuficiente o los tiempos de
transmisión son prolongados con costos elevados.
- Muy eficiente con archivos de texto (txt, excel, word, pdf, etc)

Observaciones. El problema del prefijo, que se presenta en las codificaciones de longitud

variable queda solucionado en el árbol de Huffman al ser el nodo maximal el que contiene el
carácter.

Mediante ejemplo, la estructura de la tabla de frecuencias de Huffman es como la siguiente:

Supongamos tenemos la palabra NEUQUEN
 Estado Caracter Frecuencia Codigo Dirección en
Árbol

E 3 00

N 3 01

U 2 10

BLK (blank - 1 110

espacio)

Q 1 111

Nota: La columna Código puede rellenarse luego de crear el árbol ya que para ellos hay que
seguir las ramas codificadas en binario hacia cada símbolo que se encuentra en las hojas.

Hashing
Una 𝑓𝑢𝑛𝑐𝑖𝑜𝑛 ℎ𝑎𝑠ℎ es cualquier función que mapea cadenas de tamaño arbitrario a códigos
llamados valores hash los cuales normalmente tienen longitud fija.

Se puede pensar la función hash como una función

𝐻: 𝑈 → 𝑀
Donde 𝑈 es el conjunto de dominio y 𝑀 es la imagen de la función.
La idea básica de un valor hash es que sirva como una representación compacta de la
cadena de la entrada. Por esta razón, se dice que estas funciones permiten resumir datos del
conjunto dominio.
Estos valores hash son utilizados para indexar tablas hash, se llama hashing a la acción de
utilizar una función hash para indexar una tabla hash y hallar el valor o dirección con los datos
deseados.

Es un método de acceso a datos eficiente con respecto al consumo de espacio y tiempo de

procesamiento, que por ejemplo, evita el tiempo de acceso no-lineal de las estructuras de
árboles y listas, en las cuales es necesario comparar una cierta cantidad de claves hasta
encontrar la buscada, permitiendo reducir los tiempos de acceso.
Es utilizado en sistemas de almacenamiento de datos y aplicaciones de consulta de datos.
El principal problema inherente a este método se produce cuando el valor que devuelve la
función de hash() es el mismo para dos o más claves iguales, lo que se define como colisión.
Más precisamente:

Colisión
Sean k1 y k2 claves pertenecientes a los registros r1 y r2 respectivamente, con
k1≠ k2. Y sea h(k) la función de hash. Si h(k1)=h(k2) entonces decimos que se produce una
colisión.
Es matemáticamente imposible que una función de hash carezca de colisiones, ya que el
número potencial de posibles entradas es mayor que el número de salidas que puede producir
un hash.

El principal objetivo de una función de hash es minimizar la probabilidad de colisión sin ocupar
memoria innecesariamente. Existen distintos métodos pero en la práctica nunca se utiliza uno
en particular sino una combinación de varios de acuerdo a la aplicación que se esté analizando.

Objetivos de una función de hash a tener en cuenta:

- Debe minimizar las colisiones
- Distribuye de manera uniforme los valores hash
- Facil de calcular
- Puede resolver cualquier colisión
Número máximo de elementos (maxtab)
Si llamáramos maxrec al número máximo de registros de la tabla, maxtab es un número primo
cercano y mayor a maxrec.
Ejemplo práctico: si maxrec=300, tendríamos maxtab=307

Factor de Carga (Load Factor)

En Hashing el factor de carga es una medida que indica cuándo incrementar la capacidad de la
Tabla de Hash para mantener las complejidad de las operaciones de búsqueda e inserción en
𝑂(1)
Se calcula de la siguiente manera:
𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑖𝑡𝑒𝑚𝑠 𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝑙𝑦 𝑖𝑛 𝑡ℎ𝑒 𝑡𝑎𝑏𝑙𝑒
𝑙𝑜𝑎𝑑 𝑓𝑎𝑐𝑡𝑜𝑟 = 𝑠𝑖𝑧𝑒 𝑜𝑓 𝑡ℎ𝑒 𝑡𝑎𝑏𝑙𝑒

Método de la división o módulo

Una técnica estándar consiste en utilizar la función módulo como función de hash. Las entradas
son la representación numérica de la clave y maxtab.
Una desventaja de este método es que la división es una operación microprogramada en
muchos procesadores modernos y más lenta que la multiplicación en un orden de X10.
Ejemplo práctico:
- La clave es 2866 y maxtab = 947. Hash(2866) = 25. Dado que el resto al dividir 2866
entre 947 es 25.

Método del cuadrado medio

Para producir el código hash, este método consiste en elevar al cuadrado la representación
numérica de la clave, para obtener un valor entre 1 y maxtab de los dígitos medios del valor
obtenido.
Ejemplo práctico:
- La clave=123456789 y maxtab=10.000. Al elevar la clave al cuadrado obtenemos
15241578750190521, de los cuales tomamos los dígitos medios, en este caso: 8750.
- La clave es 2866 y maxtab = 947. La clave al cuadrado es 8213956 por lo que
Hash(2866) = 139.

Este método produce claves aceptables cuando no existen muchos 0 hacia la izquierda o
derecha de la clave.

Método de dobles (Folding)

Consiste en dividir la cantidad de dígitos del valor numérico de la clave en dos o más partes
iguales y realizar una operación XOR (or exclusivo) o ADD con el valor binario de cada una de
esas partes.
Ejemplo práctico:
- si maxtab = 947 y se quiere hallar el valor de la clave 2866
- Se divide la clave en dos partes: a1 = 28 y a2 = 66.
 - El valor binario de a1 es = 11100
- El valor binario de a2 es = 1000010
- La operación XOR aplicada sobre los valores binarios de a1 y a2 dará un valor de
subíndice en binario = 1011110 que pasado al sistema decimal es igual a :
- Hash(2866) = 94

Clustering
Es un tipo de falla asociada a las soluciones de direccionamiento abierto que se aplican para
las colisiones.
Este fenómeno ocurre de la siguiente manera al tratar una colisión:
1. La función de hash arroja el mismo hash value para 2 registros distintos => colisión.
2. Se busca una posición contigua no ocupada para la clave que colisionó.
3. El cluster formado por estos registros es probable que crezca aún más por nuevas
colisiones.
4. De esta forma, puede suceder que los valores hash se terminen agrupando dentro de
ciertos valores y el resto de la tabla permanezca sin ocuparse.
5. Este fenómeno termina alargando el tiempo de las búsquedas.

Tratamiento de colisiones

Soluciones Estáticas
Utiliza lo que se llama Rehashing o Direccionamiento abierto (open addressing), lo cual
consiste en la utilización de una segunda función de hash hasta que se encuentre una posición
libre.
Soluciones de rehashing:
1. Trivial (linear probing): es la llamada solución lineal; si la posición de la tabla de
direcciones, table(dir), en el valor de subíndice obtenido al aplicar la función de hash a
una clave, dir, está ocupada, se ocupa la siguiente posición libre de la tabla. rhash(i) =
(i+1) % maxtab
 2. Generalización de la solución lineal: Luego de aplicar Hash(key) = dir, resulta que dir
es una posición ocupada, se aplica nuevamente una función de hash sobre la hash
value anteriormente obtenida: rhash(dir) = (dir + c) mod maxtab donde c y maxtab son
números primos.
3. Doble hashing (para evitar el clustering): Este método utiliza en la función de
reasignación otra función de hash independiente que toma como argumento el valor de
la clave.
4. Hacer depender la función de reasignación del número de veces que es aplicada.
De esta manera, rhash(dir, arg1) tendrá dos argumentos. rhash(dir, i) = (i+1) * dir mod
maxtab donde i es una variable inicializada en 1.
Problemas y observaciones de soluciones estáticas
El principal problema del método de direccionamiento abierto, es que se basa en el uso de una
estructura estática, es decir una tabla, la cuál debe ser dimensionada previamente y que en
ocasiones puede resultar chica, en cuyo caso se deberá crear una tabla más grande y
reorganizar todos los punteros en función del nuevo valor que tome maxtab.
Otro problema es la dificultad que se presenta al dar de baja un elemento de la tabla. Este tipo
de inconvenientes podría solucionarse con el uso de marcas de estado pero el proceso de
recuperación sería cada vez más complejo y se perdería de vista los objetivos principales que
se plantearon en un comienzo respecto de disminuir la cantidad de accesos y disminuir el
espacio utilizado por las estructuras de datos auxiliares.
Debe prestarse especial atención en el diseño del proceso de reasignación pues puede darse
el caso de que un algoritmo busque eternamente un elemento disponible en la tabla o que
informe que no hay más espacio disponible cuando en realidad sí hay elementos vacíos. Un
ejemplo claro de una función de reasignación que pueda llegar a conclusiones equivocadas es
la función rhash(dir) = dir + 2. En este caso, llevado al extremo, puede darse que todos los
elementos de la tabla con subíndice par estén ocupados, que los impares estén vacíos y la
función indique que no existe más espacio disponible.
Soluciones Dinámicas
También llamado direccionamiento cerrado (closed addressing) consiste en utilizar
encadenamiento (chaining) método que se basa en enlazar entre sí los distintos pares de
clave/puntero que colisionan 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, lo que se conoce como “separate chaining”.

Hashing into buckets (separate chaining)

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, conocida como área base, y una lista
linkeada, área de overflow, cuyo registro tiene tres campos. En uno se guarda la clave, en el
otro se guarda la dirección en donde residen los datos y en el tercer campo se guarda la
dirección del próximo registro con igual valor inicial de subíndice dir.
Procedimiento:
Cuando una función de hashing aplicada a una clave devuelve un elemento de tabla que fue
ocupado previamente por otra clave, el proceso pide entonces una dirección de memoria para
guardar los datos de la segunda clave y establece la relación mediante un link entre la primera
clave, cuyos datos se encuentran en la tabla en el área base, con la segunda clave, situada en
la lista linkeada en el área de overflow. Si se quisiera dar de baja el nodo, simplemente habría
que dar una baja en la lista.

Problemas y observaciones de soluciones dinámicas

La principal desventaja de este procedimiento es que se utiliza espacio para los punteros, pero
comparado con el método de direccionamiento abierto, es posible construir una tabla principal
más pequeña con el consecuente ahorro de espacio y sin el problema que se presenta al tener
todas las entradas de la tabla ocupadas. En este caso, deberá medirse la eficiencia del
procedimiento a través de la cantidad de accesos que deberán realizarse, es decir la cantidad
de nodos a recorrer en la lista, para hallar una clave dada. Si el número de nodos es muy
grande, se perderá mucho tiempo en recuperar un dato, con lo cuál habría que rediseñar la
función de hashing inicial o el tamaño de la tabla principal.
Comparativa entre las soluciones

Soluciones Estáticas Soluciones Dinámicas

- Llamado direccionamiento abierto - Llamado direccionamiento cerrado u

(open addressing), closed hashing o open hashing.
reshasing - Las claves siempre se almacenan al
- A lo sumo una clave por entrada de la índice que mapean dentro de la tabla
tabla de hash hash. Puede tener un número
- Cuando sucede una colisión se busca arbitrario de claves por entrada y para
otra entrada vacía dentro de la tabla ello se utiliza una estructura auxiliar la
hash cual es una lista enlazada.
- Cuando sucede una colisión, se utiliza
una lista enlazada para mantener las
claves que mapean a esta entrada

- Factor de carga máximo teórico de 1 - No tiene un factor de carga máximo

teórico

- El rendimiento se reduce cuando

incrementa el load factor

Hash Dinamico
Las tablas hash se presentaron como una alternativa hacia las estructuras tipo árbol ya que
permitían el almacenamiento de grandes volúmenes de información y algoritmos eficientes para
la administración sobre estas estructuras (inserción, eliminación y búsqueda).
Sin embargo, presenta 2 grandes problemas:
 1. No existen funciones hash perfectas que permitan asegurar que por cada
transformación de un elemento habrá una única correspondencia en la clave que
contiene este elemento.
2. Son estructuras estáticas que no pueden crecer ya que necesitan un tamaño fijo para el
funcionamiento de la estructura.
Para solucionar el segundo problema se implementa la utilización de métodos totales y
métodos parciales. Convirtiendo la tabla hash en una estructura dinámica capaz de almacenar
un flujo de información y no una cantidad fija de datos.

Métodos Totales
Método de las expansiones totales
El método de las expansiones totales consiste en realizar una duplicación del tamaño del
arreglo establecido para realizar la tabla hash, esta expansión se ejecuta cuando se supera la
densidad de ocupación . Así si se tiene una tabla hash de tamaño N, al realizar la expansión
total se obtendrá una tabla hash de 2N, al realizar una segunda expansión se obtendrá una
tabla hash de 4N, al realizar una tercera expansión se obtendrá una tabla hash de 8N y en
general el tamaño de la tabla para una i­ésima expansión se define como aparece a
continuación:
𝑖
𝑇 = 2 *𝑁
Dónde:
N: Tamaño de la Tabla.
i: Número de expansiones que se quieren realizar.
T: Nuevo tamaño de la Tabla.
La densidad de ocupación se define como el cociente entre el número de registros ocupados y
el número de registros disponibles; así se tiene que:
𝑟𝑜
𝑝𝑜 = ( 𝑟𝑑 ) * 100
Dónde:
po: Densidad de ocupación
ro: Registros Ocupados
rd: Registros Disponibles.
Cada vez que se pretende insertar un elemento es necesario calcular la densidad de
ocupación, si se supera esta densidad se procede a implementar la expansión. Al realizar cada
una de las expansiones es necesario volver a implementar la función hash para cada uno de
los registros almacenados en la tabla y volver a insertarlos de nuevo en la tabla.

Método de las reducciones totales

Este método surge como una consecuencia del método de expansiones totales presentado
anteriormente. En este método la densidad de ocupación disminuye de tal manera que acepta
una reducción del tamaño de la tabla hash a la mitad. Así si se tiene una tabla hash de N, la
primera reducción dará como resultado la N/2, la segunda reducción dará como resultado N/4,
la tercera reducción dará N/8 y la i­ésima reducción dará como resultado:
 𝑁
𝑇= 𝑖
2
Dónde:
N: Tamaño de la Tabla.
i: Número de expansiones que se quieren realizar.
T: Nuevo tamaño de la Tabla.
Para realizar una reducción la densidad de ocupación se debe disminuir a un valor menor al
rango establecido y los registros se deben eliminar de tal manera que los registros resultantes
se puedan ingresar en una tabla hash que posea la mitad del tamaño de la tabla original. Cada
vez que se implementa una reducción es necesario volver a utilizar la función hash con cada
uno de los registros almacenados.

Métodos Parciales
Método de las expansiones parciales
El método de las expansiones parciales consiste en incrementar en un 50% el tamaño del
arreglo establecido para realizar la tabla hash, esta expansión se ejecuta cuando se supera la
densidad de ocupación. Así si se tiene una tabla hash de tamaño N, al realizar la expansión
parcial se obtendrá una tabla hash de 1.5 N, al realizar una segunda expansión se obtendrá
una tabla hash de 2.25 N, al realizar una tercera expansión se obtendrá una tabla hash de
3.375 N y en general el tamaño de la tabla para una i­ésima expansión se define como:
𝑖
𝑇 = 1. 5 * 𝑁
Dónde:
N: Tamaño de la Tabla.
i: Número de expansiones que se quieren realizar.
T: Nuevo tamaño de la Tabla.
Cada vez que se pretende insertar un elemento es necesario calcular la densidad de
ocupación, si se supera esta densidad se procede a implementar la expansión. Al realizar cada
una de las expansiones es necesario volver a implementar la función hash para cada uno de
los registros almacenados en la tabla hash y volver a insertarlos de nuevo en la tabla.

Método de las reducciones parciales

Este método surge como una consecuencia del método de expansiones parciales. En este
método la densidad de ocupación disminuye de tal manera que acepta una reducción del
tamaño de la tabla hash al 50%. Así si se tiene una tabla hash de N, la primera reducción dará
como resultado la 0.5 N,la segunda reducción dará como resultado 0.25 N, la tercera reducción
dará 0.125 N y la i­ésima reducción dará como resultado:
𝑖
𝑇 = 0. 5 * 𝑁
Dónde:
N: Tamaño de la Tabla.
i: Número de reducciones que se quieren realizar.
T: Nuevo tamaño de la Tabla.
Para realizar una reducción la densidad de ocupación debe disminuir a un valor menor al rango
establecido y los registros se deben eliminar de tal manera que los registros resultantes se
puedan ingresar en una tabla hash que posea la mitad del tamaño de la tabla original. Cada
vez que se implementa una reducción es necesario volver a utilizar la función hash con cada
uno de los registros almacenados.

Comparación entre B-Tree y Hash table

B-TREE HASH TABLE

- Soporta búsquedas por igualdad y - No soporta búsqueda por rangos

rango - Soporta búsquedas por igualdad
- Soporta múltiples claves y búsquedas - No soporta búsquedas por claves
por claves parciales (es decir, sin parciales
considerar todas las claves del índice) - Requiere menos espacio de
- Responde a cambios dinámicos en almacenamiento
las tablas - En bases de datos el optimizador no
- Se puede utilizar ya sea para índices puede hacer uso de estos tipos de
o como base para estructuras de índices cuando una consulta contiene
almacenamiento la cláusula ORDER BY y la columna
- Ejemplo, las Index Organized Tables de ordenamiento es una columna
(IOT) de Oracle utilizan estructuras indexada por este método
B*Tree

UNIDAD III - DISEÑO DE DATOS

Modelo Semántico. Análisis de Datos. Modelo de Datos. Entidad-Relación.
Identificadores y atributos. Definición de claves. Redundancia y consistencia.
Dependencia Funcional. Normalización de Datos. Arquitectura de Datos. Nivel externo.
Nivel conceptual. Nivel interno. Concepto Cliente Servidor. Modelo de Objetos.
Propiedades de los objetos. Análisis de Datos Orientado a Objetos.
Modelo Relacional
En el año 1978 Edgar F. Codd mientras trabajaba para IBM inventó el modelo relacional el cual
representa todos los datos en términos de tuplas las cuales son agrupadas en relaciones, lo
llamó así ya que está basado en el álgebra relacional y teoría de predicados. Este modelo
venía a resolver problemas como la falta de criterios de estandarización, problemas de
consistencia e integridad de datos.
Es un modelo declarativo (no describe el flujo de control), es decir, los usuarios especifican qué
información debe contener la base de datos y qué información quieren consultar y dejan en
manos del DBMS los procesos internos para almacenamiento y consulta de datos.

Elementos del Modelo Relacional

- Relación: conjunto de tuplas donde no importa su orden, una tabla es la representación
visual de una relación.
- Tuplas: conjunto de atributos ordenados (columnas), es decir, es similar al concepto de
fila.
- Atributos: características de interés que tienen un nombre de atributo y un dominio.
- Dominio: o tipo de dato es quien acota el conjunto de valores posibles, ejemplo, Edad
(Integer): enteros positivos mayores a cero. Es el elemento más básico o bloque
constructor del modelo relacional.
Claves y restricciones
- Valor Nulo: representa missing values o valores desconocidos, se agrega a la tabla de
verdad de proposiciones lógicas.

- Clave Primaria (Primary Key - PK): Atributo o conjunto de atributos (en el que ninguno
puede ser nulo) que identifica unívocamente a cada tupla. Debe cumplir con
minimalidad y unicidad.
- Clave Foranea (Foreign Key - FK): Atributo o conjunto de atributos que es clave
primaria en otra relación y permite implementar el concepto de integridad referencial.
Tiene 3 opciones; RESTRICT, CASCADE, ANULACIÓN (ON DELETE SET NULL).

Caracteristicas
- Integridad referencial: es la característica que garantiza que la relación entre dos
tablas permanezca sincronizada en las operaciones de manipulación de datos, es decir,
al realizar una operación de inserción, actualización o eliminación se verifica que la tupla
o fila a la que hace referencia exista y sea válida.
- Independiente de la implementación: es independiente de la implementación física,
está abstraída.
- Independiente del Orden: los elementos de las relaciones no tienen un orden
determinado.
 - Las tablas o relaciones deberían estar normalizadas.

Normalizacion
Proceso iterativo utilizado para quitar redundancias y mejorar la integridad de los datos en un
modelo relacional.
Su principal objetivo es remover del modelo las dependencias que requieran realizar
inserciones, actualizaciones o eliminaciones en unas relaciones cuando otras se modifican.
También se busca evitar tener que reestructurar las relaciones a medida que se agregan
nuevos atributos.

Primera Forma Normal 1FN - (First Normal Form):

Una tabla está en primera forma normal si todos sus atributos son de valor único (no tiene
atributos compuestos) y no tiene atributos repetitivos.
Además cada registro debe ser único, cualidad garantizada si la tabla tiene una PK.

Segunda Forma Normal - 2FN (Second Normal Form)

Una tabla está en Segunda Forma Normal si se encuentra en 1FN y además, todos los
atributos no clave dependen en su totalidad de la PK.
Dicho de otra forma, la tabla no contiene atributos con dependencias parciales (llamada
dependencia funcional), caso que podría darse si la PK es compuesta.

Tercera Forma Normal - 3FN (Third Normal Form)

Una tabla está en 3FN si se encuentra en 2FN y además, ningún atributo No clave depende de
algún otro atributo no clave, lo que se conoce como dependencia transitiva.

Ejemplo Práctico
Un videoclub almacena toda su información en una tabla sin normalizar.

Procedemos a aplicar 1FN y trabajamos primero sobre el campo multivalor “Movies Rented” y
nos queda:
Luego vemos que para identificar unívocamente un registro no podemos utilizar solo el nombre
porque se repite, por lo que también utilizamos la dirección:

Finalmente la PK queda formada por los campos “Full Name” y “Physical Address” y es una PK
compuesta.

Ya tenemos la tabla en 1FN, podemos aplicar 2FN, para ello hay que deshacerse de la
dependencia funcional. Aquí el atributo “Movies Rented” depende de un subset de la PK, es
decir, sólo depende del nombre de la persona que alquiló la película, y no de la dirección.
Para solucionar esto partimos la tabla en dos, y además por conveniencia agregamos un id
(que será nuestra nueva PK en la tabla 1) a cada persona que alquila películas en nuestro
videoclub de manera de identificarlos unívocamente de manera más fácil y utilizar este campo
para la integridad referencial.

Observar que el campo “Membership Id” de la tabla dos es FK hacia la PK de la tabla 1.

Las FK garantizan la integridad referencial, si alguien quiere insertar en la tabla 2 un registro
para un miembro no registrado en la tabla 1 el DBMS nos informará el error.

Para dejar la tabla en 3FN debemos quitar la dependencia transitiva, en nuestro escenario la
tenemos entre los campos no clave “Full Name” y “Salutation”, si se realiza un cambio del
primero por consiguiente deberíamos actualizar también el segundo, si no lo hiciéramos
tendríamos un problema de consistencia.
Se llama dependencia transitiva ya que como podemos ver “Salutation” depende de “Full
Name” quien a su vez depende de la clave “Membership Id”, del modo
𝑠𝑖 𝐴 ⇒ 𝐵 𝑦 𝐵 ⇒ 𝐶 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝐴 ⇒ 𝐶. Para solucionar esto partimos nuevamente la tabla como
sigue:

Donde las diferentes opciones de saludo pasan a estar parametrizadas en una nueva tabla
indexadas por su correspondiente ID. Luego se cambia el atributo “Salutation” en la tabla
original para que contenga la referencia al ID correspondiente.

Arquitectura de Aplicaciones

Monocapa

- Sistemas monousuarios monolíticos también denominados aplicación desktop.

- Consisten en una aplicación en la PC del usuario
- La base de datos, lógica de aplicación y presentación se encuentran almacenadas en el
mismo programa, no hay separación en capas.
Ventajas
- Relativamente fácil de construir y deployar
- Acceso directo a datos es rápido
Desventajas
- Acoplado al sistema operativo
- Poca o Nula escalabilidad
- Portabilidad requiere reescribir el sistema
- Alto acoplamiento entre bases de datos, lógica de aplicación y presentación, cambiar
una requiere potencialmente cambiar las otras lo que dificulta el mantenimiento.

Cliente-Servidor
- Arquitectura de 2 capas
- Capa de front-end o presentación instalada en el cliente (que puede ser pesado o ligero)
que se comunica con la capa de datos que se encuentra en el servidor.
- Son casi siempre multiusuario.
- El cliente envía requests (solicitudes) de información al servidor quien procesa y envía
una respuesta.
- La lógica de negocio puede estar distribuida entre la aplicación instalada en el cliente y
el servidor (implementada como por ejemplo, stored procedures).
Ventajas
- El servidor permite la concurrencia, es decir, que múltiples usuarios accedan a los
datos en simultáneo y al mismo tiempo resuelve cualquier problema de integridad de
los datos.
- Al separar responsabilidades el mantenimiento se hace más fácil.

Desventajas
- El cliente (cliente pesado) debe contar con suficientes recursos para correr la
aplicación que se instalará en él.
- Aumenta la complejidad de actualizaciones y seguridad

Multicapa
- Compuesto por tres capas:
- Aplicación Cliente: puede ser de instalable de escritorio (desktop) o web
accedida mediante un navegador.
- Servidor de aplicaciones: servidor donde se concentra la lógica de negocio o
lógica de aplicación.
- Capa de Base de Datos
 -
Ventajas
- El cliente solo posee una interfaz del sistema reduciendo el consumo de recursos
(cliente liviano).
- Lógica de negocio implementadas en el servidor de aplicaciones.
- Mejora el encapsulamiento y seguridad alejando al cliente de la capa de datos, el
cliente solo puede comunicarse con el servidor de aplicaciones y este es quien accede
a los datos.
- Reduce el acoplamiento y permite la escalabilidad horizontal.
Desventajas
- Más complejo de implementar.

Sistema de Administración de Bases de Datos (DBMS - Database

Management System)
Capa de software que permite realizar distintas operaciones en la BD, desde manipulación de
datos (persistencia y modificación) hasta administración de la propia estructura de la Base de
Datos (DDL para usuarios, datafiles, tablespaces, etc).
ACID (Atomicity Consistency Isolation Durability)

Para que un producto se considere DBMS debe cumplir con la propiedades ACID, en español
representan Atomicidad, Consistencia, Aislamiento, Durabilidad.
- Atomicidad: propiedad que garantiza que una operación o transacción se complete
enteramente o no, es decir, garantiza que una operación no pueda quedar a medias.
Por ejemplo, una transacción bancaria precisa ser atómica ya que el depósito en una
cuenta destino y deducción de la cuenta origen necesitan ocurrir en conjunto, ocurren
ambas o ninguna.
- Consistencia: también llamada integridad, propiedad que asegura que se ejecutarán
operaciones que no rompan reglas y directrices de integridad de la BD. Esta propiedad
sostiene que cualquier operación consistente llevará la BD de un estado valido a otro
estado valido.
- Aislamiento: propiedad que garantiza que una operación no puede afectar a otras.
Asegurando que dos transacciones sobre el mismo conjunto de datos son
independientes y no generen ningún tipo de error. Define cómo y cuándo los cambios
producidos por una transacción se hacen visibles para las demás transacciones
concurrentes.
- Durabilidad: también llamada persistencia, propiedad que garantiza que los datos una
vez confirmada (commit) la operación se preservarán en el tiempo.
Arquitectura ANSI - SPARC

ANSI SPARC es una arquitectura de DBMS. Fue creada por ANSI y sirve como una
estandarización de las arquitecturas de DBMS.
El DBMS se encarga de coordinar la acción de los tres niveles que componen
ANSI-SPARC.

Nivel Externo:
- El nivel externo comprende las vistas que los usuarios tienen de la base de
datos, es decir, la abstracción que se le permite ver al usuario de toda la base
de datos (depende de factores como la relevancia de los datos para el usuario)
- Diferentes vistas externas pueden usar el mismo nivel conceptual para satisfacer los
requerimientos de distintos usuarios.
- También llamado vista externa, nivel de vistas o esquema externo.

Nivel Conceptual:
- El nivel conceptual comprende la forma lógica en que todos los datos se
almacenan, sus relaciones y las reglas de integridad.
- Permite ocultar detalles físicos al nivel externo y trabajar con elementos lógicos como
tablas, relaciones.
- Nivel de abstracción utilizado por el DBA o arquitectos de datos quienes toman
decisiones como por ejemplo sobre qué información mantener en la Base de Datos.
- Conocido como vista lógica o simplemente esquema.
Nivel Interno:
- Comprende la forma física en que los datos se organizan y se almacenan.
- Incluye técnicas de compresión, almacenamiento y encriptamiento de datos.
- Generalmente dependiente del software y dispositivos de almacenamiento secundario.

Ventajas
- Abstracción: oculta los detalles de cómo la base de datos almacena los datos
físicamente. Esto hace que el usuario tenga menos en lo que pensar y pueda enfocarse
en sus tareas.
 Usuarios finales y desarrolladores de aplicaciones pueden enfocarse en los datos que
desean consumir.
Los Arquitectos de Datos pueden concentrarse en las entidades y relaciones del modelo
de manera de mejorar la integridad de los datos.
DBA puede centrarse en la organización física de los datos (datafiles, tablespaces) y
supervisar el rendimiento del DBMS en general.
- Portabilidad: la base de datos es la misma en todos los sistemas, por lo que
hace fácil la migración .
- Independencia lógica: un cambio o actualización en el nivel conceptual no
modifica el nivel externo.
Por ejemplo, agregar una nueva entidad o quitar una relación del nivel conceptual no
interfiere con el nivel externo ya que los usuarios solamente ven lo que necesitan, por
ejemplo, un usuario sabe nada más que le puede pedir a la base de datos una
lista de clientes y sus nombre pero no sabe ni cómo está guardada, ni que existen
más campos, etc.
- Independencia física: un cambio o actualización en el nivel interno no modifica el
nivel conceptual ni externo.
Por ejemplo, el tipo de almacenamiento secundario utilizado (HDD o SSD) debe ser
indistinto para el nivel conceptual y externo.

UNIDAD IV - BASES DE DATOS

Concepto de Base de Datos. Tipos de Bases de Datos. Modelo en Red (IDMS). Modelo
Jerárquico (IMS). Modelo de lista invertida (DATACOM/DB). Modelo Relacional. Modelo
orientado a objetos. Concepto de SQL. Concepto de PL-SQL. Recuperación y
Concurrencia, Seguridad e integridad de los datos. Aplicaciones con SQL y PL-SQL.

Concepto de Base de Datos

Una Base de datos es un conjunto de datos persistentes ,organizados e interrelacionados que

utilizan los sistemas de aplicación de empresas, los datos se almacenan en conjuntos
independientes y sin redundancia, se compone de:
- Datos: los cuales tienen la característica de ser integrados (minimizan la redundancia) y
compartidos (muchos usuarios pueden accederlos concurrentemente).
- Procesos/Programas: el propio software del DBMS es el más importante pero también
tenemos librerías de funciones, herramientas de desarrollo, de reportería ,etc . Los
 Procesos controlan el DBMS y abstrae al usuario de los detalles tecnológicos
brindándoles los servicios que precisa (ofrece una percepción de alto nivel de la BD).
- Usuarios: hace referencia al programador de aplicaciones, DBA, y usuarios finales.
- Tecnología: conformado por equipamiento de hardware (discos de almacenamiento
secundario, memoria RAM y procesadores) y el Sistemas Operativo son parte de los
recursos necesarios sobre el que corre el DBMS.

Funciones del motor de Base de Datos y del DBMS en su conjunto

1. Diccionario de Datos: Mantenido por el DBMS, son metadatos accesibles mediante
vistas a los usuarios, brindan información sobre la base de datos, sus objetos,
seguridad, etc. Son mantenidas automáticamente, no pueden ser modificadas por
usuarios de forma explícita.
2. Control de Seguridad: implica que los usuarios tengan autorización para realizar
determinadas acciones. Para ello contamos con el sublenguaje de sentencia de DCL
(Data Control Language) donde las más importantes son GRANT y REVOKE. Creación
y asignación de perfiles y roles a los usuarios. También existen otros mecanismos de
seguridad como los objetos (vistas, triggers, sinónimos, SP’s) o en Oracle VPD.
3. Mecanismos para brindar integridad y consistencia
- Transacciones: son operaciones que se realizan de forma atómica, es decir, se
ejecutan correctamente o fallan, no dejan nada a medias, lleva la BD de un
estado correcto a otro estado correcto. Las sentencias TCL principales son
COMMIT y ROLLBACK. Las transacciones deben cumplir con las propiedades
ACID.
- Constraints (Restricciones): controles que permiten implementar verificaciones
automáticas sobre los datos, por ejemplo, NOT NULL verifica que el atributo
contenga un valor, PRIMARY KEY que los valores sean únicos y no nulos. Otras
restricciones son FOREIGN KEY, CHECK, UNIQUE, DEFAULT.
- Triggers: Son procedimientos almacenados que se disparan ante determinados
eventos. Por ejemplo por detectar determinada sentencia DML sobre un objeto
de base de datos o por detectar la conexión de un usuario del cual queremos
persistir la información de log.
- Logical logs: registros de log donde el DBMS almacena la traza de las
operaciones y eventos sucedidos en la BD.
4. Backup and Recovery: Son utilidades para respaldo de datos y recuperaciones ante
caídas.
- Recovery: es un mecanismo de tolerancia a fallas que utiliza los logs para llevar
la Base de Datos al último estado consistente y válido conocido.
- Backup: consiste en volcar total o parcialmente la BD en otro sistema de
almacenamiento masivo de respaldo, hay diferentes tipos los cuales son:
- Completo (full): respaldo de toda la base de datos.
- En caliente: se realiza con usuarios conectados y el sistema está arriba
(UP).
- En frío: se desconectan los sistemas de acceso a la BD.
 - Backup de Logs Transaccionales: sobre logs transaccionales.
- Diferencial Incremental: se toma como punto de partida un backup
anterior (no importa si fue full o incremental). Se realiza cuando el tiempo
es un limitante.
- Diferencial Acumulativo: a partir de los cambios que hubo en un backup
Full anterior.

5. Administración de la Organización Física de los datos en disco y/o memoria: cada

distribución de DBMS tiene su propia forma de hacer uso de los recursos que el sistema
le brinda, aquí entran una serie de consideraciones como ser:
a. El tamaño de la página y mecanismo de paginación
b. Tamaños de los buffers de disco
c. Tamaño de la memoria compartida
d. Administración de la memoria
e. Manejo de extents y datafiles
f. Fragmentación de las tablas
6. Conectividad: el motor de DBMS mantiene un pool de conexiones para usuarios y
aplicaciones. La conexión puede ser a través de distintos mecanismos como ODBC
(Open DataBase Connectivity).
7. Administración de recursos: los DBMS proporcionan utilitarios que permiten
monitorear los recursos de la BD.
8. Concurrencia de lectura y actualizaciones: como las BD son sistemas multiusuarios
deben proporcionar mecanismos que permitan mantener la integridad y consistencia de
los datos mientras los distintos usuarios los acceden y modifican. También deben poder
realizar tratamiento sobre deadlocks. Para ello cuentan con mecanismos como bloqueos
y niveles de aislamientos:
- Bloqueos (Locks):
- Compartido: se reserva el recurso para lectura (SELECT) de modo que
otros no puedan modificarlo, varios recursos pueden solicitar este
bloqueo. Las transacciones que deben modificar datos bloqueados
esperan hasta que se libere el bloqueo.
 - Exclusivo: se reserva el acceso únicamente para quien impuso el
bloqueo, se utiliza en sentencias DELETE, INSERT y UPDATE.
Normalmente se aplica a nivel de filas. Se libera al finalizar la
transacción.
- Promovido
- Granularidad de bloqueos
1. Lockeos a nivel de BD
2. Lockeos a nivel tabla
3. Lockeos a nivel página
4. Lockeos a nivel fila

- Tipos de Lecturas:
- Sucia: permite leer datos que fueron modificados por otra transacción
concurrente aún no confirmada.
- No Repetible: ocurre cuando durante una transacción una fila se lee dos
veces con valores no coincidentes deB bido a que otras transacciones
posiblemente modificaron los datos.
- Fantasma: es un caso particular de lectura no repetible, durante una
transacción se realizan dos consultas idénticas y sus resultados no
coinciden. En este caso pueden haberse añadido datos desde otras
transacciones y estos datos cumplen los criterios de las consultas.
- Niveles de Aislamiento: a continuación se listan desde el más permisivo al más
restrictivo.
- Read Uncommitted (RU): es el más permisivo, permite leer cambios que
no fueron confirmados, se pueden producir lecturas sucias, no repetibles
y lecturas fantasma. No aplica locks por SELECT.
- Ve INSERT/UPDATE/DELETE confirmados y no confirmados
- Un SELECT no bloquea la tabla de la que tomó los datos
- Read Committed (RC): modo defecto de muchos DBMS asegura que no
existan lecturas sucias, no garantiza lecturas repetibles. Aplica el lock
durante la lectura, luego libera.
- Solo ve INSERT/UPDATE/DELETE confirmados
- Un SELECT no bloquea la tabla de la que tomó los datos
 - Repeatable Read (RR): bloquea los registros seleccionados para lectura
y escritura. Asegura que no sucedan lecturas sucias y las lecturas son
repetibles (al estar los registros bloqueados dos lecturas secuenciales
arrojarian los mismos resultados), no garantiza que no sucedan lecturas
fantasmas.
- No ve INSERT/UPDATE/DELETE no confirmados
- No ve UPDATE/DELETE confirmados
- Ve INSERTS confirmados
- Un SELECT bloquea los registros seleccionados para
UPDATE/DELETE pero permite hacer SELECT/INSERT.
- Serializable Read (SR): es el único que asegura que no existan lecturas
sucias, ni lecturas fantasmas y que las lecturas puedan ser repetibles.
Puede afectar a otros usuarios en sistemas multiusuario debido a los
bloqueos ya que las transacciones se procesan en serie una después de
otra.
- No ve INSERT/UPDATE/DELETE ya sean confirmados o no
confirmados
- Un SELECT bloquea los registros seleccionados para
INSERT/UPDATE/DELETE solo permite hacer lecturas SELECT

Explicacion; Repeatable read vs Serializable Read

Lectura Sucia Lectura Lectura
Repetible Fantasma

Read Si No Si
Uncommitted

Read No No Si
Committed

Repeatable No Si Si
Read

Serializable No Si No
Read

9. Facilidades de Auditoría: log de registro de uso de recursos y otros.

10. Logs del sistema: permiten monitorear y detectar causas de posibles caídas.
11. Optimización de consultas: módulo del DBMS que se encarga de seleccionar el mejor
plan de ejecución lo que permite mejorar la performance de las consultas.
Hay muchos algoritmos diferentes para resolver los joins (nested-loop join, hash join,
sort-merge join).
 12. Creación de triggers y stored procedures: son procedimientos almacenados, código
escrito en lenguajes como PL/SQL o T-SQL que son extensiones de SQL y que tienen
la posibilidad de almacenarse como objetos de base de datos para aplicar lógica de
negocio sobre la capa de datos.
13. Data replication y Data Encryption: permiten mejorar la disponibilidad y seguridad
respectivamente.

¿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?
Porque:
● 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.

Tipos de Bases de Datos

NoSQL

También llamados Bases de Datos No Relacionales, es una amplia categoría que incluye BD
que no usan SQL para interactuar con la base de datos. Ideales para almacenar datos
semi-estructurados o no estructurados.
Ejemplos: Apache Cassandra, MongoDB, CouchDB, and CouchBase
Ejemplos de aplicaciones: plataformas de redes sociales utilizan este tipo de BD para
almacenar log de chats, videos e imágenes de sus usuarios.
Cloud DB
Se refiere a cualquier DBMS diseñado para correr en la nube. Son ideales para aplicaciones
que corren en la nube. Ofrece flexibilidad y escalabilidad junto con alta disponibilidad.
Requieren bajo o nulo mantenimiento ya que son ofrecidas a través de modelos SaaS.

Ejemplos: Microsoft Azure SQL Database, Amazon Relational Database Service, Oracle
Autonomous Database, Snowflake.

Object-Oriented DataBases
Asociada a la POO, todos los atributos son asociados a objetos los cuales se persisten.
Son administradas por OODBMS y trabajan bien con lenguajes de programación como C++ y
Java. Como las Bases de Datos Relacionales siguen los estándares ACID.

Ejemplos: Wakanda, ObjectStore, Smalltalk is used in GemStone, LISP is used in Gbase, and
COP is used in Vbase.
Ejemplos de aplicaciones: Algunas de las aplicaciones comunes que usan bases de datos de
objetos son sistemas en tiempo real, arquitectura e ingeniería para modelado 3D,
telecomunicaciones y productos científicos, ciencia molecular y astronomía.

BD’s basadas en Grafos (Graph databases)

Son un tipo de Base de Datos NoSQL que están basadas en la teoría de grafos. Diseñadas
para identificar y trabajar con conexiones entre puntos de datos. A menudo utilizadas para
analizar las relaciones entre datos heterogéneos, como por ejemplo datos de redes sociales.

Ejemplos: Neo4J, Datastax Enterprise Graph

Ejemplos de aplicaciones: Redes Sociales, Detección de Fraude, Sistemas de Recomendación.

Modelo en Red (IDMS)

El Integrated Database Management System (IDMS), es un modelo de Bases de Datos basado
en redes y utilizado principalmente en mainframes.
Los conceptos estructurales principales son records y sets.
En cuanto al almacenamiento, IDMS organiza los datos como un conjunto de archivos los
cuales son formateados y mapeados a las llamadas áreas. Estas últimas se subdividen en
páginas las cuales finalmente se almacenan en los bloques en disco.

OODBMS
Motor de base de datos orientado a objetos.
Almacena los objetos e incorpora todas las características del paradigma lo que
aumenta la flexibilidad y la seguridad. Por ejemplo, herencia, polimorfismo y poder
manejar objetos complejos aumentan la flexibilidad mientras que encapsulamiento
aumenta la seguridad. Las ventajas incluyen la posibilidad de usar los conceptos del paradigma
sin mapeos y de forma fluida (sin ORMs).
Las desventajas incluyen la carencia de estándares, experiencia y la falta de madurez del
paradigma.

Datawarehouse

Base de Datos corporativa que contiene datos históricos para su análisis. Puede integrar datos
de varias fuentes como ser sistemas externos y bases de datos transaccionales. Los datos
suelen ser explotados para la toma de decisiones estratégicas. Existen diferentes modelos:
- ROLAP: Relational Online Analytical Processing, modelo relacional.
- MOLAP: multidimensional.
- HOLAP: hibrido
Los DataWarehouses se crearon con un propósito diferente a las bases de datos
transaccionales:
- Las BD OLTP están diseñadas y optimizadas para cargas de trabajo conocidas, con
tamaños de bloque más pequeños en relación a OLAP así disminuir la fragmentación de
bloques y también posibilitar que la manipulación de datos sea más eficiente.
Orientadas al procesamiento de transacciones de forma eficiente.
- En las BD OLAP buscan mantener y explotar datos históricos, frecuentemente no
normalizados para reducir el número de joins, y se arrojan consultas que exploren tablas
con cientos de miles o millones de registros con tiempos de respuesta aceptables.
Además, en OLAP frecuentemente se integran datos de diferentes fuentes con el fin de
enriquecer la explotación y agregar valor. Orientadas a la reportería, análisis y toma de
decisiones.
Funciones Principales
Las funciones principales de un DW pueden subdividirse en 5 grandes grupos cada uno de
ellos con propósitos específicos.
● Acceso a fuentes (Source)
○ Esta etapa suele consumir hasta el 80% del esfuerzo para poblar el DW. Las
fuentes pueden ser no solo de la organización sino que también pueden ser
externas, como por ejemplo datos de distribución pública, o datos adquiridos a
terceros.
● Carga (Load)
○ Asociada a ETL (Extraction Transformation and Load), son procesos que se
encargan de preparar, depurar y finalmente transferir los datos.
● Almacenamiento (Storage)
○ Abarca la arquitectura de los modelos de datos.
● Consultas (Query)
○ Orientadas al análisis y producción de reportes.
 ● Metadatos (Meta Data)
○ Información descriptiva del contexto, calidad y características de los elementos.
Dicho de otra forma, son datos sobre los datos.
Caracteristicas:
1. Soporta el proceso de toma de decisiones: Es la principal función de un DW.
2. Orientada a sujetos: El DW está orientado a los mayores sujetos (procesos o
departamentos de la empresa) de la empresa para que tomen las decisiones más
convenientes.
3. Integrada: integra los datos de distintas fuentes para que los mismos sean
consistentes.
4. No volátil: Los datos utilizados para la toma de decisiones deben ser estables por lo
tanto no deben modificarse una vez almacenados.

Arquitectura Datawarehouse

Datamart
Vista multidimensional de cada área del DATA WAREHOUSE.
A diferencia del DATA WAREHOUSE, los DATA MARTS:
● Son pequeños sistemas de almacenamiento de datos.
● Se ajustan mejor a las necesidades que tiene una parte específica de la organización.
● Optimizan la distribución de información útil para la toma de decisiones.
● Se enfocan en el manejo de datos resumidos o de muestras (no en la historia en
detalle).
● Son menos costosos y tienen un alcance más limitado que los DW.
● Al igual que el Datawarehouse puede ser implementado en un modelo Relacional
(RDBMS) o multidimensional (MDBMS).

Data Mining
Se refiere a la aplicación de técnicas y tecnología para la búsqueda y explotación de
información implícita que puede ser relevante para el negocio.
- Ayudan a tomar decisiones basadas en los datos (data-driven).
- Exploran las BD en busca de patrones ocultos que pueden ser de interés para
solucionar requerimientos del negocio.
- Busca modelos desconocidos, analiza tendencias y predicciones de comportamiento
que puedan utilizarse y mejorar la toma de decisiones.
- Suelen implementarse y automatizarse.
- Por ejemplo, un Banco puede aplicar Minería de Datos para buscar clientes leales,
encontrar nuevos segmentos de clientes, hallar patrones para detectar fraude, etc.
- Algunas técnicas usadas son redes neuronales y árboles de decisión entre otras.

SNOWFLAKE - STAR
Para implementar un Datawarehouse en un RDBMS se utiliza el modelo estrella (STAR) que se
conforma por dos tipos de tablas; tablas de hechos y tablas de dimensiones.
● Tablas de Hechos (Fact Table): registra medidas (measures) o métricas de un Evento
específico, generalmente consisten de valores numéricos (datos asociados
específicamente con el evento), y claves foráneas que referencian a tablas de datos
dimensionales que guardan información descriptiva.
Se diseñan para contener detalles uniformes a bajo nivel (referidos como "granularidad"
o "grano"), o sea que los hechos pueden registrar eventos a un gran nivel de
atomicidad.
● Tablas de Dimensiones (Dimension Tables): guardan información descriptiva, pueden
definir una amplia variedad de características. Las tablas de Dimensiones generalmente
tienen un bajo número de registros, en comparación a las tablas de hechos, pero cada
registro puede tener un gran número de atributos para describir los datos del hecho.
 STAR SNOWFLAKE

Normalizacion Tablas de dimensión no Tablas de dimensión

normalizadas normalizadas

Redundancia de Datos Alta redundancia de datos Baja o nula redundancia lo

que ahorra espacio de
almacenamiento secundario

Complejidad Consultas relativamente Consultas complejas que

simples que requieren pocos requieren múltiples joins y no
joins y corren rápido corren tan rápido

Casos de Uso Si el foco está en consultas Si el foco está en disminuir la

rápidas de relativa baja redundancia y mejorar la
complejidad integridad de los datos
Objetos de Bases de Datos

Esquemas
En algunos motores como Oracle, el DBMS crea una estructura contenedora llamada esquema
por cada usuario, la misma agrupa todos los objetos propiedad del usuario.

Tablas
Unidad básica de almacenamiento de datos. Poseen nombre identificatorio, filas y columnas
con su correspondiente tipo de datos. Llamadas relaciones en el modelo relacional. Existen
diferentes tipos de estructuras u organizaciones internas de tablas:
- Heap (montón): estructura por defecto en la que se persisten los datos sin un orden
determinado.
- Tablas Organizadas por índice (IOT): los registros son almacenados en una estructura
de índice B-Tree y ordenados por la clave primaria. Cada nodo hoja almacena ambas
columnas clave y no clave. Las principales ventajas es que se reduce el espacio
requerido para almacenar los datos, no requiere una estructura separada para el índice
de la PK y que los datos ya se encuentran organizados. Casos de Uso: para tablas de
lookup cuando los datos son accedidos por la PK y se retornan todas las columnas.
- Tablas externas: característica proporcionada por Oracle que permite leer ficheros
externos formateados como si fueran tablas, tiene limitantes como ser que no se
pueden crear índices ni realizar DML.
- Tablas Temporales: los datos están disponibles durante la duración de la sesión, al
desconectarse los datos son purgados. En algunos DBMS como MS SQL SERVER es
posible separar entre locales y globales, en este último caso los datos son purgados
cuando todos los usuarios referenciando la tabla se desconectan. Caso de Uso: carrito
de compras.
- Tablas Anidadas: algunos DBMS como Oracle brinda la posibilidad de crear tablas
anidadas, en los cuales un atributo de la tabla contiene la especificación de una nueva
dentro de ella.
Clusters
Un cluster es un grupo de tablas que comparten los mismos bloques de datos porque tienen
columnas comunes compartidas y que a menudo se usan juntas.
Beneficios:
- Reducción de E/S a disco para los joins de las tablas agrupadas
- Mejora en tiempos de acceso para los joins de las tablas agrupadas
- En un clúster, el valor de clave de clúster es el valor de las columnas clave del clúster
para una fila en particular. Cada valor de clave del cluster se guarda sólo una vez en el
cluster y en el índice del cluster, independientemente de cuántas filas de diferentes
tablas contengan dicho valor. Por lo tanto, se requiere menos espacio para almacenar
tablas relacionadas e índices de datos en un cluster.

Vistas
Son objetos que permiten almacenar la implementación de una consulta detrás de un
identificador el cual puede consumirse como una tabla, de este modo se pueden disponibilizar
el acceso a consultas complejas a usuarios con poca experiencia en SQL o agregar un control
de seguridad brindándole solo acceso a la vista y no a las tablas subyacentes, pudiendo así por
ejemplo, esconder campos con datos sensibles. La vista no almacena los datos sino que es
una ventana de acceso a la consulta a la cual está asociada.

Vistas materializadas
También llamadas Snapshots son un tipo especial de vistas en la que los datos si son
persistidos en una estructura separada de las tablas que son origen de los datos.
Se suele utilizar para consultas complejas en la que es necesario sumarizar o precomputar
datos y persistir sus valores en el tiempo. Un ejemplo de uso podría ser calcular facturaciones
diarias por sucursales, al almacenarse en una vista materializada que se refresque a cada
cierre de día podría historificar datos de facturación y evitar re-cálculos. Muy utilizados en
Datawarehouse.

Secuencias
Objetos que generan números según una secuencia especificada, un uso común es que sus
valores son utilizados para las claves primarias. Las secuencias permiten especificar valores
mínimos, máximos, valor de inicio e intervalo o salto entre otras opciones.

Indices
Los índices son objetos que son físicamente independientes de los datos en la tabla asociada.
Se puede crear o borrar un índice en cualquier momento sin afectar a las tablas base o a otros
índices.
Su función es la de permitir un acceso más rápido a los datos, se pueden crear distintos tipos
de índices sobre uno o más campos.
En Oracle al crear una clave primaria o clave única el motor crea automáticamente un índice
UNIQUE.
Los índices se mantienen sincronizados con los datos de las columnas a las que están
asociados por lo que deben ser mantenidos cuando se realiza operaciones DML sobre la tabla
base, siendo esto un overhead.

Tipos de Índices
1. Btree Index : Estructura de índice estándar.
2. Btree Cluster Index : La tabla se ordena igual que el índice.
3. Reverse Key Index (Oracle) : Son un tipo de índice B-Tree pero en este caso se
invierte los bytes de la clave a indexar. Esto sirve para los índices cuyas claves son una
serie constante con por ej. Crecimiento ascendente para que las inserciones se
distribuyan por todas las hojas del árbol de índice. Se utiliza para reducir la contención
de bloques.
4. Bitmap Index (Oracle) : Son utilizados para claves con muchas repeticiones de una
serie acotada de valores. Por ejemplo; estado civil, tipo de documento, etc.
Cada bit en el Bitmap corresponde a una fila en particular. Si el bit está en on significa
que la fila con el correspondiente rowid tiene el valor de la clave.
5. Function Base Index (Oracle): Implementa una función que se debe utilizar luego
también en las consultas que se desean que utilicen el índice. Pueden ser B-Tree o
Bitmap.

Características de los Índices

- Unique: cada entrada el índice es única. No admite duplicados.
- Cluster: provoca que al momento de su creación los datos de la tabla sean
reorganizados por el mismo, SQL Server y DB2 tienen este tipo de índices, en Oracle
esto se resuelve con Clusters.
- Comun / Duplicado: permite entradas duplicadas.
- Compuesto: la clave del índice se compone por varias columnas. Se utilizan para
mejorar joins entre múltiples tablas o para incrementar la unicidad o selectividad. Las
columnas más accedidas o más selectivas van al principio de la clave.

Beneficios
Permite aplicar controles de unicidad como así también mejora la performance de las consultas
para columnas que se usan en los siguientes casos:
- Joins
- Filtros
- Ordenamiento
Costos
- Mantención: al realizar operaciones de manipulación de datos es necesario mantener el
índice en sincronización con los datos de la tabla, esto es un overhead que se suma al
tiempo de la transacción.
- Espacio: la estructura del índice requiere espacio adicional.
Sinonimos
Es un alias definido sobre una tabla, vista ó snapshot. Dependiendo el motor de BD puede ser
también definido sobre un procedure, una secuencia, función o package. Se usan a menudo
por seguridad o por conveniencia (por ej. en entornos distribuidos). Permiten enmascarar el
nombre y dueño de un determinado objeto. Proveen de una ubicación transparente para
objetos remotos en una BD distribuida. Simplifican las sentencias SQL para usuarios de la BD.
Pueden ser públicos (visibles para todos los usuarios).

DB Links
Un database link es un puntero que define una ruta de comunicación unidireccional desde un
servidor de base de datos hasta otro. Para acceder al enlace, se debe estar conectado a la
base de datos local que contiene la entrada en el diccionario de datos que define dicho puntero.
Hay dos tipos de enlace según la forma en que ocurre la conexión a la base remota:
• Enlace de usuario conectado: el usuario debe tener una cuenta en la base remota con el
mismo nombre de usuario de la base local.
• Enlace de usuario fijo: el usuario se conecta usando el nombre de usuario y password
referenciados en el enlace.

Disparadores (Triggers)
Tipo especial de stored procedure que se dispara al suceder un evento determinado. Ejemplo,
conexión a la BD de un usuario o DML sobre una tabla o vista (trigger INSTEAD OF)

Directorios
Un directorio especifica un alias para un directorio en el file system del servidor, donde se
ubican archivos binario externos (BFILES) y datos de tablas externas.

Tipos de Datos definidos por el usuario (Object/Record/Collections)

Tipos de datos que pueden agrupar atributos y/o colecciones para ser utilizados en stored
procedures o nested tables.

Stored Procedures
Objetos que son almacenados en las Bases de Datos y que permiten aplicar capacidades de
los lenguajes procedurales como lógica condicional, bucles (loops), manejo de variables. Usan
lenguajes como PL/SQL (Oracle) o T-SQL (Microsoft) que son extensiones de SQL. Tipos de
SP son funciones, procedimientos, paquetes (subprogramas relacionados lógicamente).

Beneficios
- Permiten aplicar reglas de negocio en la capa de datos.
- Pueden reducir la complejidad en la programación. Creando SP con las funciones más
usadas.
- Pueden ganar perfomance en algunos casos
- Otorgan un nivel de seguridad extra
 - Pueden definirse ciertas reglas de negocio independientemente de las aplicaciones.
- Diferentes aplicaciones acceden al mismo código ya compilado y optimizado.
- En un ambiente cliente servidor, no sería necesario tener distribuido el código de la
aplicación.

SQL

PREGUNTAS Y RESPUESTAS DE FINALES

Verdadero - Falso

Afirmacion Verdadero/Falso Justificacion

En Heapsort, el tiempo de Falso Depende también del orden de los

ejecución solo depende del elementos, si esta semi-ordenado,
número de elementos a ordenar será más óptimo

Un árbol con grado mayor a 2 no Falso Un árbol se representa de forma

puede ser representado con una estática a través de un vector. El
representación computacional grado no es un limitante.
estática
El algoritmo de Huffman basa la Verdadero Aunque también utiliza una tabla de
asignación de códigos frecuencias, es el árbol binario quién
comprimidos basándose en define qué ramas recorrer para
un árbol binario llegar al símbolo. Las ramas
izquierdas se leen como 0 y las
derechas como 1.

La cantidad de nodos de un árbol Falso No es requisito necesario, la

de Huffman siempre es impar cantidad de nodos dependerá más
bien de los símbolos y sus
frecuencias

Al algoritmo de Quicksort es Falso Si los datos vienen ordenados, el

siempre más performante que el heapsort será más performante.
Heapsort

Al aplicar un barrido simétrico Verdadero También llamado inorden es un tipo

sobre ABB se obtiene el conjunto de barrido DFS.
de datos ordenados

La estructura de ABB (árbol Falso No necesariamente.

binario de búsqueda) es un árbol
completo

En Huffman si el código es 1001, Verdadero Dado que las hojas son los
entonces ningún otro carácter caracteres, para poder llegar al caso
puede tener el código 10011 10011, es necesario que exista un
hijo derecho al nodo 1001, pero
como la premisa dice que esa
codificación representa un carácter,
no es posible llegar a la otra
codificación

El árbol B+ nunca puede quedar Falso En este tipo de árboles todo nodo
lleno tiene entre n y n/2 hijos, ahora bien,
si todo nodo a excepción de las
hojas tuvieran hijos quedaría lleno.

Si en el caso de que el árbol tenga

un factor de carga del 100% esto es
posible. Tal escenario puede ser útil
para un B+ Tree asociado a un
índice que solo se utiliza para
consulta.

REVISAR.

Dado el grafo G(P,E) donde Falso Dado que un árbol es un grafo

P={(a)} y E={(a,a)} decimos que el acíclico que entre otras cosas “la
mismo es un árbol suma de nodos es igual a la suma
de arcos +1” (es decir, siempre hay
 más nodos que arcos), y en este
caso no se cumple dado que este es
un grafo con 1 vértice y una arista
cíclica.

Configurando el Read Commited Falso Las lecturas no son repetibles, dado

Isolation Level al ejecutar una que el SELECT no es bloqueante.
transacción, se evita que otras Por lo tanto no evita que otras
transacciones modifiquen las filas transacciones modifiquen las filas
que han sido leídas por la leídas.
transacción
actual

El árbol B (B-Tree) es más óptimo Falso Para búsquedas por igualdad la

para la búsqueda de claves estructura de hashing ofrece acceso
puntuales que la estructura de directo en orden O(1), es decir
Hashing. constante. Mejorando el del Árbol B
el cual es logarítmico O(log n)

Huffman, el árbol en el que se Falso No es requisito que sea balanceado

basa es un árbol principal derecho
balanceado

ABB, cuando un ABB se basa en Falso Un ABB en el mejor de los casos (si
un árbol AVL su orden de está balanceado) ofrece búsquedas,
complejidad será el inserciones y eliminaciones en orden
mejor, n log 2 n de complejidad O(log n), y en el peor
de los casos será lineal O(n).

Un vector es una representación Verdadero De hecho la representación

computacional estática que puede estáticas de árboles se realiza con
almacenar un árbol. vectores y la dinámica con listas
enlazadas.
El ejemplo es Heapsort que usa una
estructura estática que es un
Vector.

Todo grafo de grado 2 es un árbol Falso Un grafo de grado 2 podría tener

binario una flecha saliente a otro nodo y
otra flecha autoreferenciandose y no
sería un árbol binario.

Para reducir el espacio al Falso Depende del grafo a representar.

representar un grafo siempre es Las representaciones dinámicas se
más conveniente la forma recomiendan para grafos grandes
dinámica que estática. con muchos nodos y/o dispersos
(pocas aristas).
Por otro lado, las representaciones
estáticas se recomiendan para
 grafos pequeños y/o densos.

La cantidad de nodos de un árbol Falso No es así, por ejemplo para la

de expresión siempre es par expresión (2 * 3) + 6 el árbol de
expresión contaría con 5 nodos.

El algoritmo Heapsort siempre Falso El orden de complejidad varíara en

tiene el mismo orden de función de cómo se ingresan los
complejidad para cualquier datos.
orden en el que ingresan los datos Por ejemplo, si los datos ingresan
semi-ordenados será una mejor
opción que Quicksort, algoritmo con
el cual se lo compara con frecuencia
dado que ambos son in-situ, no
estables y con complejidad
logarítmica.

Todo grafo de grado 1 es tambíen Falso Un grafo con un único nodo que
un árbol contiene un arco autoreferenciarse
(bucle) es un grafo de grado 1 y no
es un árbol.
Para que un grafo sea considerado
un árbol entre otras debe ser
acíclico, dirigido, el número de
nodos igual al número de arcos -1 y
debe existir un único camino entre
cualquier par de nodos.

Si un árbol es completo, la Falso Un árbol completo es aquel de grado

cantidad de arcos es par k en que todos los nodos tienen 0 o
k hijos a excepción del último nivel
que no es necesario que cumpla esa
condición pero los nodos deben
estar alineados a la izquierda.
Pero en ningún caso es
precondición que la cantidad de
nodos sea par.

Sobre un árbol k-ario con k>2 se Falso El recorrido simétrico también

pueden realizar los siguientes llamado inorden solo es valido para
barridos: preorden, simétrico, Arboles Binarios
postorden y por niveles.

Un árbol binario de búsqueda Verdadero Para ordenar una lista se requiere

siempre es más rápido que una una búsqueda lineal 𝑂(𝑛).
lista (unsorted array) para ordenar Por el contrario un ABB ofrece
un conjunto de valores complejidad del orden logarítmico
𝑂(𝑙𝑜𝑔 𝑛)
Debido a que el crecimiento de un Verdadero A partir de la formula
árbol es exponencial en base al 𝑚𝑎𝑥 𝑛𝑜𝑑𝑜𝑠 < 𝑔𝑟𝑎𝑑𝑜
𝑛𝑖𝑣𝑒𝑙𝑒𝑠
− 1 se ,
grado del mismo, puede llegar a la conclusión de que
los tiempos de búsqueda en el la búsqueda es logarítmica
mismo son siempre logarítmicos

La reexpresión de caracteres al Falso La longitud de los códigos de

aplicar huffman implica la huffman es variable.
disminución de 8 bits para
la expresión de todos los
caracteres

El orden de complejidad de ABB Verdadero En ABB el orden de complejidad es

siempre es mejor que el orden de 𝑂(𝑙𝑜𝑔 𝑛) mientras que en Quicksort
complejidad de en el mejor de los casos el orden
Quicksort será de 𝑂(𝑛 𝑙𝑜𝑔 𝑛)

La técnica de Hash abierto puede Verdadero Si se utiliza direccionamiento abierto

generar muchas lecturas o rehashing para solucionar las
secuenciales para un colisiones aumenta probablemente
valor “clave hash” cuando hay alto el número de lecturas secuenciales
grado de repetición de claves de
usuario

La compactación por algoritmo de Falso No hay pérdida de información al

Huffman permite redefinir el utilizar este algoritmo
almacenamiento
lógico de símbolos de tal manera
que la pérdida de información sea
despreciable

Una tabla de Hash permite Verdadero Solo permite búsqueda por igualdad
desarrollar un mecanismo para recuperación de claves únicas
indexado para recuperación de
claves únicas

Un DBMS que soporte atomicidad, Verdadero Cumple con el estándar ACID

consistencia, Aislamiento y
durabilidad puede ser
considerado transaccional

Los árboles B garantizan mayor Falso Hashing permite un acceso a datos

velocidad que Hashing para el más veloz pero solo soporta
acceso a los datos búsquedas por igualdad, es decir
acceso directo (no soporta acceso
secuencial o por rango)
La implementación de una tabla Verdadero ok
de Hash es utilizada para
recuperar datos por medio de una
clave permitiendo un acceso de
alta velocidad a los datos

La Normalización aplicada al Falso Al normalizar normalmente

diseño de un modelo de datos perdemos performance en las
relacional, nos permite consultas, ya que ahora para
desarrollar un modelo de manera recuperar los datos se deben hacer
estructurada independientemente joins entre las tablas que contienen
de la performance que ese los datos.
modelo pueda llegar a obtener

Todos los motores de Bases de Falso En general los índices utilizan la

Datos utilizan el método de estructura B-Tree
Hashing para el armado de sus
índices

Las dimensiones en una base de Verdadero Las dimensiones proveen

datos multidimensional indican la información de hechos sobre uno o
forma de acceder a la información más cubos. Ejemplos de
que se encuentra en la dimensiones son; productos,
intersección de dichas clientes.
dimensiones

El checksum es una de las Verdadero .

técnicas utilizadas para corroborar
la integridad de los
datos

Data Mining son las técnicas y Verdadero Data Mining, la extracción de

algoritmos utilizados para patrones ocultos, modelos
encontrar información y desconocidos, que permiten analizar
relaciones ocultas en un y predecir tendencias en grandes
Datawarehouse bases de datos

El algoritmo de Quicksort tiene en Falso Método que mejor responde en la

promedio un grado de complejidad mayoría de los casos, implementado
O(n log n) pero en determinada en gran número de soluciones
circunstancia puede tener grado
de complejidad O(n2) y ser el peor
de todos los métodos de
clasificación

En la implementación de un Árbol Falso En B-Tree los nodos internos

B, todos los nodos de datos que también contienen claves. Es en
contienen claves, se encuentran B+Tree donde solo los nodos hojas
en el mismo nivel. contienen claves o puntos de datos
y estos se encuentran al mismo
nivel.

En un índice de un DBMS, Falso No depende del tamaño de la clave

armado en un árbol B, el tiempo sino de la altura del B-Tree, en el
de acceso a la información peor escenario el dato está en las
depende en parte del tamaño de hojas.
la clave almacenada.

En un modelo de DB OLTP el Verdadero La propiedad de Atomicidad

concepto de transacción está garantiza que la transacción sea
asociado a la atomicidad atómica o indivisible
de procesamiento

En un modelo OLAP se puede Verdadero Y terminaría en un modelo

aplicar normalización en cualquier snowflake
tabla de dimensión

La compresión que se logra Verdadero Ya que contaría con más

mediante el algoritmo de Huffman ocurrencias por carácter y a estos se
es mayor cuando la les asignaron códigos binarios más
variedad de caracteres diferentes cortos.
que aparecen es menor

Un árbol siempre tiene más Falso El número de aristas de un árbol

punteros que elementos de datos será igual a la cantidad de nodos
menos 1. Es decir, si hay “n” nodos,
habrá “n-1” aristas.

Un modelo OLAP, posee al menos Verdadero Pero puede contener más.

una tabla de hechos (FACT
TABLE), con campos
precalculados

Para representar grafos Falso Son más performantes las

irrestrictos son más performantes representaciones estáticas, dado
las representaciones que no hace falta dar de alta nuevas
dinámicas que las estáticas. relaciones en memoria de forma
constante.
Las funciones de hashing no Verdadero De esta forma son resistentes a
poseen funciones inversas ataques de preimagen,y son
extremadamente difíciles de invertir.

La única estructura de datos Verdadero La matriz podría ser de adyacencia

estática capaz de representar o de incidencia
cualquier grafo es una matriz.

El método de Árbol B no es Falso Si es aplicable, de hecho lo utilizan

aplicable a archivos con grandes los SO para el File System o
volúmenes de datos también los índices de Bases de
Datos

Dado el árbol {(c, a); (c, b); (c, d); Falso No se pueden realizar barridos
(c, e)} su barrido simétrico simetricos en un Arbol NO Binario
es a, b, c, d, e

Si un árbol está balanceado Falso Para que el árbol esté completo, el

entonces está completo último nivel se puede permitir la
ausencia de nodos a condición que
sean los de la derecha. En un árbol
balanceado solo requiere que a lo
sumo la diferencia entre las ramas
sea de 1 nivel, y la rama que falta
puede ser la izquierda, en cuyo caso
sería balanceado pero no completo.

Un AB con cuatro nodos nunca Falso Sí puede, ejemplo {(A,B), (A,C), (B,
puede ser completo D)}

Debido a que el crecimiento de un Verdadero .

árbol es exponencial en
base al ancho del mismo, los
tiempos de búsqueda en el
mismo son siempre logarítmicos

En un stored procedure, dentro de Falso Si es posible cambiarlo. De hecho

una transacción no se puede es lo que se suele hacer.
cambiar el nivel de aislamiento.

El método Heapsort, siempre es Verdadero Heapsort es en general más rápido

más rápido que Bubblesort para con una complejidad de 𝑂(𝑛 𝑙𝑜𝑔 𝑛)
ordenar un conjunto de datos del otro lado bubble sort tiene una
desordenados. 2
complejidad 𝑂(𝑛 ) sin importar cómo
vienen los datos por lo que Heapsort
será siempre una mejor opción en
términos de complejidad.
Un modelo OLAP solo puede ser Falso Puede ser representado también en
implementado en una DB bases relacionales (ROLAP).
Multidimensional

En el peor de los casos, el Falso En el peor de los casos Quicksort

algoritmo de ordenamiento tiene un orden de complejidad
Quicksort es igual a Heapsort 2
cuadrático 𝑂(𝑛 ) mientras que
Heapsort nunca supera 𝑂(𝑛 𝑙𝑜𝑔 𝑛)

El algoritmo de Huffman siempre Falso No se basa en árboles completos,

se basa en árboles completos se basa en árboles binarios los
cuales no necesariamente quedan
completos.

El algoritmo QuickSort es siempre Falso Por lo general Quicksort es más

más rápido que HeapSort rápido, pero si los datos vienen
semi-ordenados Heapsort será más
rápido.
También en el peor de los casos de
cada algoritmo respectivamente,
Heapsort será una mejor opción

Si un árbol B tiene N claves Verdadero Un B-Tree de k claves puede tener

entonces el grado es N+1 k+1 hijos, su grado será k+1.

Una subconsulta ubicada en un Falso No es necesario que así sea y si eso

WHERE siempre debe retornar al pasa esa subquery se toma como
menos una fila NULL.
Ej:
SELECT 'subquery nula' output
FROM DUAL
WHERE (SELECT 1 FROM DUAL
WHERE 1 = 2) IS NULL;
DBMS Oracle

El algoritmo de Huffman se basa Verdadero Cada carácter se codifica leyendo el

conceptualmente en un árbol árbol desde la raíz hasta la hoja que
binario del que consigue los tiene al mismo.
códigos comprimidos para cada
carácter.

Es posible realizar un barrido Falso Este barrido sólo es válido para

simétrico en un árbol n-ario con árboles binarios.
n>2
 Si una columna posee la Falso Permitirá tantos nulos como se
constraint de UNIQUE, entonces quiera porque NULL representa
ninguna fila acepta ausencia de valor, y ni es
NULOS en dicha columna comparable ni se puede considerar
único respecto a otro.

Dada una tabla que tiene un Verdadero Si falla el trigger también fallara la
trigger de INSERT; Si al insertar sentencia que lo disparó.
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.

El árbol lleno y el árbol completo Falso El árbol lleno es un árbol de grado k

son dos tipos de árboles binarios en el que todos sus nodos tienen 0 o
balanceados k hijos.
El árbol completo es un árbol lleno a
excepción del último nivel que puede
permitirse que falten nodos a
condición de que sean los derechos
(quedando los nodos alineados a la
izquierda).
Un árbol binario balanceado es un
árbol de grado k=2 en el que todos
sus subárboles desde la raíz pesan
lo mismo o difieren a lo sumo en 1.

Las claves alternas (o Falso Las claves candidatas son posibles

alternativas), son posibles claves claves primarias, pero cuando no
foráneas que pertenecen al son primarias, se llaman alternas o
conjunto de las claves candidatas alternativas.

El método de Hashing resuelve Falso El método Hashing no puede

más eficientemente las búsquedas resolver búsquedas por rango.
con rangos de claves

El algoritmo Heapsort siempre Verdadero Su complejidad siempre es O(n log

tiene la misma complejidad n) para el mejor caso, el peor caso,
computacional para cualquier y el caso promedio.
orden en el que ingresan los datos Aunque sí puede tener mejor mejor
rendimiento en comparativa con
otros algoritmos similares como
Quicksort si los datos vienen
semi-ordenados.
La única manera para asegurar Falso También se podría implementar un
unicidad de los campos es con control de unicidad mediante trigger
una Primary Key o aunque no sería lo recomendable.
con UNIQUE

El orden de complejidad de un Falso En general ambos tienen un orden

ABB (árbol binario de búsqueda) de complejidad temporal de 𝑂(𝑙𝑜𝑔 𝑛)
es similar al del Árbol-B . La diferencia reside en que en el
peor de los casos un el ABB tiene un
orden 𝑂(𝑛) mientras que el B-tree
siempre se mantiene en 𝑂(𝑙𝑜𝑔 𝑛)
(gracias al balanceo).

Si un árbol B (B-Tree) tiene N Falso El grado del árbol B se define por la

claves entonces el grado es N+1 cantidad de keys que soporta por
nodo y por el load factor que se
utiliza.

La cantidad de nodos de un árbol Verdadero La cantidad de nodos de un árbol

de Huffman siempre es impar lleno se puede calcular como n = 2l
-1, donde “l” es el número de hojas.
Esta expresión siempre dará un
número impar.

Sobre un árbol n-ario con n>2 se Falso Solo se puede aplicar dichos
pueden realizar los siguientes barridos para árboles binarios. El
barridos (recorridos) preorden, barrido simétrico solo se puede
simétrico, postorden, y por niveles 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.

El Árbol B es más óptimo para la Falso Para búsquedas puntuales es más

búsqueda de claves puntuales óptimo Hashing.
que la estructura de Hashing

La implementación de la cantidad Falso La tabla hash es estática por

de entradas para claves en una definición.
tabla de hash es dinámica

Es posible implementar el Verdadero Es posible y de hecho es lo que

concepto de ABB (Arbol Binario utiliza el método de ordenamiento
de Búsqueda) en un array Heapsort.
Si existe un select dentro de una Falso El subquery puede devolver más de
cláusula HAVING, este debe una fila pero se debe usar el
devolver 1 fila y 1 columna operador adecuado (IN, ANY, ALL).

Gracias a los índices se puede Falso La integridad referencial se asegura

asegurar la integridad referencial mediante relaciones entre Primary
Key y Foreign Key.

Si se desea que no se puedan Verdadero Es una opción posible, este trigger

eliminar registros de una tabla de podría ser disparado BEFORE
auditoría, una opción es crear un STATEMENT, y mostrar un mensaje
trigger que lo impida de error al usuario.
Una mejor opción podría ser utilizar
REVOKE para quitar los permisos
de DELETE.

La cantidad de nodos de un árbol Falso Comprobable con una expresión

de expresión siempre es par como (10+5)*3

El Heapsort tiene peor Falso En cualquier caso Heapsort tiene

rendimiento si los datos ya vienen rendimiento O(log n)
ordenados

Los índices sólo se usan en las Falso También se usan en operaciones de

base de datos para ganar ordenamiento, agrupamiento, joins,
velocidad y también pueden crearse índices
únicos para claves UNIQUE.

Los grafos irrestrictos solo pueden Falso También puede representarse de

representarse manera estática con por ejemplo
computacionalmente de manera una matriz de adyacencia.
dinámica

Si tengo un conjunto de datos Falso Si los datos vienen semi-ordenados

tendiendo a ordenados, el u ordenados, Quicksort tenderá a
algoritmo de Quicksort es el comportarse como en el peor de los
más eficiente para su 2
casos 𝑂(𝑛 )
ordenamiento total

La acción que ejecuta un trigger y Verdadero Un trigger es parte de una

el evento que lo dispara siempre transacción de mayor envergadura,
se ejecutan de manera atómica que contiene al evento disparador y
otros previos a este. Una vez que el
trigger se ejecuta y retorna el
control, si se compromete o deshace
la transacción, los efectos del trigger
también se comprometen o no
respectivamente porque está
contenido en la misma transacción.
En ACID, Atomicity trata este tema
en general como un grupo de
operaciones que se comprometen o
no en conjunto siempre llevando la
BD de un estado válido a otro válido.