TEMA1-Gestion de Bases de Datos - RAMA

7/27/2019 TEMA1-Gestion de Bases de Datos - RAMA

1/37

Sistemas de

almacenamientode la informacin1

Ojo o

Aprender qu son y cmose utilizan los archivossecuenciales, aleatorios eindexados.

Entenderlos en un contextode evolucin histrica.

Conocer sus ventajas einconvenientes.

Entender en qu manerahan influido en el posteriordiseo de las bases dedatos relacionales.

4

4

4

4


2/37

20

GESTIN DE BASES DE DATOS RA-MA

1.1

sistema basadO en archivOs

1.1.1 histOria de lOs archivOs

Debemos entender la evolucin de las bases de datos como un proceso

continuo de modernizacin que nos ha llevado desde el papel hasta el estado

actual. Hace treinta aos, las necesidades eran menores y los grandes

ordenadores enfocaban sus objetivos a controlar los procesos bsicos de unaempresa, que en aquel momento eran la contabilidad en primer trmino y tras

ello la facturacin.

Hoy da controlamos muchas ms cosas; los procesos de la produccin; la

optimizacin de los recursos; los documentos de la empresa; los centros de

comunicacin con el cliente; la inteligencia de negocio aplicada a las ventas y

tantos otros.

En cambio, hace treinta aos, los problemas se podan solucionar con una

decena de archivos, Quin me quiere comprar algo? Mis clientes. Por tantonecesito un archivo de clientes. Quin me suministra la materia prima?

Mis proveedores. Por tanto necesitamos un archivo de proveedores. Y as

sucesivamente.

La mayor parte de las empresas de hace treinta aos utilizaban archivos de

papel, donde anotaban los datos de sus clientes en forma de fichas escritas con

una mquina de escribir de la poca.

Por eso los archivos tambin reciban el nombre de ficheros, y por esa razn

tambin la primera informatizacin empezaba por pasar del sistema de fichasde papel o de cartulina a un sistema informatizado.

La principal ventaja del sistema informatizado estaba en evitar tiempo

para encontrar una ficha de papel dentro de un enorme cajn de fichas. Poder

encontrar una ficha en menos de un minuto ya era una importante diferencia

con respecto a enviar a una persona a buscarla a otra planta del edificio (el

archivo de muchas empresas sola estar en los stanos) y trarnosla al cabo de

cinco minutos.

Pasbamos, pues, de un sistema en que el soporte era papel, a un nuevosistema en el que el soporte era digital.


3/37

21

RA-MA 1 n SISTEMAS DE ALMACENAMIENTO DE LA INFORMACIN

1.1.2 mtOdOs de accesO a lOs datOs

Toda la historia de los archivos ha ido ligada al avance de la tecnologa;principalmente del hardware y en menor medida del software.

A continuacin vamos a ver cuatro tipos de archivos, aunque los ms

utilizados han sido tres:

1 Archivos secuenciales.

2 Archivos de acceso aleatorio.

3 Archivos indexados.

4 Archivos hash.

Los archivos de los tipos 1, 2 y 3 son los ms comunes, puesto que cuando

se empezaron a utilizar los archivos hash, el concepto de base de datos cambi

y se cuestion tambin el complejo sistema hash frente a sus mejoras de

rendimiento.

Veamos con detalle estos tipos de acceso a los archivos.

1.2 archivOs secuenciales

Situmonos en la poca. Los sistemas de almacenamiento fsico eran

tambores de cinta magntica de un dimetro comparable al de los antiguos

discos de vinilo conocidos como LP.

En casa es posible que nuestros padres tengan an unas cintas de msica

llamadas cassettes. Pues bien, las unidades de cinta informticas eran como

unos cassettes gigantes donde se almacenaban datos digitales: ceros y unos enorden secuencial.


4/37

22


Qu quiere decir secuencial? Que van ordenados en posiciones sucesivas,

y que si queremos llegar a la posicin nmero 100, debemos pasar antes por la

1, la 2 y as sucesivamente; secuencialmente.

Este era el hardware que tenamos y el software de gestin ms sencillo era

el procesador de textos.

No pensemos en un procesador de textos como Word. Word es una maravilla

comparado con lo que haba en la poca. No haba tipos de letra. No podamos

ver cmo quedaba el formato del documento. Tenamos editores de lneas; es

decir, disponamos de instrucciones para abrir un archivo concreto quedndonos

en la lnea cero por defecto; otros comandos para desplazarnos hasta una lnea,

mostrar su contenido; modificar a partir de una posicin y almacenar loscambios lnea a lnea. Tras ello, con otro comando grabbamos el archivo y

finalmente con el comando Q salamos de nuevo a la pantalla negra del sistema

operativo.

El sistema ms normal para crear un archivo de clientes era escribir su

nombre, separar con un retorno de carro, escribir su direccin seguida de otro

retorno de carro, poblacin y as sucesivamente.

Entre cliente y cliente se colocaba una marca de final de bloque que indicaba

el inicio de los datos de un nuevo cliente o bien el final del archivo de clientes.

Cada uno de estos bloques con los datos de un cliente recibe el nombre de

registro y cada una de estas informaciones (nombre, direccin, poblacin, etc.)

recibe el nombre de campo.

Por tanto, un registro se compone de campos.

Veamos un ejemplo:

Juan Martnez

Calle del Pez, 5

Madrid

Comercial Martnez

Calle de la Cuesta, 10

Sevilla

Jos Snchez

Calle Mayor, 7

Salamanca


5/37

23


1.2.1 utilidad de lOs archivOs secuenciales paraimprimir

Este tipo de archivos era muy til si tena justamente este formato, puesto

que serva para imprimir etiquetas y enviar circulares. La marca que

tambin poda sustituirse por un punto solitario, quedaba en el espacio entre

etiquetas y no se vea.

Esto funcionaba siempre que tuvisemos el cuidado de colocar bien el

