Sistemas Manejadores de Bases de Datos Con Portada

INSTITUTO TECNÓLOGICO SUPERIOR DE LA MONTAÑA

INGENIERÍA EN SISTEMAS COMPUTACIONALES

ASIGNATURA: “FUNDAMENTOS DE INVESTIGACIÓN”DOCENTE: ING. FREDDY RAMÍREZ VILLALOBOS

TEMA: “SISTEMAS MANEJADORES DE BASE DE DATOS”

ACTIVIDAD: INVESTIGACION DOCUMENTAL

PRESENTA: Jesús Monje Labra

TLAPA DE COMONFORT, GRO., 14 de Diciembre.

INVESTIGACIÓN DOCUMENTALSISTEMAS MANEJADORES DE BASE DE DATOS

INTRODUCCIÓN

Los sistemas manejadores de base de datos (SGBD), en inglés: DataBase Management

System (DBMS), es un tipo de software que sirven de interfaz entre la base de datos, el usuario

y las aplicaciones que lo utilizan. Actualmente en el mercado existe una gran variedad SMBD

que comparten un mismo propósito general: manejar de manera clara, sencilla y ordenada un

conjunto de datos que posteriormente se convertirán en información relevante para una

organización. Entre las principales funciones de los SMBD se encuentran:

1. Abstracción de la información

2. Independencia

3. Consistencia

4. Seguridad

5. Manejo de Transacciones

6. Tiempo de respuesta

7. Establece y mantiene las trayectorias de acceso

8. Maneja la base de datos de acuerdo a la petición

9. Registra todo el movimiento de las bases de datos

10. Interactúa con el manejador de base de datos

Aunque todos los SMBD tienen el mismo propósito, existen casos especiales que los hacen

diferentes y, por lo consiguiente, cada uno posee ciertas ventajas sobre los demás. Existen en

el mercado y se clasificaran de acuerdo a la licencia que posean, esta puede ser: de código

libre o abierto son aquellos que se les puede modificar su código, se adecuan a las

necesidades del usuario y cuentan con licencia, por ejemplo MySQL, Apache Derby, DB2, etc.

Al contrario de aquellos SMBD propietarios o de manejo mediante web no libre y gratuito como

FileMaker, WindowBase, Microsoft SQL Server Compact, etc. Por último se mencionaran los

sitios web que ofrecen versiones gratuitas como es el dreamspark, el tipo de aplicaciones que

se pueden desarrollar y el tipo de software que se utilizara.

1


Sistemas Manejadores de Bases de Datos

I Introducción

Durante un buen tiempo, las bases de datos pasaron a formar punto clave y primordial en

nuestras vidas, debido a que la ciencia fue creciendo de tal manera que se necesitaba alguna

manera organizar los datos de distintos objetos, fue así como nació las bases de datos; que a

través del paso de los días fueron siendo cada vez mas complejas y organizadas fue así como

distintos software aparecieron y ofrecieron una mejor organización en base de datos cuando

estos eran de gran inmensidad. Ofrecieron mejores avances grandes y significativos resultados

en las organizaciones. Gracias a la evolución de la base de datos, el día de hoy podemos gozar

de los beneficios de tener grandes bases de datos organizadas y fáciles de manipular e

introducir datos, hoy podemos obtener los resultados eficaces, ya ahora se obtienen los datos

necesarios en segundos.

I.1 Panorama general de un SMBD.

Es un conjunto de elementos relacionados entre si que reflejan o modelan la información

de una organización. Quiere decir que el contenido de cualquier BD refleja una realidad

significativa para alguien, desde el punto de vista de sistemas, esta compuesto por unos

componentes integrados que les permitirán a los usuarios manipular la información

según sus necesidades.

I.2 Revisión del modelo relacional.

I.3 Revisión de SQL.

2


II Almacenamiento y estructura de archivos

Es una colección de objetos que guardan relaciones lógicas entre sí. Estos objetos

que guardan son las diversas tablas e índices almacenados físicamente.

II.1 Organización de la memoria.

II.2 Los discos duros.

II.3 Los niveles RAID.

RAID (Redundant Array of Independent Disk) la creación de imagines proporciona gran

fiabilidad pero resulta costosa. La distribución proporciona velocidades de transferencia

de base de datos elevados, pero no mejora la fiabilidad. Varios esquemas alternativos

pretenden proporcionar redundancia a un coste menor combinado la distribución de los

discos combinada con los bits de “paridad”. Estos esquemas tienen diferentes

compromisos entre el coste y el rendimiento y se clasifican en los denominados niveles

