resumenCBD1

resumenParcial1.md

Conceptos basicos

• Base de datos: informacion dispuesta de manera adecuada para su tratamiento por una computadora. Coleccion de archivos diseñados para server a multiples aplicaciones. Conjunto de datos interrelacionados con un proposito especifico vinculado a la resolucion de un problema del mundo real.
  • Propiedades:
    • Se diseña, construye y completa con datos para un proposito especifico.
    • Es una coleccion coherente de datos, estan estructurados y deben tener cierta logica.
    • Destinada a un grupo de usuarios concreto.
• SGBD(Sistema de gestion de Bases de Datos): Sistema de software que permite a los usuarios crear y manteler la BD.
  • Facilita procesos de definicion, construccion y manipulacion de la BD.
  • Objetivos:
    • Control de redundancia
    • Acceso a los datos en todo momento, y acceso concurrente
    • Restriccion a accesos no autorizados
    • Almacenamiento persistente
    • Integridad
    • Backups
• Origen:
  • Aplicaciones antiguas:
    • Usaban archivos propios para consultar y/o actualizar.

Archivos

Definicion

• Archivo:
  • Es una coleccion de registros semejantes, guardados en dispositivos de almacenamiento secundario de la computadora.
  • Estructa de datos que recopila una coleccion de elementos del mismo tipo.
  • Coleccion de registros que abarcan entidades con un aspecto comun.

Organizacion

• Secuencia de bytes: no se puede determinar facilmente el comienzo y fin del archivo
• Campos
• Registros: conjunto de campos que definen un elemento del archivo

Acceso

• Secuencial: acceso a registros uno tras otro. en orden fisico
• Secuencial indexado: acceso de acuerdo al orden establecido por otra estructura
• Directo: se accede a un registro sin necesidad de haber accedido a otro previamente

Almacenamiento

• Primario: RAM. Acceso rapido. capacidad limitada, volatil y alto costo
• Secundario: Cintas, Discos. Alta capacidad, no volatil menor costo. Acceso LENTO
  • Cintas: acceso secuencial
  • Discos: acceso directo.
    • Un registro en un solo sector
      • Ventaja: cualquier registro se recupera con solo recuperar un sector
      • Desventaja: puede quedar espacio sin uso
    • El principio en un sector y el final en otro
      • Ventaja: se evita que quede espacio sin uso
      • Desventaja: acceso a dos sectores en vez de uno

Niveles de vision

• Fisica: archivo que existe en el almacenamiento secundario. Conocido por el S.O, directorio
• Logica: Visto desde dentro del programa. Independencia fisica, se realizan operaciones sin conocer su ubicacion fisica real

Camino de los datos

Cuando se escribe un dato en un archivo desde un programa, intervienen varios componentes del SO:

• Administrador de archivos: Conjunto de programas del S.O que tratan de aspectos relacionados con archivos y dispositivos de E/S.
• Buffer de E/S: Agilizan la E/S de datos. Mem intermedia entre un archivo y un programa. Ocupan lugar en RAM.
• Procesador de E/S: Accede a los buffers de E/S y envia requerimientos de R/W al controlador de disco.
• Controlador de Disco: Encargado de controlar la operacion de disco.

Algoritmica clasica

• Modificacion: Consiste en cambiar datos. El archivo debe ser recorrido desde su primer elemento hasta el ultimo, siguiendo un procesamiento secuencial.
• Agregado: Consiste en agregar datos a la posicion que se necesite. Primero moverse a esa posicion y luego agregar.
• Actualizacion maestro-detalle: Maestro contiene la info a ser actualizada, detalle contiene la info que se utilizara para actualizar el maestro.
• Corte de control: Permite analizar la info almacenada en archivos y generar reportes. El archivo debe estar ordenado por 1 o mas criterios. Se obtiene un reporta que respeta un formato determinado.
• Merge: Involucra un conjunto de archivos con contenido similar, el cual se debe resumir a uno solo. Todos deben tener la misma estructura y estar ordenados por el mismo criterio.

Acceso a los datos

• Clave o llave: facilitar el acceso a un registro en particular dentro del archivo. La clave identifica al registro.
  • Forma canonica: forma estandar para una clave. Se deriva a partir de reglas bien definidas. La clave tiene una representacion unica.
• Performance:
  • Busqueda secuencial es O(n)
  • Acceso directo es O(1), es necesario conocer el lugar del comienzo. Preferible solo cuando se necesitan pocos registros especificos.

Mantenimiento