cabezal de la impresora en la primera etiqueta. Si no, tenamos que abortar el

listado porque las etiquetas salan desplazadas. Y a repetir de nuevo.

Qu era el cabezal de la impresora? Slo tenamos impresoras de agujas.

Las lser tardaron ms tiempo en salir al mercado y su precio era prohibitivo

para la mayor parte de empresas; slo las compraban las imprentas!

Las impresoras de agujas disponan de un cabezal con una matriz de filas

de 9 agujas que golpeaban una cinta empapada en tinta, dejando la huella del

impacto sobre el papel o en este caso sobre la etiqueta.


6/37

24


Pues bien, este era el sistema de trabajo con un archivo de clientes, y en la

primera poca eran slo los informticos (con bata blanca) los autorizados a

trabajar con los editores de lneas para confeccionar los archivos de clientes.

Imprimir las etiquetas para enviar las cartas era un trabajo que, si se haca

a mquina, podra tardar semanas. Con el ordenador y la impresora se poda

hacer en media hora.

1.2.2 caractersticas de lOs archivOs secuenciales

1.2.2.1 l o ogo

Para leer un registro situado en medio del archivo debemos pasar por todos

los registros anteriores.

1.2.2.2 no oo (fow o)

En los archivos secuenciales se realiza la lectura slo hacia delante. Por

ejemplo: si nosotros leemos el primer registro del cliente, el segundo, el tercero,

el cuarto y despus deseamos volver al segundo, la nica forma de hacerlo

consiste en cerrar el archivo y volver a abrirlo, ya que no podemos retroceder.

1.2.2.3 lo o o ooo

Los archivos secuenciales no permiten el acceso simultneo (concurrencia)

de varios usuarios. Si por desventura se accediera simultneamente en modo

escritura, los resultados son impredecibles: puede producirse corrupcin de

datos por escrituras entremezcladas o desaparicin inadvertida de datos. Elltimo que escribe tiene mayores posibilidades de mantener su informacin.

Evitemos la concurrencia en archivos secuenciales.

1.2.2.4 e g o

Todos los registros deben apareceren orden. Esto quiere decir que si nosotros

escogemos el orden Nombre, Direccin, Poblacin en el primer registro, no

podemos cambiarlo por Direccin, Poblacin, Nombre en el siguiente registro.

El programa de lectura de un archivo secuencial va a ciegas leyendo lneas y

necesita saber qu significado tiene cada lnea segn su orden.


7/37

25


Pero, qu pasa si queremos grabar ms datos de cada cliente? Por ejemplo

su telfono o su cdigo fiscal, o sus condiciones de pago

La primera consecuencia es que debemos rehacer todos los programas de

lectura para tener en cuenta estos nuevos campos. Y esto puede representar

mucho trabajo si tenemos que acabarlo de un da para otro.

La segunda consecuencia es que ese archivo ya no nos servira para imprimir

etiquetas. Tendramos que guardar un archivo central con todos los datos y, a

partir de ste, extraer en otro archivo slo los datos que deseamos imprimir.

Tras ello ya podramos lanzar el nuevo listado por la impresora. Por tanto,

debemos crear un nuevo proceso y complicar el que ya tenamos.

1.2.2.5 e oo oo o

Las lecturas y las escrituras dependen del modo en que se haya abierto un

archivo secuencial. En el momento de abrir un archivo, dependiendo del modo

que hayamos escogido, quedaremos autorizados a leer o a escribir, pero no a

las dos cosas.

1.2.2.6 l o o

Las operaciones de lectura pueden ser parciales, pero las operaciones de

escritura conllevan obligatoriamente la escritura total de toda la secuencia

completa de registros.

Dicho de otro modo: al abrir un archivo en modo escritura estamos borrando

su contenido anterior si lo hubiere.

Por esta razn algunos lenguajes de programacin contienen un modo de

apertura llamadoAppend que escribe al final de un archivo existente en vezde reescribirlo de nuevo.

1.2.2.7 l f o (eOF)

Las operaciones de lectura deben comprobar siempre que no rebasan el

final del archivo secuencial, mediante la comparacin del carcter de final

de archivo (EOF o End Of File). Este carcter se coloca siempre y de modo

implcito al cerrar un archivo secuencial en modo escritura.


8/37

26


1.2.2.8 boo go oo oo

El borrado de un registro puede hacerse por varios mtodos, aunque el ms

utilizado consiste en la escritura de todos los registros menos el que deseamos

eliminar.

Otro sistema es mantener la informacin, pero marcarla como borrada, lo

cual implica hacer consideraciones de programacin ms complejas.

1.2.2.9 l o o oo

Existe una posibilidad realmente una tcnica que no se utilizaba en los

primeros aos del uso de los archivos secuenciales y que tiene que ver con la

marca de sincronismo entre registros.

La marca de sincronismo es una lnea con un conenido especfico que es

palabra reservada. Es decir, si la marca que nosotros elegimos es ,

no puede haber ningn cliente que se llame ni ninguna direccin ni

poblacin que sea .

Por tanto, cuando nosotros veamos en una lnea un contenido aislado como

la palabra reservada sabremos que se acaba un registro y a continuacin

empieza otro con el mismo orden.

Esto nos permite crear registros con campos que tienen este orden:

Nombre

Direccin

Poblacin

CIF

Telfono

Email


9/37

27


Y nos permite tambin mezclar registros con diferentes estructuras, siempre

que haya una parte inicial comn:

Nombre

Direccin

Poblacin

CIF

Telfono

Email

Nombre

Direccin

Poblacin

Nombre

Direccin

Poblacin

CIF

Telfono

Email

La tcnica se basa en la lectura lnea a lnea. Cuando se descubre que

el contenido de una lnea es , sabemos que el siguiente campo es el

primer campo del siguiente registro y que, por tanto, debemos omitir la lectura

de los posibles campos que puedan seguir pertenecientes al registro actual.