de RAID, como se presenta a continuación:

El nivel 0 de RAID hace referencia a disposiciones de discos con distribución en

el nivel de bloques, pero sin redundancia (como la creación de imágenes o los

bits de paridad).

El nivel 1 de RAID hace referencia a disposiciones de discos con distribución de

bloques. Obsérvese que algunos fabricantes emplean el término nivel 1+0 de

RAID o nivel 10 de RAID para referirse a imágenes del disco con distribución, y

utiliza el término nivel 1 de RAID para las imágenes del disco sin distribución.

Estos ultimo también se puede emplear con disposiciones de discos para dar la

apariencia de un disco grande y fiable: si cada disco tiene M bloques, los bloques

3


lógicos 1 a M se almacenan en el disco 1; M + 1 a 2 M en el segundo, y así

sucesivamente, y se crea una imagen de cada disco.

El nivel 2 de RAID, también conocido como organización de códigos de

corrección de errores tipo memoria (memory-style-error-correcting-code

organitation, ECC) emplea bits de paridad. Hace tiempo que los sistemas de

memoria utilizan los bits de paridad para la detección y corrección de errores.

Cada byte del sistema de memoria puede tener asociado un bit de paridad que

registra si el número de bits del byte que vale uno es par (paridad = 0) o impar

(paridad = 1). Si alguno de los bits del byte se deteriora (un uno se trasforma en

cero y viceversa) la paridad del bute se modifica y, por lo tanto, no coincide con

la paridad guardada. Analógicamente, si el bit de paridad guardado se deteriora

no coincide con la paridad calculada. Por tanto, el sistema de memoria detecta

los errores que afecta a un número impar de bits de un mismo byte. Los

esquemas de corrección de errores guardan dos o más bits adicionales y pueden

reconstruir los datos si se deteriora un solo bit.

La idea de los códigos para la corrección de errores se puede utilizar

directamente en las disposiciones de discos mediante la distribución de los byte

entre los diferentes discos. Por ejemplo, el primer bit de cada byte pueden

guardarse en el disco uno, el segundo en los disco dos, etc., hasta que se guarde

el octavo bit en el disco ocho; los bits para la corrección de errores se guardan en

discos adicionales.

El nivel 3 de RAID organiza de paridad con bits entrelazados, mejora respecto al

nivel 2 al aprovechar que los controladores de disco, a diferencia de los sistemas

de memoria, puedan detectar si los sectores se han leído correctamente, por lo

que se utilizar un solo bit de paridad para la corrección y para la detección de los

errores. La idea es la siguiente : si uno de los sectores se deteriora, se sabe

exactamente el sector que es y , para cuando uno de sus bits, se puede

determinar si es uno o un cero calculando la paridad de los bits correspondientes

de los sectores de los demás discos. Si la paridad de los bits restantes es igual

que la paridad guardada, el bit perdido es un cero; en caso contrario, es uno. El

4


nivel 3 de RAID es tan bueno como el nivel 2, pero resulta menos costoso en

cuanto al número de discos adicionales (solo tiene un disco adicional), por lo que

el nivel 2 no se utiliza en la práctica. El nivel 3 de RAID tiene dos ventajas

respecto al nivel 1. Solo necesita un disco de paridad para varios discos

normales, mientras que en el nivel 1 necesita un disco de imagen por cada disco.

Por lo que se reduce la necesidad de almacenamiento adicional. Dado que los

procesos de lectura y de escritura de cada bute se distribuyen por varios discos,

con la distribución de los datos en N fracciones, la velocidad de transferencia

para la lectura o la escritura de un solo bloque multiplica por N la de organización

de RAID de nivel 1 que emplee la distribución entre N discos. Por otro lado, el

nivel 3 de RAID permite un menor número de operaciones de E/S por segundo,

ya que todos los discos tienen que participar en cada solicitud de E/S.

El nivel 4 de RAID organiza de paridad con bloques entrelazados, emplea la

distribución del nivel de bloques, como RAID 0, y, además, guarda un bloque de

paridad en un disco independiente para los bloques correspondientes de los

otros N discos. Si falla uno de los discos, se puede utilizar el bloque de paridad

con los bloques correspondientes de los demás discos para restaurar los bloques

del disco averiado. La lectura de un bloque solo accede a un disco, lo que

permite que los demás discos procesen otras solicitudes. Por tanto, la velocidad

de transferencia de datos de cada acceso es menor. Pero se pueden ejecutar en

paralelo varios accesos de lectura, lo que produce una mayor velocidad global de

