Not Only SQL

About “Not Only SQL”…

We could say that it’s the next Generation Databases mostly addressing some of the points: being non-relational, distributed, open-source and horizontally scalable.

We can find a lot of new databases of this type like:

  • Couchbase Server:

    API: Memcached API+protocol (binary and ASCII) , most languages, Protocol:Memcached REST interface for cluster conf + management, Written in: C/C++ + Erlang (clustering), Replication: Peer to Peer, fully consistent, Misc: Transparent topology changes during operation, provides memcached-compatible caching buckets, commercially supported version available.

  • RaptorDB:

    JSON based, Document store database with compiled .net map functions and automatic hybrid bitmap indexing and LINQ query filters

  • EJDB:

    Embedded JSON database engine based on tokyocabinet. API: C/C++, C# (.Net, Mono), Lua, Ruby, Python, Node.js binding, Protocol: Native, Written in: C, Query language: mongodb-like dynamic queries, Concurrency: RW locking, transactional , Misc: Indexing, collection level rw locking, collection level transactions, collection joins., License: LGPL

Modelo relacional de empresa de autobuses en Excel

Ejemplo de modelo relacional en Excel

En este ejercicio vamos a crear un modelo de esquema de registros utilizando excel. Para tres ficheros diferentes en los que deberá confeccionar el conjunto de campos y campos clave para una empresa de autobuses en los siguientes supuestos:

  1. Crea un fichero con la información de los autobuses que son de su propiedad.
  2. Fichero con la información de los conductores de la empresa.
  3. Fichero con la información de los clientes que utilizan el servicio de autobuses.

Para ello hemos elegido los siguientes Tablas y registros:

  • Tabla 1 AUTOBUSES: En la cual designamos el campo clave como número de autobús. Los registros capacidad, matricula y disponible como secundarios.

 

  • Tabla 2 CONDUCTORES: En este caso pondremos el número de conductor como campo clave .Los campos nombre, apellidos, DNI y antiguedad como secundarios.

 

  • Tabla 3 CLIENTES: Para esta tabla utilizaremos el número de cliente como campo clave. Los campos nombre, DNI y edad como secundarios.

Características de los diferentes tipos de sistemas de ficheros de acceso indexado

Se consideran dos variantes en el acceso indexado:

  • acceso secuencial indexado
  • acceso indexado

Acceso secuencial indexado (ISAM)

  • El fichero de indice como el fichero de datos están ordenados por un valor clave.
  • La relación entre el fichero y la posición donde se encuentra en la zona de registros, se establece una relación por rangos.
  • El fichero de índice está compuesto por una entrada por cada registro de datos y debe encontrarse ordenado por el campo clave para poder realizar búsquedas de forma eficiente.
  • Al estar los registros ordenados por un campo clave, es posible aplicar la búsqueda dicotómica para acelerar las búsquedas.
  • Recuperación de registros: si es denso, la lectura es inmediata, si es en índices escasos, se deben recorrer los niveles y efectuar alguna secuencial.
  • Recuperación del siguiente: dado que se encuentran ordenados, es sencillo.
  • Inserción: aquí se complica, pues lo difícil es mantener el fichero de índices.
  • Ya podemos ver que este tipo de estructura es buena para lecturas pero no
    para otro tipo de operaciones sobre registros.
  • Borrado: igual que con la inserción de registros