10/37

28


1.2.2.10 rgo og

Los registros de un archivo secuencial tienen una longitud variable porque

tambin sus campos tienen una longitud variable.

No ocupa el mismo espacio un cliente que se llameJuan Snchez, que otro

cliente que se llameJos Mara Gonzlez de Castro y Santos de Carballar.

Esto implica que a priori no vamos a saber el tamao de las variables que

debemos usar en memoria para almacenar estos contenidos.

Para superar este tipo de problemas apareci el archivo de acceso aleatorio,

que veremos ms adelante.

1.2.2.11 coo g oo xo

El contenido de un archivo secuencial es legible en un procesador de

textos.

Pas mucho tiempo antes de que aparecieran los editores de pantalla

completa que permitan mover el cursor hasta la lnea que queramos con las

flechas del teclado o con combinaciones de teclas.

El primero de ellos fue Wordstar y aqu ya empezamos a hablar de

procesadores de textos. No funcionaban por comandos sino por combinaciones

de teclas. En este momento las mquinas de escribir ya empezaban a estar

amenazadas.


11/37

29


1.2.2.12 coo o o o o

Los archivos secuenciales siguen siendo buenas opciones para

almacenamiento de pocos registros en los que la velocidad de acceso no sea un

punto clave.

Todos los sistemas operativos soportan operaciones de lectura y escritura

sobre archivos secuenciales.

Todos los lenguajes de programacin estn dotados de funciones para

acceder a archivos secuenciales.

Los programas encargados de las altas, bajas, modificaciones, consultas,listados y otras operaciones que afectan exclusivamente a un archivo (por

ejemplo, clientes) reciben el nombre de mantenimientos.

Podemos, pues, realizar mantenimientos de archivos secuenciales mediante

programas escritos en lenguajes de todo tipo: antiguos y modernos, como BASIC,

Pascal, Fortran, COBOL, C/C++, Java, Visual Basic, C#, Prolog, LISP, etc.

En nuestro caso vamos a utilizar cuatro lenguajes de gran difusin comercial

y acadmica:

1. Visual C++.

2. Visual Basic 6.0.

3. Java.

4. C#.

En las actividades encontraremos ejemplos en estos cuatro lenguajes.

1.3

archivOs de accesO aleatOriO

Si los archivos secuenciales se emparejan en el tiempo con el hardware de

los tambores de cinta magntica, los archivos de acceso aleatorio aparecen con

el disquete y el disco duro.


12/37

30


Los archivos de acceso aleatorio no estn sujetos a la esclavitud de pasar

por el inicio hasta llegar a la porcin de la informacin que nos interesa.

En los archivos de acceso aleatorio podemos colocarnos en una posicin

determinada expresada por un nmero.

Por ejemplo, podemos ir directamente a la posicin 100, volver atrs hasta

la posicin 20, avanzar ahora hasta la 200 y as tantas veces como queramos.

Esto implica que si utilizamos una estructura delimitada en longitud,podemos calcular la posicin en la que debemos situarnos para leer un

registro.

La medida bsica de la posicin del puntero de lectura es el byte; primer

byte, segundo byte y as sucesivamente.

Esto quiere decir que, si empleamos caracteres de dos bytes (por ejemplo,

en Unicode), las posiciones para leerlos sern la 0, la 2, la 4, etc., avanzando

cada vez de dos en dos.

Pongamos por caso que tenemos un registro como ste codificado en ANSI

(1 byte por carcter):

Nombre: 80 caracteres ANSI

Direccin: 100 caracteres ANSI

Poblacin: 50 caracteres ANSI

Su longitud ser de 230 caracteres. Esto implica que el primer registro se

encontrar en la posicin 0; el segundo registro se encontrar en la posicin

230; el tercero estar en la posicin 460 y as sucesivamente.

n

n

n


13/37

31


Por tanto, podemos decir que la posicin ser:

Pos = NumRegistro * LongitudRegistro

Si en cambio codificamos los caracteres en Unicode (UTF-16) de forma que

su longitud es de 16 bits por carcter, esto es 2 bytes, el registro quedar as:

Nombre: 80 caracteres UTF-16.

Direccin: 100 caracteres UTF-16.

Poblacin: 50 caracteres UTF-16.

Su longitud ser de 460 caracteres para un solo registro, ya que cada

carcter ocupa 2 bytes.

Ya tenemos la manera de calcular la posicin. Ahora, cada lenguaje de

programacin dispondr de su propia funcin para el posicionamiento del

cursor de lectura o de escritura para realizar el acceso aleatorio.

1.3.1 Qu sucede si un campO es de tipO numricO?

En los archivos secuenciales se guardaba el nmero con su formato

expresado en decimal: dgito a dgito. Por tanto, el nmero 10 ocupaba 2

caracteres y el nmero 1234567 ocupaba 7 caracteres.

En los archivos aleatorios no se guardan los dgitos, sino el valor binario.

Un nmero entero simple de 16 bits (de 0 a 65535) emplea 2 bytes.

n

n

n


14/37

32


Si se trata de un nmero entero de 32 bits (de 0 hasta 4.000 millones

aproximadamente) ocupa 4 bytes.

Si se trata de un nmero en coma flotante (normalmente se ajustan a la

norma IEE488 como Excel) usa 8 bytes para almacenar mantisa y exponente.

Estos datos ya no son legibles con un procesador de texto y si intentamos

leerlos nos aparecern caracteres extraos, con posibilidad de que el contenido

no aparezca entero, ya que es frecuente encontrar un valor binario que coincida

con el valor EOF (final de archivo).

1.3.2 caractersticas de lOs archivOs de accesOaleatOriO

1.3.2.1 pooo o

Permiten situar el puntero de lectura o escritura sobre una posicin

concreta del archivo sin necesidad de pasar por las posiciones anteriores,

con el consiguiente incremento de rapidez. Una sola apertura proporciona la