E/S. Las velocidades de transferencia para los procesos de lectura de gran

tamaño son elevadas, dado que se pueden leer todos los discos en paralelo; los

procesos de escritura de gran tamaño también tienen velocidades de

transferencia elevadas, dado que los datos y la paridad pueden escribirse en

paralelo.

Los procesos de escritura independientes de un pequeño tamaño, por otro lado,

no pueden realizarse en paralelo. La operación de escritura de un bloque tiene

que acceder al disco en el que se guarda ese bloque, así como al disco de

paridad, ya que hay que actualizar el bloque de paridad. Además, hay que leer

tanto el valor anterior del bloque de paridad como el del bloque que se escribe

para calcular la nueva paridad. Por tanto, un solo proceso de escritura necesita

5


cuatro accesos a disco: dos para leer los dos bloques antiguos y otros dos para

escribir los dos nuevos.

El nivel 5 de RAID paridad distribuida con bloques entrelazados, mejora respecto

al nivel 4 al dividir los datos y paridad entre todos los N + 1 discos, en vez de

guardar los datos en N discos y la paridad en uno solo. En el nivel 5 todos los

discos pueden atender las solicitudes de lectura a diferencia del nivel 4 de RAID,

en el que el disco de paridad no puede participar, por lo que el nivel 5 aumenta el

número total de solicitudes que pueden atenderse en una cantidad de tiempo

dada. En cada conjunto de N bloques lógicos, uno de los discos guarda la

paridad y los otros otros N guardan los bloques.

El nivel 6 de RAID, también denominado esquema de redundancia P+Q, es muy

parecido al nivel 5, pero guarda información redundante adicional para la

protección contra los fallos de disco múltiples. En lugar de utilizar la paridad, el

nivel 6 utiliza códigos para la corrección de errores como los Reed-Solomon.

II.4 Organización de archivos.

Los archivos se organizan lógicamente como secuencias de registros. Esos registros se

corresponden con los bloques del disco. Los archivos constituyen un elemento

fundamental de los sistemas operativos, por lo que se supone la existencia de un

sistema de archivos subyacente. Hay que tomar en consideración diversas maneras de

representar los modelos lógicos de datos en términos de los archivos. Aunque los

bloques son de un tamaño fijo determinado por las propiedades físicas del disco y por el

sistema operativo, el tamaño de los registros varía. En las bases de datos relacionales,

las tuplas de las diferentes relaciones suelen ser de tamaño diferente un enfoque de las

correspondencia entre base de datos y archivos es utilizar varios archivos y guardar los

registros de la misma longitud en un mismo archivo. Una alternativa es estructurar los

archivos y guardar los registros de la misma longitud en un mismo archivo. Una

alternativa es utilizar varios archivos y guardar los registros de la misma longitud en un

mismo archivo. Una alternativa es estructurar los archivos de modo que puedan aceptar

6


registros de longitudes diferentes; no obstantes, los archivos con registros de longitud

fija don más sencillos de implementar que los que tienen registros de longitud variable.

Muchas de las técnicas empleadas para los primeros pueden aplicarse a los de longitud

variable. Por tanto, se comienza por tomar en consideración los archivos con registros

de longitud fija.

Registros de longitud fija

Consideramos que unos archivos con registros de cuentas de la base de datos

bancaria. Cada registro de este archivo se define (en seudocódigo) de la manera

siguiente:

Si se supone que cada carácter ocupa un byte y que los valores de un tipo

numeric(12,2) ocupan ocho bytes, el registro de cuenta tiene cuarenta bytes de

longitud. Un enfoque sencillo es utilizar los primeros cuarenta bytes siguientes

para el segundo, y así sucesivamente. Sin embargo, hay dos problemas con este

sencillo enfoque:

1. Resulta difícil borrar registros de esta estructura. Hay que rellenar el

espacio ocupado por el registro que van a borrar con algún otro registro

del archivo, o tener alguna manera de marcar los registros borrados para

poder pasarlos por alto.

2. A menos que el tamaño de los bloques sea múltiplo de cuarenta (lo que

resulta improbable), algún registro se saltara los límites de los bloques. Es

7

type deposito = record

numero_cuenta char(10);

nombre_sucursal char (10);

saldo numeric(12,2);

end


decir, parte del registro santo, se guardara en un bloque y parte de otro.

Harán falta, por tanto, dos accesos a bloques para leer o escribir esos

registros.

Cuando se borra un registro, se puede desplazar el situado a continuación al

espacio ocupado que ocupaba el registro borrado y hacer lo mismo con los