Acceso indexado

  • El acceso indexado “puro” es una modificación del acceso indexado secuencial,  ya que en esta implementación se suprime el uso de la zona de desbordamiento.
  • Zona de registros. Se siguen manteniendo los registros del fichero pero se almacenarán por orden de llegada. no se almacenarán ordenados por el campo clave. Los registros que se almacenan pueden ser de longitud fija o variable.
  • Zona de índices. Existirá una referencia de la localización de cada registro. En este caso siempre habrá una relación 1 a 1 de referencia hacia un registro. Los ficheros de índices, si existen varios niveles, estarán ordenados por el campo clave. Además, podrán existir tantos índices diferentes como campos existan en el registro.
  • Recuperación de un registro: dado que se usan índices densos y no
    hay zona de desbordamiento, es más eficiente. Es la más eficiente de
    todas.
  • Recuperación del registro siguiente: no es eficiente porque hay que
    localizarlo en el índice, que se encuentra ordenado, pero en la zona
    de registros pueden estar distantes.
  • Inserción de registros: se coloca al final del fichero y se actualizan
    todos los ficheros de los índices. Mientras que la agregación es
    eficiente, la gestión de los ficheros puede ser bastante más compleja
  • Modificación de registros: localizar el registro y proceder a realizar la
    modificación sobre el propio fichero y actualizar los índices afectados.
    Borrado de registros: la eliminación de los registros no se aplican sobre la zona de registros, sino que se marca el espacio como disponible en el registro y se modifican todos los índices afectados en los ficheros de índices.

Acceso secuencial y directo

Método Secuencial y Método Directo

¿En qué supuestos es la mejor opción el método secuencial como organización de datos?¿Y el método directo?

El acceso secuencial será utilizado en aplicaciones orientadas al manejo por lotes o en los que no es prioritario el acceso a un registro determinado. Esto es así porque se accede a los datos del fichero en un predeterminado orden.
En cambio, el acceso directo lo utilizaremos cuando sea necesario conocer la posición que ocupan cada uno de los registros en el fichero ya que nos permite acceder a cualquier registro de un fichero sin necesidad de recorrer los anteriores.

Ventajas e inconvenientes de ambos métodos

Método Secuencial

Ventajas
       • Evita fragmentación externa al no existir espacios entre       registros, pero precisa una carga
       extra de optimización.
       • Acceso rápido a registros contiguos. Por ejemplo, extraer los contactos que comienzan
        por una determinada letra en una agenda personal.
Desventajas:
       • Accesos ineficientes: Debido a que hay que recorrer muchos registros innecesarios.
       Obviamente, si el fichero a buscar se encuentra al comienzo, será rápido, mientras que si
       se encuentra al final, será muy costoso. Para definir el coste se suele indicar el coste
       medio.
       • Alto coste en las operaciones de mantenimiento de la estructura de datos. Por ejemplo,
       si se utiliza un almacenamiento contiguo en el que todos los registros ocupan un espacio
       variable pueden quedar huecos entre registros que deben ser reagrupados
       (compactación o desfragmentación).

Método Directo

 Ventajas:
• Evita la fragmentación externa
• Eficiencia en el acceso a datos
• Bajo coste en las operaciones de mantenimiento de la estructura de datos en caso de
registros de tamaño fijo
Desventajas:
• Limitación del hardware. Sólo se puede usar este método en dispositivos de acceso
directo (HDD, SSD).
• Alto coste en las operaciones de mantenimiento de la organización de los datos en caso
de registros de tamaño variable. Para reagrupar los huecos existentes y para realizar las
operaciones de eliminación o actualización.

¿Dónde encontramos estos tipos de ficheros?

Si hablamos de los ficheros de acceso secuencial, podríamos encontrarlos en: tocadiscos, lectura de cintas de respaldo, grabadores de discos ópticos de CD’s – DVD’s – Blu rays, casetera…

Si nos referimos a los ficheros de acceso directo, los encontraríamos en: disco duro, memoria USB, disquete, memoria RAM…

Puntos fuertes y débiles de los métodos de acceso

Acceso secuencial

Ventajas
  • Evita fragmentación externa al no existir espacios entre registros, pero precisa una carga extra de optimización.
  • Acceso rápido a registros contiguos.Por ejemplo, extraer los contactos que comienzan por una determinada letra en una agenda personal.