capacidad de avanzar y retroceder sin necesidad de reabrir el archivo.

1.3.2.2 rgo og fj

Todos los registros tienen la misma longitud, ya que se utiliza siempre una

estructura rgida dimensionada a la mxima longitud para cada campo.

1.3.2.3 a /

Permiten su apertura en modo mixto (lectura y escritura), de forma que con

una sola operacin de apertura podemos leer o escribir a voluntad en cualquier

posicin segn nos convenga.

1.3.2.4 p o o (o)

Al establecerse zonas especficas y limitadas de actuacin para lectura y

escritura, diversos usuarios pueden acceder y escribir en diferentes porciones

del archivo de forma simultnea.


15/37

33


Esto lleva a considerar la posibilidad de concurrencia de dos usuarios en

el mismo registro. Para ello se utilizan algoritmos de gestin de los bloqueos.

Dichos algoritmos administran zonas (que no siempre coinciden con registros)y las marcan para evitar dicha concurrencia de forma temporal. El tema del

bloqueo lo trataremos ms adelante dentro de los captulos dedicados a bases

de datos relacionales.

1.3.2.5 doo xo o

Los archivos de acceso aleatorio deben dimensionarse hasta un nmero de

registros mximo en el momento de crearse.

1.3.2.6 boo go o

El borrado de un registro se realiza poniendo a 0 el espacio que ocupa;

rellenndolo con bytes con el valor binario 0. En sistemas ms complejos se

emplea un algoritmo de reutilizacin de gaps o espacios vacos, o incluso de

compactacin.

Si empleamos un algoritmo de compactacin de registros degaps, deberemos

ser conscientes de que el nmero de registro cambiar para un cliente dado

en el momento en que se reubica, por lo cual una clave de acceso basada en

nmero de registro no tendr validez.

Si utilizamos un algoritmo de reutilizacin degaps deberemos ser concientes

de que un cliente nuevo puede reutilizar el espacio de un cliente borrado. Por

tanto, si utilizamos referencias a su nmero de registro en otros archivos,

deberemos ser cuidadosos de que un cliente no sea falsamente referenciado en

otros archivos.

Estos son problemas de integridad referencial que se resuelven mejor en

sistemas gestores de bases de datos, como veremos ms adelante, y que fueron

una de las razones para realizar el cambio desde el sistema de informacin

basado en archivos al sistema de informacin basado en bases de datos.


16/37

34


1.3.3 cOnsideraciOnes adiciOnales sObre lOs archivOsde accesO aleatOriO

Los archivos de acceso aleatorio estn especialente indicados para

aquellos casos en que el cdigo del registro (cliente, proveedor, etc.) pueda ser

directamente el nmero de registro en el que se guardan los datos.

Al trabajar con archivos de acceso aleatorio deberemos tener en cuenta no

rebasar nunca el final de archivo. Si nuestro archivo est dimensionado hasta

100 registros, intentar que no haya ningn usuario que nos pregunte por el 101

o por el 200. Para ello deberemos establecer nuestros sistemas de prevencin

desde el interfaz o desde el sistema de clculo de la posicin del puntero de

lectura / escritura.

Los archivos de acceso aleatorio son un paso ms que nos conduce por el

camino de los archivos indexados, puesto que constituyen el depsito de los

datos. Como veremos ms adelante, el almacenamiento temporal o no de las

claves es el elemento que lo diferencia de los indexados.

1.4

archivOs indeXadOs

Los archivos indexados son bsicamente archivos de acceso aleatorio a los

que se aade una utilidad para acceder al registro deseado a travs de una

clave.

En el caso de los archivos de acceso aleatorio, la clave es siempre el nmero

de registro.

Los archivos indexados pueden buscar un cliente segn su nombre, segn

su cdigo de identificacin fiscal o segn cualquier otro campo.

Para ello se construye una estructura de ndice por cada campo que se desea

indexar.

Esta estructura de ndice se mantiene en la memoria RAM de forma

ordenada, de manera que podamos encontrar rpidamente una relacin entre

el apellido de un cliente y el nmero de registro en el que se encuentra.


17/37

35


Esto es lo que permite realizar las bsquedas por clave sin necesidad de

recorrer todos los registros de la base de datos.

Tradicionalmente, la estructura de informacin utilizada para localizar los

registros por clave es el rbol binario o rbol de ndices.

1.4.1 histOria y FunciOnamientO bsicO de lOs rbOlesde ndices

En el ao 1962, Giorgi Maxmovich Adelson-Velskii y Yevgueni Mijilovich

Landis, dos matemticos rusos, crearon un sistema de acceso muy rpido

llamado rbol AVL (Adelson-Velskii-Landis).

Un rbol se compone de nodos, que son los que contienen la informacin

de la clave y del nmero de registro en donde se encuentran los datos que nos

interesan.

Dentro de un nodo tenemos:

1. El propio valor de la clave.

2. Un dato til para referenciar en donde se encuentran los campos del

registro, como por ejemplo, un nmero de registro para ir a buscar los

datos.

3. Un puntero hacia un nodo que contenga una clave con un valor inferioro un nulo si no la hay, a la que llamaremos puntero L (de left o puntero

a la izquierda).

4. Un puntero hacia un nodo con una clave mayor o un nulo si no la hay, a

la que llamaremos R (de right o puntero a la derecha).

5. Otros datos interesantes para conocer rpidamente el estado del rbol,

como por ejemplo la altura del nodo respecto a la base del rbol o el

factor de equilibrio, que son datos que veremos ms adelante. Los rboles

binarios se representan al revs, como una coliflor boca abajo, en la quela raz est siempre arriba.


18/37

36


Veamos un ejemplo de rbol en el que ordenaremos nmeros:

A la izquierda de cada nodo colgamos un elemento ms pequeo que el

propio y a la derecha colgamos un elemento ms grande.

En todos los procesos de bsqueda mediante rboles, se entra a buscarsiempre por la raz.