demás, hasta que todos los registros situados a continuación del borrado se

hayan desplazado hacia delante. Este tipo de enfoque necesita desplazar gran

número de registros. Puede que fuera más sencillo desplazar simplemente el

último registro del archivo al espacio ocupado por el registro borrado.

No resulta deseable desplazar los registros para que ocupen el espacio liberado

por los registros borrados, ya que para hacerlos se necesitan accesos

adicionales a los bloques. Dado que las operaciones de inserción tienden a ser

más frecuentes que las de borrado, resulta aceptable dejar libre el espacio

ocupado por los registros borrados y esperar a una intercesión posterior ante de

volver a utilizar ese espacio. No basta con una simple marca en el registro

borrado, ya que resulta difícil hallar el espacio disponible mientras se realiza una

inserción. Por tanto, hay que introducir una estructura adicional.

Al comienzo del archivo se asigna cierto número de bytes como cabecera del

archivo. La cabecera contiene gran variedad de información sobre el archivo. Por

ahora, todo lo que hace falta guardar es la dirección del primer registro cuyo

contenido se haya borrado. Se utiliza este primer registro para guardar la

dirección del segundo registro disponible, y asi sucesivamente. De manera

intuitiva se pueden considerar estas direcciones guardadas como punteros, dado

que indican la posición de un registro. Los registro borrados, por tanto forman

una lista enlazada a la que se suele denominar lista libre. Al insertar un registro

nuevo se utiliza el registro al que apunta la cabecera. Se modifica el puntero de

la cabecera para que señale a los siguientes registros disponibles. Si no hay

espacio disponible, se añade el nuevo registro al final del archivo.

La inserción y borrado de archivo con registros de longitud fija son sencillas

implementar, dado que el espacio que deja libre cada registro borrado es

8


exactamente el mismo que se necesita para insertar otro registro. Si se permiten

en un archivo registros de longitud variable, esta coincidencia no se mantiene.

Puede que el registro insertado no quepa en el espacio liberado por el registro

borrado o que solo llene una parte.

Registros de longitud variable

Los registros variables surgen de varias maneras en los sistemas de base de

datos:

Tipos de registro que permiten longitudes variables para uno varios de los

campos.

Tipos de registros que permiten campos repetitivos, como los arrays o los

multiconjuntos.

Existen diferentes técnicas para implementar los registros de longitud variable. La

estructura de páginas con ranuras se utiliza habitualmente para organizar los

registros en bloques, hay una cabecera al principio de cada bloque, que contiene

la información siguiente:

1. El número de elementos del registro de la cabecera.

2. El final del espacio vacío del bloque.

3. Un array cuyas entradas contienen la ubicación y el tamaño de cada

registro.

Los registros reales se ubican en el bloque de manera contigua, empiezan por el

final. El espacio libre dentro del bloque es contiguo, entre la última entrada del

array de la cabecera y el primer registro. Si se insertan un registro, se le asigna

9


espacio al final del espacio libre y se añade a la cabecera una entrada que

contienen su tamaño y su ubicación.

Organización de los registros en archivos

Es la forma de organizar los registros en archivos:

Organización de los archivos en montículos. Se puede colocar cualquier

registro en cualquier parte del archivo en que haya espacio suficiente. Los

registros no se ordenan. Generalmente solo hay un archivo para cada

relación.

Organización secuencial de los archivos. Los registros se guardan en

orden secuencial, según el valor de la “clave de búsqueda” de cada uno.

Organización asociativa (hash) de los archivos. Se calcula una función de

asociación (hash) para algún atributo de cada registro. El resultado de la

función de asociación especifica el bloque del archivo en que se debe

colocar cada registro.

Generalmente se usa un archivo separado para almacenar los registros de cada

relación. No obstante, en cada organización de archivos en agrupaciones de

varias tablas se pueden guardar en el mismo archivo registros de relaciones

diferentes; además, los registros relacionados de las diferentes relaciones se

guardan en el mismo bloque, por lo que cada operación de E/S afecta a registros

relacionados de todas esas relaciones. Por ejemplo, los registros de dos

relaciones se pueden considerar relacionados si casan en una reunión de dos

relaciones.

Organización de archivos secuenciales.

Los archivos secuenciales están diseñados para el procesamiento eficiente de

los registros de acuerdo con un orden basado en alguna clave de búsqueda. La

10


clave de búsqueda es cualquier atributo o conjunto de atributos; no tiene por qué

ser la clave primaria, ni siquiera una superclave. Permitir la recuperación rápida

de los registros según el orden de la clave de búsqueda, estos se vinculan