• Tipos de archivos(segun sus cambios):
  • Estaticos: pocos cambios.
    • No necesita estructuras adicionales para agilizar los cambios.
  • Volatiles: operaciones frecuentes. agregar/borrar/actualizar.
    • Su organizacion debe facilitar cambios rapidos. Necesita estructuras adicionales para mejorar los tiempos de acceso.
• Eliminacion de un registro:
  • Baja fisica: El registro eliminado deja de estar fisicamente en el archivo. Mediante compactacion: copiar todo a excepcion de los registros eliminados.
  • Baja logica: El registro eliminado sigue estando en el archivo, pero marcado como eliminado. Permite anular el proceso de eliminacion facilmente. Los programas que usan archivos deben cambiar sus metodologias de trabajo: ignorar resgistros eliminados.
• Recuperacion dinamica de espacio: reutilizar el espacio al momento de insertar un nuevo registro en el archivo. Usando marcas de borrado logico se puede identificar un espacio vacio.
  • Longitud fija:
    • Busqueda secuencial: Se busca el 1er regitro eliminado. Si no existe se llega al final y se agrega alli. MUY LENTO para archivos volatiles*.
    • Lista encadenada o pila: se mantienen enlazados los espacios libres. La lista no necesita estar ordenada: PILA
  • Longitud variable:
    • Se utiliza la marca de borrado para identificar registros eliminados.
    • El nuevo registro no se puede colocar en cualquier lugar: ya que debe caber.
    • Se necesita realizar una busqueda en la lista de lugares disponibles(no se organiza como pila)
  • Fragmentacion interna: Ocurre cuando se desperdicia espacio dentro de un registro: el lugar esta asignado al mismo pero no lo ocupa totalmente. Se da tanto en fija como variable.
  • Fragmentacion externa: Ocurre cuando el espacio libre es demasiado pequeño como para ser ocupado por un nuevo registro.
  • Estrategias de colocacion: solo tienen sentido con registros de longitud variable
    • Primer ajuste(+ rapido, genera frag interna): selecciona la primera entrada de la lista de disponibles y se le asigna de forma completa al mismo. MINIMIZA LA BUSQUEDA.
    • Mejor ajuste(genera frag interna): elige la entrada que mas se aproxime al tamaño del registro y se le asigna de forma completa al mismo. EXIGE BUSQUEDA COMPLETA.
    • Peor ajuste(genera frag externa): elige la entrada mas grande para el registro pero solo le asigna el espacio necesario, queda libre el resto. El sobrante puede ser usado por otro registro. EXIGE BUSQUEDA COMPLETA.

Busqueda de informacion

• Busqueda de registro por NRR(Numero relativo de registro):
  • Rapido, O(1)
• Busqueda de registro secuencialmente:
  • Archivo desordenado: O(N)
  • Archivo ordenado: O(N)
• Busqueda binaria: El archivo tiene que tener registros con longitud fija, y estar ordenado por clave
  • Se compara la clave buscada con la encontrada en el registro que se encuentra en la mitad del archivo. Si no se encuentra se continua procesando la mitad del archivo que corresponda.
  • Es O(log2(N)).
  • Ventajas: en cada paso acota el espacio para encontrar la info. Se mejora la performance de la busqueda secuencial.
  • Desventajas: Mantener el archivo ordenado.

Clasificacion

• Clasificacion del archivo completo en RAM: Consiste en llevar el archivo a memoria RAM y luego ordenarlo.
  • El archivo a ordenar debe caber en la memoria RAM
• Clasificacion de las claves en RAM: No se lleva el archivo completo a memoria RAM, sino que solo se llevan las claves.
• Clasificacion por partes: Cuando no cabe el archivo ni sus claves, se debe partir, ordenar y juntar.
  • Clasifica archivos de cualquier tamaño
• Clasificacion por partes: Sort interno
  • El tamaño de cada particion se determina segun el tamaño de la RAM
  • Es el mas simple
• Clasificacion por partes: Sel. por reemplazo: Aumenta el tamaño de las particiones al doble.
  • Particionas mas grandes que sort interrelacionados
  • Genera muchos registros dormidos
• Clasificacion por partes: Seleccion natural: reserva y utiliza un buffer en memoria secundaria.
  • Genera particiones de mayor tamaño que el resto
  • Mayor costo de acceso
• Clasificacion por partes: intercalacion en mas de un paso.
  • Se agregan pasos intermedios que generar particiones intermedias temporales.
  • Cada registro se debe leer mas de una vez.