Imaginemos que estamos buscando el nmero 4.

Entramos por la raz, que es el 5.

Es ste el que buscamos? No. Es menor? S. Nos vamos hacia la

izquierda.

Encontramos el 3. Mayor, menor o igual que 4? Mayor.

Nos vamos hacia la derecha y lo encontramos. Hemos realizado 3

comparaciones hasta llegar al dato que buscamos.

Esto es ms lgico que emplear una lista ordenada, ya que en una lista los

nmeros se organizaran as:

1

2

34

5

6

7

En el caso de buscar el mismo nmero, el 4, el nmero de comparaciones

sera el mismo que empleando un rbol.

Si buscsemos el nmero 2 en la lista, el nmero de comparaciones sera 1,

ms rpido que con el rbol.


19/37

37


En cambio, si buscramos el 7, deberamos hacer 6 comparaciones; mucho

ms lento, puesto que el rbol slo tiene 3 niveles. En un rbol de 8 elementos,

la altura mxima del rbol es de 3 niveles. No har falta nunca rebasar 3comparaciones para llegar al dato que buscamos, independientemente de si es

grande o pequeo.

En una lista ordenada, el nmero de comparaciones crece linealmente en

funcin de la cantidad de elementos que almacenamos en la lista.

En cambio, con el rbol, el nmero de comparaciones queda mucho ms

contenido. Comparemos el peor de los casos en cada sistema.

Tabla 1.1

rbol Lista ordenada

8 elementos 3 8

16 elementos 4 16

32 elementos 5 32

64 elementos 6 64

128 elementos 7 128

Si nos fijamos, veremos que 8 es 23. Por tanto, en un rbol de N elementos,

el nmero de comparaciones mximo es el logaritmo en base 2 de los elementos

contenidos.

Los rboles ya se conocan antes de Adelson-Velskii y Landis. Eran y son

llamados rboles BST oBinary Search Tree, pero a pesar de que agilizaban el

acceso a los datos, se podan mejorar.

Por qu?

Porque los rboles que empezaban teniendo 10 o 15 elementos eran muyrpidos, pero cuando iban creciendo exista el riesgo de crecer de forma

asimtrica; se iban descontrolando; crecan de forma asimtrica.

La palabra asimtrica expresa un crecimiento desequilibrado en el que unas

ramas acaban siendo mucho ms largas que otras, causando una desproporcin

en el nmero de pasos que deben darse (nmero de comparaciones necesarias)

para llegar hasta encontrar una clave dependiendo de en qu rama se

encuentre.


20/37

38


Este rbol respeta las normasL


21/37

39


Podemos tener algoritmos de autoequilibrado ms veloces y menos veloces.

Todos hemos tenido experiencias con bases de datos que cada cierto tiempo

denegaban peticiones porque se estaban reorganizando ndices. Posiblementeno lo sabamos, pero durante unos segundos la base de datos se quedaba

congelada y no nos atenda porque se estaba reorganizando internamente.

El tema es complejo y se centra en dos cuestiones:

1. Decidir si vamos a reevaluar el autobalanceo del rbol en cada nueva

insercin de datos (lo cual empeora la velocidad de insercin) o si vamos

a hacerlo cada cierto tiempo o cada cierto nmero de inserciones (lo cual

causa ese lapso de denegacin de servicio).

2. Una vez decidido si vamos por uno u otro camino, encontrar la manera

de que la reorganizacin sea lo ms rpida posible en la bsqueda del

algoritmo ptimo.

En 1976, Colin Day propuso un algoritmo bastante rpido, escrito en

lenguaje FORTRAN, que fue traducido a lenguaje Pascal, para ganar en

estructuracin y recursividad, y modificado en 1988 por Quentin Stout y Bette

Warren dando origen 12 aos ms tarde al algoritmo conocido como DSW (Day-

Stout-Warren).

Se trata de un algoritmo elegante que se basa en una teora apoyada en dos

funciones: una Tree-To-Vine (de rbol hacia sarmiento o vara) y otra simtrica

Vine-To-Tree (de sarmiento o vara hacia rbol). La teora se basa en que se

puede construir un rbol equilibrado si los datos de las claves se suministran

en orden.

Por tanto, se recorre el rbol de forma ordenada (recorrido In-order) y se

genera un rbol completamente lineal y degenerado. Resultado: una vara o

rama nica. Como si slo tuvisemos una lista con nodos que tuviesen un nicopuntero L y careciesen de puntero R.

Despus se reconstruye el rbol a partir de la vara, suministrando los datos

ordenadamente, montando los nodos a base de rotaciones progresivas.

Despus vinieron cuestiones sobre cmo atravesar el rbol de forma ptima,

con o sin recursividad, utilizando los algoritmos de Frank M. Carrano y de

Mark A. Weiss, siendo ste un alumno de Robert Sedgewick de la Universidad

de Princeton.


22/37

40


Sedgewick realiz aportaciones finales de funciones auxiliares que fueron

recogidas en el libroAlgorithms in C++,Parts 1-4 (Fundamental Algorithms,

Data Structures, Sorting, Searching) de Addison-Wesley, Boston 1998.

Timothy Rolfe optimiz al mximo el cdigo con todas estas consideraciones

y lo emple en la Eastern Washington University, como material de apoyo para

dar clases de estructuras de informacin y algoritmos.

En Espaa, el profesor Ceballos de la Universidad Complutense de Alcal,

viene difundiendo y estructurando desde hace aos en sus clases y en sus libros

los rboles y los algoritmos de equilibrado.

1.5

actividades

Las actividades que implican cdigo fuente se encuentran en el CD ROM

del libro dentro de la carpeta \Actividades\Captulo 1

Para archivos secuenciales:

1. Escribir un programa que genere un archivo secuencial llamado

CLIENTES.TXT en el que grabaremos tres registros de clientes como

los expuestos en el ejemplo anterior, con los campos de nombre, direccin