mediante punteros. El puntero de cada registro según el orden de la clave de

búsqueda, estos se vinculan mediante punteros. El puntero de cada registro

señala al siguiente registro según el orden indicado por la clave de búsqueda.

Además, para minimizar el número de accesos a los bloques en el

procesamiento de los archivos secuenciales, los registros se guardan físicamente

en el orden indicado por la clave de búsqueda, o lo más cercano posible.

La organización secuencial de archivos permite que los registros se lean en

forma ordenada, lo que puede resultar útil para la visualización asi como para

ciertos algoritmos de procesamiento de consultas. Sim embargo resulta difícil

mantener el orden físico secuencial a medida que se insertan y se borran

registros, dado que se resulta costoso desplazar muchos registros como

consecuencia de una sola operación de inserción o de borrado. Se puede

gestionar el borrado mediante cadenas de punteros, como ya se ha visto. Para la

inserción se aplica las reglas siguientes:

1. Localizar el registro del archivo que precede al registro que se van

insertar según el orden de la clave de búsqueda.

2. Si existe algún registro vacío (es decir, un espacio que haya quedado

libre después de una operación de borrado) dentro del mismo bloque que

eses registro, el registro nuevo se insertara ahí. En caso contrario, el

nuevo registro se insertara en un bloque de desbordamiento. En cualquier

caso, hay que ajustar los punteros para vincular los registros según el

orden de la clave de búsqueda.

Organización de archivos en agrupaciones de varias tablas.

11


Muchos sistemas de base de datos relacionales guardan cada relación en un

archivo diferente, de modo que se puedan aprovechar completamente el sistema

de archivos proporcionado por el sistema operativo. Generalmente las tuplas de

cada relación se pueden representar como registros de longitud fija. Por tanto,

se puede hacer que las relaciones se correspondan con una estructura de

archivos sencilla. Esta implementación sencilla de los sistemas de base de datos

relacionales resulta adecuada para las implementaciones de bajo coste de las

bases de datos como, por ejemplo, los sistemas empotrados o los dispositivos

portátiles. En esos sistemas el tamaño de la base de datos es pequeño, por lo

que se obtiene poco provecho de una estructura de archivos avanzada. Además,

en esos entornos, es fundamental que el tamaño total del código objeto del

sistema de bases de datos sea pequeño. Una estructura de archivos sencilla

reduce la cantidad de código necesario para implementar el sistema. Este

enfoque sencillo de la implementación de las base de datos relacionales resulta

menos satisfactorio a medida que aumenta el tamaño de la base de datos ya que

ha visto que se puede obtener mejoras en el rendimiento mediante la asignación

esmerada de los registros a los bloques y la cuidadosa organización de los

propios bloques. Por tanto, resulta evidente que una estructura de archivos más

compleja puede resultar beneficiosa, aunque se mantenga la estrategia de

guarda cada relación en un archivo diferente. Sin embargo. Muchos de los

sistemas de base de datos de gran tamaño no utilizan directamente el sistema

operativo subyacente para la gestión de los archivos. Por el contrario, se asigna

al sistema de base de datos un archivo de gran tamaño del sistema operativo. En

ese archivo, el sistema de base de datos, que también lo administra, guarda

todas las relaciones.

III Métodos de indexamiento

12


III.1 Índices sobre archivos secuenciales.

III.2 Índices secundarios.

Este tipo de índices debe ser denso, con una entrada en el índice por cada valor de la

clave de búsqueda, y un puntero a cada registro del archivo. Un índice con agrupación

puede ser disperso, almacenado solo algunos de los valores de la clave de búsqueda,

ya que siempre es posible encontrar registros con valores de la clave de búsqueda

intermedios mediante un acceso secuencial a parte del archivo. Si su índice secundario

almacena solo algunos de los valores de la clave de búsqueda, los registros con los

valores de la de búsqueda intermedios pueden estar cualquier lugar del archivo y, en

general, no pueden encontrar sin explorar el archivo completo. Un índice secundario

sobre una clave candidata es como un índice denso con agrupación, excepto en que los

registros apuntados por los sucesivos valores del índice no están almacenados

secuencialmente. Generalmente los índices secundarios están estructurados de manera

diferente a como lo están los índices con agrupación.

Si la clave de búsqueda de una índice con agrupación no es una clave candidata. Es

suficiente si el valor de cada entrada en el índice apunta al primer registro con ese valor

en la clave de búsqueda, ya que los otros registros podrían ser alcanzados por una