Desventajas:
  • Accesos ineficientes . Debido a que hay que recorrer muchos registros innecesarios. Obviamente, si el fichero a buscar se encuentra al comienzo, será rápido, mientras que si se encuentra al final, será muy costoso. Para definir el coste se suele indicar el coste medio.
  • Alto coste en las operaciones de mantenimiento de la estructura de datos. Por ejemplo, si se utiliza un almacenamiento contiguo en el que todos los registros ocupan un espacio variable pueden quedar huecos entre registros que deben ser reagrupados (compactación o desfragmentación).

Acceso indexado

Ventajas
  • Todas las del acceso directo, puesto que todos los registros están asociados con una entrada en el fichero de índices.
  • Se pueden realizar búsquedas y órdenes por cualquier campo de los registros, puesto que se pueden construir índices para cada uno de estos.
  • La inserción de registros es muy eficiente, puesto que no se tienen que mantener en orden
  • los registros, sino que se insertan al final y es la gestión de los índices donde recae el esfuerzo.
Desventajas
  • Limitación de hardware, sólo se puede utilizar en soportes direccionales (no se puede implementar en soportes de almacenamiento que no permita esta característica).
  • Las operaciones por lote no son eficientes.
  • Es necesario más espacio en disco.
  • La gestión de índices es muy compleja en las operaciones de inserción/modificación/eliminación.

Direccionamiento calculado

Ventajas
  • Eficiencia en el acceso a datos
  • Bajo coste en operaciones de mantenimiento
Inconvenientes
  • Limitación por hardware
  • Alto coste en recorrer todos los elementos

Diferencia entre acceso directo y acceso por direccionamiento calculado

Acceso directo

El campo de operando en la instrucción contiene la dirección en memoria donde se encuentra el operando.

En este modo la dirección efectiva es igual a la parte de dirección de la instrucción. El operando reside en la memoria y su dirección es dada directamente por el campo de dirección de la instrucción. En una instrucción de tipo ramificación el campo de dirección especifica la dirección de la rama actual.

Si hace referencia a un registro de la máquina, el dato estará almacenado en este registro y hablaremos de direccionamiento directo a registro; si hace referencia a una posición de memoria, el dato estará almacenado en esta dirección de memoria (dirección efectiva) y hablaremos de direccionamiento directo a memoria. Estos modos de direccionamiento tienen una forma muy simple y no hay que hacer cálculos para obtener la dirección efectiva donde está el dato. El tamaño del operando, en el caso del direccionamiento directo a registro, dependerá del número de registros que tenga la máquina; en el direccionamiento directo a memoria, dependerá del tamaño de la memoria.

 

Acceso por direccionamiento calculado

Al igual que ocurre con los ficheros de acceso directo, los registros se almacenan en una posición específica del fichero que  es obtenida en este caso no simplemente por el valor de la clave  sino por el resultado de aplicar el algoritmo a dicha clave. A esta clave se la reconoce también con el nombre de  clave de direccionamiento calculado. El algoritmo determinará la posición de memoria en la que se localizará el registro, denominado como función de direccionamiento calculado. Esta aplicación de aplicar un algoritmo a la clave del registro se conoce como técnica de Hashing o direccionamiento calculado.

tabla hash

Índice exhaustivo e índice selectivo

Los ficheros de índice suelen ser de dos tipos:

Índice exhaustivo o denso

En este tipo de índices existe un registro índice por cada valor del campo clave que se encuentra en la zona de registros. Se conoce como organizaciones indexadas puras.
El índice denso es como un acceso directo, pero ocupan más espacio y requieren de más operaciones de mantenimiento.

Índice selectivo o escaso

No existe un registro índice por cada valor del campo clave que se encuentra en la zona de registros, sino que se crean solamente entradas en el fichero de índices para algunos registros. Los registros se agrupan en el área de datos (están ordenados) y se realiza la indexación por grupos. Posteriormente se realiza una búsqueda secuencial dentro de cada grupo.