y poblacin.

2. Abrir el archivo con el bloc de notas de Windows (Notepad.exe) y verificar

que su contenido es legible.

3. Escribir un programa de lectura de un archivo secuencial lnea a lnea

mediante un bucle que verifique el final de archivo.

Para archivos de acceso aleatorio:

4. Escribir un programa de creacin de un archivo de acceso aleatorio

para un archivo de clientes (CLIENTES.DAT) con un espacio de

almacenamiento de 10 registros, en el cual se escriban los tres primeros

clientes que ya utilizamos en el ejemplo anterior. Escribir una funcin

dentro de este programa que, dado un nmero de registro entre 0 y 9,

nos permita recuperar el contenido de uno de los registros anteriores.


23/37

41


Para archivos indexados:

5. Trabajar con el programa de ejemplo Actividad5 que se encuentra en el

CD ROM del libro. Investigar cules son sus funcionalidades y revisar en

el cdigo fuente cul es el procedimiento interno para manejar el rbol

binario de indexacin, el archivo de datos y el interfaz de la aplicacin.

1.5.1 actividad 1

Escogeremos un lenguaje de programacin de entre los cuatro propuestos:

C++Visual Basic 6.0

Java

C#

1.5.1.1 a 1a: e gj c++

En lenguaje C++, este fragmento de cdigo fuente se encarga de generar

un archivo secuencial y rellenarlo con tres clientes, cerrando el archivo a

continuacin. Se trata de una aplicacin muy sencilla en modo consola (pantalla

de texto). El ejemplo ha sido compilado con Microsoft Visual C++. Si se desea

compatibilizarlo con otros compiladores de C como GNU C, se debe sustituir el

# fx. por #

#include stdafx.h

#include io.h

int main(int argc, char* argv[])

{FILE * pArchivo;

printf(Ejemplo de escritura de tres registros en

archivo secuencial\n);

pArchivo = fopen(CLIENTES.TXT, w);

if (pArchivo)

{

//Primer cliente:fprintf(pArchivo, %s\n, Juan Martnez);

44

4

4


24/37

42


fprintf(pArchivo, %s\n, Calle del Pez, 5);

fprintf(pArchivo, %s\n, Madrid);

fprintf(pArchivo, %s\n, );

//Segundo cliente:

fprintf(pArchivo, %s\n, Comercial Martnez);

fprintf(pArchivo, %s\n, Calle de la Cuesta, 10);

fprintf(pArchivo, %s\n, Sevilla);


//Tercer cliente:

fprintf(pArchivo, %s\n, Jos Snchez);

fprintf(pArchivo, %s\n, Calle Mayor, 7);

fprintf(pArchivo, %s\n, Salamanca);


//Cerrar el archivo:

fclose(pArchivo);

printf(%s\n, 3 registros escritos.);

}

else{

printf(%s\n,No se ha podido abrir el archivo para

escritura.);

}

printf(%s\n, Final de programa);

return 0;

}

1.5.1.2 a 1b: e gj v b 6.0

En lenguaje Visual Basic 6.0, este fragmento de cdigo fuente se encarga de

generar un archivo secuencial y rellenarlo con tres clientes, cerrando el archivo

a continuacin.

Private Sub Command1_Click()

On Error GoTo manejador


25/37

43


MsgBox (Ejemplo de escritura de 3 registros en un archivo

secuencial)

ChDir App.Path

Open CLIENTES.TXT For Output As #1

Primer cliente:

Print #1, Juan Martnez

Print #1, Calle del Pez, 5

Print #1, Madrid

Print #1,

Segundo cliente:

Print #1, Comercial Martnez

Print #1, Calle de la Cuesta, 10

Print #1, Sevilla

Print #1,

Tercer cliente:

Print #1, Jos Snchez

Print #1, Calle Mayor, 7

Print #1, SalamancaPrint #1,

Cerrar el archivo:

Close #1

MsgBox (3 registros escritos.)

Exit Sub

manejador:

MsgBox (Err.Description)End Sub

1.5.1.3 a 1c: e gj J

En lenguaje Java, este fragmento de cdigo fuente se encarga de generar

un archivo secuencial y rellenarlo con tres clientes, cerrando el archivo a

continuacin.

import java.io.*;


26/37

44


public class Actividad1C

{

public static void main (String[] args)

{

FileWriter archivo = null;

try

{

System.out.println(Ejemplo de escritura de 3

registros en un archivo secuencial\r\n);

//Cliente 1:

archivo = new FileWriter(CLIENTES.TXT);

archivo.write(Juan Martnez\r\n);

archivo.write(Calle del Pez, 5\r\n);

archivo.write(Madrid\r\n);

archivo.write(\r\n);

//Cliente 2:

archivo.write(Comercial Martnez\r\n);

archivo.write(Calle de la Cuesta, 10\r\n);

archivo.write(Sevilla\r\n);


//Cliente 3:archivo.write(Jos Snchez\r\n);

archivo.write(Calle Mayor, 7\r\n);

archivo.write(Salamanca\r\n);


archivo.close();

System.out.println(3 registros grabados.\r\n);

}

catch(IOException e)

{System.out.println(Error: +e.toString());

}

}

}

1.5.1.4 a 1d: e gj c#

En lenguaje C#, este fragmento de cdigo fuente se encarga de generar

un archivo secuencial y rellenarlo con tres clientes, cerrando el archivo acontinuacin.


27/37

45


using System;

using System.Collections.Generic;

using System.Text;

using System.IO;

namespace Actividad1D