búsqueda secuencial del archivo. En cambio. Si la clave de búsqueda de un índice no es

una clave candidata, no sería suficiente apuntar solo al primer registro de cada valor de

la clave. El resto de registros con el mismo valor de la clave de búsqueda podría estar

en cualquier otro sitio del archivo, ya que los registros están ordenados según la clave

de búsqueda del índice con agrupación, en vez de la clave de búsqueda del índice

secundario. Por lo tanto, un índice secundario deber contener punteros a todos los

registros.

III.3 Árboles B+.

13


El inconveniente principal de la organización de un archivo secuencial indexado reside

en que el rendimiento, tanto para buscar en el índice como para buscar secuencialmente

a través de los datos, se degrada según tanto crece el archivo. Aunque esta

degradación se puede remediar reorganizando el archivo, no es deseable hacerlo

frecuentemente.

La estructura de índice de árbol B+ es la más extendida de las estructuras de índices

que mantienen su eficiencia a pesar de la inserción y borrado de datos. Un índice de

árbol B+ toma la forma de un árbol equilibra donde los caminos de la raíz a cada hoja

del árbol son de la misma longitud. Cada nodo que no sea hoja tiene entre [n/2] y n hijos,

donde n es fijo para cada árbol concreto.

Se verá que la estructura de árbol B+ implica una degradación del rendimiento al insertar

y al borrar, además de un espacio extra. Este tiempo adicional es aceptable incluso en

archivos con altas frecuencias de la modificación, ya que se evita el coste de reorganizar

el archivo. Además, puesto que los nodos podrían estar a lo sumo medio lleno (si tienen

el mínimo número de hijos) se desperdicia algo de espacio. Este gasto de espacio

adicional también es aceptable dados los beneficios en el rendimiento aportados por las

estructuras de árbol B+.

Estructura de árbol B+

Un índice de árbol B+ es un índice multinivel pero con una estructura que difiere

del índice multinivel de un archivo secuencial. Considérese primero la estructura

de nodos hoja. Para i = 1,2,…, n – 1, el puntero P apunta, o bien a un registro del

archivo con valor de la clave de búsqueda K, o bien a un cajón de punteros, o

bien a un cajón de punteros, cada uno de los cuales apunta a un registro del

archivo con valor de la clave de búsqueda K. la estructura cajón se usa

solamente si la clave de búsqueda no es una clave candidata y si el archivo no

está ordenado según la clave de búsqueda.

14


Los nodos internos del árbol B+ forman un índice multinivel (disperso) sobre los

nodos hoja. La estructura de los nodos internos es la misma que la de los nodos

hoja, excepto que todos los punteros son punteros a nodos del árbol. Un modo

interno podría guardar hasta n punteros y debe guardar al menos [n/2] punteros.

El numero de punteros de un nodo se llama grado de salía del nodo.

Considérese un nodo que contienen m punteros. Para i = 2, 3, …., m – 1, el

puntero P apunta al subárbol que contienen los valores de la clave de búsqueda

menores que K y mayor o igual que K -1. El puntero P apunta a la parte del

subárbol que contiene los valores de las claves mayores o iguales que K y el

puntero P apunta a la parte del subárbol que contiene los valores menores que K.

III.4 Tablas de dispersión.

III.5 Índices de múltiples dimensiones y mapas de bits.

Un mapa de bits es simplemente un array de bits. En su forma mas sencilla, un índice de

mapas de bit sobre el atributo A de la relación r consiste en un mapa de bits para cada

valor que pueda tomar A. cada mapa de bits para el valor uj se define como 1 si el

registro con un numero i tiene el valor uj para el atributo A. El resto de los bits del mapa

de bits se define como ().

En este ejemplo hay un mapa de bit para el valor m y otro para f. el i –esimo bit del mapa

de bits para m se define como 1 si el valor sexo del registro con numero i es m. el resto

de bits del mapa de bits para m se define como (). Analógicamente, el mapa de bits de f

tienen el valor 1 para los bits correspondientes a los registros con el valor m (o f) seria

simplemente leer todos los registros de la relación y seleccionar los de valor m (o f,

respectivamente). El índice de mapa de bits no ayuda realmente a acelerar esa

selección.

15


De hecho, los índices de mapas de bits resultan útiles para las selecciones sobre todo

cuando hay selecciones bajo varias claves. Supónganse que se crea un índice de

mapas de bits sobre el atributo nivel_ingresos, que ya se ha descritos antes, además del

índice de mapas de bits para sexo.

Los índices de mapas de bits son generalmente bastante pequeños en comparación con