{

class Program

{

static void Main(string[] args)

{

StreamWriter archivo = null;

try

{

Console.WriteLine(Ejemplo de escritura de 3

registros en un archivo secuencial);

archivo = new StreamWriter(CLIENTES.TXT);

if (archivo!=null)

{

//Cliente 1:archivo.WriteLine(Juan Martnez);

archivo.WriteLine(Calle del Pez, 5);

archivo.WriteLine(Madrid);

archivo.WriteLine();

//Cliente 2:

archivo.WriteLine(Comercial Martnez);

archivo.WriteLine(Calle de la Cuesta, 10);

archivo.WriteLine(Sevilla);

archivo.WriteLine();//Cliente 3:

archivo.WriteLine(Jos Snchez);

archivo.WriteLine(Calle Mayor, 7);

archivo.WriteLine(Salamanca);



//Cerrar el archivo:

archivo.Close();

Console.WriteLine(3 registros grabados.);

}

}


28/37

46


catch(IOException e)

{

Console.WriteLine(Error: +e.ToString());

}

}

}

}

1.5.2 actividad 2

Para esta actividad no es necesario recurrir a ninguno de los archivos

contenidos en el CD ROM que acompaa al libro.

Abrir el archivo con el bloc de notas de Windows (Notepad.exe) y verificar

que su contenido es legible.

En esta actividad verificaremos que el contenido generado dentro del

archivo secuencial se corresponde con texto y adems veremos las diferencias

entre las diferentes pginas de cdigos que usa por defecto cada lenguaje.

Para abrir los textos utilizaremos el bloc de notas de Windows.

En todos los ejemplos, el resultado ser el mismo, pero con diferencias en

las pginas de cdigo.

En el ejemplo de la actividad 1.1, 1.2 y 1.3, correspondientes respectivamente

al programa escrito en lenguaje C++ (Visual C++ v.6.0), el programa escrito en

Visual Basic 6.0 y el programa escrito en Java, el archivo resultado est escrito

en cdigo ANSI de Windows.

En cambio, en el ejemplo de la actividad 1D, correspondiente al programa

escrito en C#, el resultado est escrito en Unicode de 8 bits (UTF-8), locual quiere decir que no es compatible binariamente con los tres formatos

anteriores.

Este es un punto a tener en cuenta cuando debemos afrontar migraciones

de datos entre aplicaciones escritas en diferentes lenguajes.


29/37

47


1.5.3 actividad 3

Escribir un programa de lectura de un archivo secuencial lnea a lneamediante un bucle que verifique el final de archivo.

1.5.3.1 a 3a: e gj c++

Un programa mnimo de lectura de un archivo secuencial y salida hacia

pantalla quedara as:

#include stdafx.h

#include

//Actividad 3A:

//Lectura de archivo secuencial con tres clientes.

int main(int argc, char* argv[])

{

FILE * pArchivo = NULL;

char szLinea[255];

pArchivo = fopen(CLIENTES.TXT, r);if (pArchivo)

{

while (!feof(pArchivo))

{

memset(szLinea, 0, sizeof(szLinea));

fgets(szLinea, 255, pArchivo);

//Eliminar ltimo caracter LF:

*(szLinea + strlen(szLinea)-1)=0;

printf(%s\n, szLinea);}

fclose(pArchivo);

}

return 0;

}


30/37

48


1.5.3.2 a 3b: e gj v b 6.0

A continuacin exponemos el cdigo fuente contenido en una funcin que

reacciona a la pulsacin de un botn. Lee el contenido del archivo secuencial

lnea a lnea y lo coloca en una caja de lista:

Private Sub Command1_Click()

Dim Linea As String

ChDir App.Path

Open CLIENTES.TXT For Input As #1

While Not EOF(1)

Line Input #1, LineaList1.AddItem (Linea)

Wend

Close #1

Exit Sub

manejador:

MsgBox (Err.Description)

End Sub

1.5.3.3 a 3c: e gj J

Este es el programa Java que lee lnea por lnea un archivo secuencial:

import java.io.*;

public class Actividad3C

{

public static void main(String[] args)

{

File archivo = null;DataInputStream flujo = null;

String strLinea = ;

System.out.println(Ejemplo de lectura de un archivo

secuencial\r\n);

try

{

//Verificar si existe el archivo CLIENTES.TXT);

archivo = new File(CLIENTES.TXT);

if (archivo.exists())


31/37

49


{

flujo = new DataInputStream(new

BufferedInputStream(new

FileInputStream(archivo)));

while (strLinea != null)

{

strLinea = flujo.readLine();

//o readUTF para UTF-16

if (strLinea!=null) System.out.println(strLinea);

}

}

flujo.close();

}

catch (EOFException e)

{

//Final de archivo

System.out.println();

}

catch (IOException e2)

{

System.out.println(e2.getMessage());

}}

}

1.5.3.4 a 3d: e gj c#

Este es el fragmento de cdigo fuente que lee un archivo secuencial lnea a

lnea, escrito en C#. Reacciona a la pulsacin de un botn sobre un formulario

de Windows.

private void button1_Click(object sender, EventArgs e)

{

StreamReader lector;

string strLinea;

try

{

lector = new StreamReader(CLIENTES.TXT);

while (!lector.EndOfStream){


32/37

50


strLinea = lector.ReadLine();

listBox1.Items.Add(strLinea);

}

lector.Close();

}

catch(IOException ex)

{

MessageBox.Show(ex.Message);

}

}

1.5.4 actividad 4

En esta actividad llevaremos a la prctica dos objetivos:

1. Escribir un programa de creacin de un archivo de acceso aleatorio

para un archivo de clientes (CLIENTES.DAT) con un espacio de

almacenamiento de 10 registros, en el cual se escriban los tres primeros

clientes que ya utilizamos en el ejemplo anterior.

2. Escribir una funcin dentro de este programa que, dado un nmero deregistro entre 0 y 9, nos permita recuperar el contenido de uno de los

registros anteriores.

En este caso, por razones de espacio slo elaboraremos el programa en C++.

Se trata de un programa Windows basado en un formulario en el que el cdigo

fuente asociado a la pulsacin de un botn genera el archivo de acceso aleatorio

y escribe los tres clientes iniciales de ejemplo.