el tamaño real de la relación. Los registros suelen tener entre decenas y centenares de

bytes de longitud, mientras que un solo bit representa a un registro en el mapa de bits.

Por tanto, el espacio ocupado por cada mapa de bits suele ser menos del uno por ciento

del espacio ocupado por la relación. Por ejemplo, si el tamaño del registro de una

relación dada es de 100 bytes, el espacio ocupado por cada mapa de bits seria la octava

parte del uno por ciento del espacio ocupado por la relación. Si el tributo A de la relación

solo puede tomar uno valor de entre ocho, el índice de mapas de bits de ese atributo

consiste en ocho mapas de bits que, juntos, solo ocupan el uno por ciento del tamaño

de la relación.

IV Procesamiento y optimización de consultas

IV.1 Álgebra y cálculo relacional.

Es una colección de operaciones que sirven para manipular relaciones enteras. Estas

operaciones sirven, por ejemplo para seleccionar tuplas de relaciones individuales y para

combinar tuplas relacionadas a partir de varias relaciones con el fin de especificar una

consulta—una solicitud de obtención—de la base de datos. El resultado de cada

operación es una nueva relación, que podremos manipular en una ocasión futura.

Las operaciones del algebra relacional suelen clasificarse en dos grupos. Uno contiene

las operaciones corrientes de la teoría matemática de conjuntos; es posible aplicarlas

por que las relaciones se definen como un conjunto de tuplas. Entre las operaciones de

conjuntos están la unión, la intersección, la diferencia y el producto cartesiano. El otro

grupo consiste en operaciones creadas específicamente para bases de datos

relacionales; incluyen Seleccionar, Proyectar y Reunión (a esta ultima también le llaman

16


Junta), entre otras. Primero veremos operaciones seleccionar y proyectar porque son las

más sencillas y luego estudiaremos las operaciones de conjuntos. Por ultimo, trataremos

la reunión y otras operaciones complejas.

1. Operación seleccionar

La operación seleccionar sirve para seleccionar un subconjunto de las tuplas de una

relación que satisface una condición de selección. Por ejemplo, para seleccionar el

subconjunto de tuplas de EMPLEADO que trabajan en el departamento 4 o cuyo salario

rebasa los $30 000, podemos especificar individualmente cada una de estas dos

condiciones con la operación SELECCIONAR, como sigue:

Nd=4 (EMPLEADO)

SALARIO>30000 (EMPLEADO)

En general, denotamos la operación SELECCIONAR con

<condición de selección> (<nombre de la relación>)

La relación que resulta de la operación SELECCIONAR tiene los mismos atributos que la

relación especificada en <nombre de la relación>. La expresión booleana específica en

la <condición de la selección> se compone de una o de más clausulas de la forma:

<nombre de atributo><operador de comparación><valor constante> , o

<nombre de atributo><operador de comparación><nombre de atributo>

Donde <nombre de atributo> es el nombre de un atributo de <nombre de la relación>,

<operador de comparación> es normalmente uno de los operadores {=, <, ≤, >, ≥, ≠}, y

<valor constante> es un valor constaste del dominio del atributo. Las clausulas pueden

conectarse arbitrariamente con los operadores boléanos y (AND), O (OR) Y NO (NOT)

para formar una condición de selección general.

17


2. La operación Proyectar

Si visualizamos una relación como una tabla, la operación SELECCIONAR selecciona

algunas filas de la tabla y desecha otras. La operación PROYECTAR, en cambio,

selecciona ciertas columnas de la tabla y desecha las demás. Si solo nos interesan

ciertos atributos de una relación, “proyectaremos” la relación sobre esos atributos con la

operación PROYECTAR. Por ejemplo, si queremos listar el apellido, nombre de pila y el

salario de todos los empleados, podemos usar la siguiente operación PROYECTAR:

APELLIDO, NOMBREP, SALARIO (EMPLEADO)

Calculo relacional

Es el lenguaje formal para las bases de datos relacionales, en el mercado hay muchos

lenguajes de base de datos relacionados que apoyan en algunos aspectos de este

cálculo, entre ellos el lenguaje SQL, sin embargo, algunos lenguajes son más parecidos

al cálculo relacional que otros; por ejemplo los lenguajes QUEL y QBE. En un sentido

importante, el calculo y el algebra relacionales son idénticos. Se ha demostrado que

cualquier obtención de datos que se pueda especificar en el algebra relacional puede

especificar en el algebra relacional puede especificarse también en el calculo relacional,

y viceversa; en otras palabras, el poder de expresión de dos lenguajes es idéntico. Esto

ha dado lugar a la definición del concepto de lenguaje relacionalmente completo. Se dice

que un lenguaje de consulta relacional es relacionalmente completo si es posible

expresar en L cualquier consulta que se pueda expresar en el cálculo relacional.

Calculo relacional proporciona una serie de procedimientos que genera la respuesta a la

consulta. Por eso se emplean tuplas, es decir es un lenguaje de consultas no

procedimental. Describe la información deseada sin dar un procedimiento concreto para

obtenerla.

Las consultas se expresan en el cálculo relacional de tuplas como

18


{ t | P (t) |

Es decir, es el conjunto de todas las tuplas t tales que el predicado P es cierto par t.

siguiendo la notación usada anteriormente, se usa t[A] para denotar el valor de la

tupla t en el atributo A y t € r para denotar que la tupla t está en la relación r.

Un ejemplo claro de las consultas aplicando el cálculo relacional seria:

{ t | t € préstamo ^ t [importante] > 1200}

IV.2 Algoritmos de una pasada

El algoritmo de una sola pasada es un “conjunto ordenado y finito de operaciones que

permite hallar la solución de un problema”. En términos sencillos, un algoritmo es una

“receta”, o sea, un conjunto de pases que, ejecutados de la manera, correcta, permite

obtener un resultado (en un tiempo acotado).

El algoritmo que se lee de una sola pasada es aquel que solo recibe datos de entrada y

realiza las operaciones una sola vez, son operaciones sencillas. Un algoritmo es

univoco, lo que implica algún juicio o interpretación.

IV.3 Algoritmos de dos pasadas basados en ordenamientos y en

dispersión.

Se puede ver la estructura de datos básica para la dispersión abierta. La idea

fundamental es que el conjunto (posiblemente infinito) de miembros potenciales se

divide en un número finito de clases. Si se desea tener B clases, numeradas de 0 a B-1.

Lógicamente, el valor de h (x) es la clase a al cual x pertenece. A menudo se da a x el

nombre de la clave y a h(x) el de valor de dispersión de x. a las <<clases>> se les da el

nombre de cubetas y se dice que x pertenece a la cubeta h(x).

En un arreglo llamado tabla de cubetas, indizado por los números de cubeta 0, 1,…,B-1,

se tienen los encabezamientos de B listas. Los elementos de la i-esima lista son los

19


miembros del conjunto que se está representando y que pertenece a la clase i, esto es,

aquellos elementos x del conjuntos tales que h(x) = i.

Se espera que las cubetas tengan casi el mismo tamaño, de modo que la lista para cada

cubeta sea corta. Entonces si hay N elementos en los conjuntos, en promedio, cada

cubeta tendrá N/B miembros.

IV.4 Algoritmos de más de dos pasadas.

IV.5 Algoritmos basados en índices.

IV.6 El compilador de consultas.

V Procesamiento de transacciones

V.1 Concepto, problemas.

V.2 Propiedades ACID de una transacción.

V.3 Implementación de ACID.

V.4 Seriabilidad.

VI Control de concurrencia

VI.1 Seriabilidad y sus problemas.

VI.2 Bloqueos y sus tipos.

VI.3 Deadlock: definición, manejo y prevención.

20


VI.4 Planeación.

VI.5 Métodos de control de concurrencia.

VII Sistema de recuperación

VII.1 Tipos de fallas.

VII.2 Seriabilidad.

VII.3 Recuperación.

VII.4 Tipos de almacenamiento.

VII.5 Recuperación basada en registro histórico.

VII.6 Protección contra fallas en los medios.

VII.7 Paginación sombra.

VII.8 Recuperación en transacciones concurrentes.

21


CONCLUSIONES

22


BIBLIOGRAFÍA

ELMASRI RAMEZ (1997). SISTEMAS DE BASE DE DATOS. México, DF.: Person

Educacion.

Korth Henry F. (2006). FUNDAMENTOS DE BASES DE DATOS. MEXICO, DF.: Mc

Graw Hill.

Lopez Gustavo. (2009). ANALISIS Y DISEÑO DE ALGORITMOS. MEXICO, DF.:

Alfaomega.

Addison Wesley. (1998). INTRODUCCION A LOS SISTEMAS DE BASE DE DATOS.

MEXICO, DF.: Addison Wesley Iberoamericana.

SUSAN C. LILLY. (1992). PASCAL Y ESTRUCTURAS DE DATOS. MEXICO, DF.: Mc

Graw Hill.

23

Documents

Sistemas Manejadores de Bases de Datos Con Portada