typedef struct tagCliente

{char Nombre[80];

char Direccion[100];

char Poblacion[50];

} cliente;

void CActividad4AView::OnCrearArchivo()

{

FILE * pArchivo;

tagCliente MiCliente;

tagCliente Cliente1;


33/37

51




int nLongRegistro = sizeof(tagCliente);

int n;

pArchivo = fopen(CLIENTES.DAT, wb);

if (pArchivo)

{

//Escribir los 10 registros:

memset(&MiCliente, 0, sizeof(tagCliente));

for (n=0;n


34/37

52


Ahora vamos a tratar el siguiente objetivo: escribir una funcin dentro

de este programa que, dado un nmero de registro entre 0 y 9, nos permita

recuperar el contenido de uno de los registros anteriores.

void CActividad4AView::OnBuscarCliente()

{

// Obtener el nmero de registro que deseamos buscar:

UpdateData(TRUE);

//Comprobar que est dentro del rango:

if (m_NumRegistro < 0)

{

MessageBox(No se puede buscar un nmero de registro

negativo., Error, MB_OK);

return;

}

if (m_NumRegistro > 9)

{

MessageBox(Escoja un registro del 0 al 9);

return;

}//Llamar a la funcin de bsqueda:

BuscarCliente(m_NumRegistro);

}

void CActividad4AView::BuscarCliente(int nRegistro)

{

FILE * pArchivo;

tagCliente Cliente;

char szMensaje[1024];

int nPos;

pArchivo = fopen(CLIENTES.DAT, r+);

if (pArchivo)

{

//Hallar la posicin en el archivo:

nPos = nRegistro * sizeof(tagCliente);

//Posicionarse:

fseek(pArchivo, nPos, SEEK_SET);

//Leer el contenido:

fread(&Cliente, sizeof(tagCliente), 1, pArchivo);


35/37

53


sprintf(szMensaje, Registro: %d\nNombre: %s\nDireccion: %s\

nPoblacion: %s\n,

nRegistro, Cliente.Nombre, Cliente.Direccion, Cliente.

Poblacion);

MessageBox(szMensaje, Registro ledo:, MB_OK);

fclose(pArchivo);

}

}

1.5.5 actividad 5

En esta prctica partiremos de un ejemplo que se encuentra realizado y

documentado en el CD ROM que acompaa al libro.

El ejemplo contiene clases de indexacin mediante rbol binario realizadas

en C++.

El objetivo de esta prctica es ver cmo se integran estas clases en unaaplicacin sencilla para indexar un archivo de clientes mediante una aplicacin

en entorno Windows. El cdigo fuente est realizado en Visual C++, pero las

clases de indexacin pueden ser compiladas bajo Linux mediante el compilador

C de GNU.

Los ejemplos se encuentran en la carpeta \a\co 1\a5 y dentro de esta carpeta encontraremos tambin un texto quenos guiar a travs de la aplicacin de ejemplo y nos ayudar a hacer un

seguimiento de su cdigo fuente.


36/37

54


Los antecesores de las bases de datos son los archivos de almacenamiento

de datos.

Histricamente se ha pasado por tres fases, que corresponden a los tres

tipos de archivo principales: archivos secuenciales, archivos de acceso

aleatorio y archivos indexados.

Especialmente estos ltimos proporcionan una tecnologa que est

presente en el diseo de los servidores de bases de datos relacionales(SGBD).

Podemos escribir programas en diferentes lenguajes que trabajen con

estos tipos de archivos, los cuales siguen siendo una buena opcin para

tareas sencillas y robustas.

2resumen del captulO

n1. Para comprobar el funcionamientodel proceso de bsqueda en un rbol

binario equilibrado (archivo indexa-do), estableceremos un punto de rup-

tura o break point en la lnea 521 del

archivo BST.cpp. Recordemos que el

punto de ruptura se establece pul-

sando la tecla F9 habiendo situado el

cursor sobre esta lnea. Se trata de la

instruccin while de la funcin Find

del rbol binario. Con este punto de

ruptura, si ejecutamos la aplicacin

en modo depuracin (tecla F5) y bus-camos un cliente, iremos pasando

sucesivamente por esta funcin vien-

do si avanzamos hacia el puntero L

o hacia el puntero R hasta llegar ala clave buscada o hasta llegar a un

nodo terminal (hoja) que no coincida

porque la clave no existe.

n2. Escribir un programa para guar-dar las apuestas de un partido de ft-

bol (por ejemplo, Barcelona-Madrid)

dentro de un archivo secuencial. Los

campos sern Nombre del apostan-

te, Goles Barcelona, Goles Madrid yValor apostado.

2 eJerciciOs prOpuestOs


37/37


n3. Escribir un programa de bsque-da de apuesta que encuentre los ga-

nadores de la apuesta a partir delresultado de goles del Barcelona y de

goles del Madrid.

n4. Intentar estos mismos programasmediante archivo de aceso aleatorio

o archivo indexado, a gusto del lec-tor.

1Qu tipo de archivos permiten lalectura directa de los datos a partirde su nmero de registro?

)Archivo secuencial.)Archivo de acceso aleatorio.)Archivo indexado.

)Todos los anteriores.

2Qu tipo de archivos se relacionanhistricamente con los tambores decinta magntica?

)Archivo secuencial.)Archivo de acceso aleatorio.)Archivo indexado.)Todos los anteriores.

3Qu concurrencia permiten losarchivos secuenciales?) Monousuario.) Multiusuario.

4Qu concurrencia permiten losarchivos de acceso aleatorio?1. Monousuario.

2. Multiusuario.

5

Qu tpica estructura de datos

se emplea en la construccin deindexados?

) La tabla.) La coliflor equilibrada.) El sarmiento (vine-to-tree / tree-

to-vine).

)El rbol binario equilibrado.

2test de cOnOcimientOs

Documents

TEMA1-Gestion de Bases de Datos - RAMA