jueves, 22 de noviembre de 2012

Confiabilidad.

Confiabilidad.

La confiabilidad es otro requerimiento indiscutible – y probablemente el más importante. Una base de datos no confiable es simplemente inutilizable. Para la mayoría de las aplicaciones empotradas, en especial las empleadas en sistemas de tiempo real, la confiabilidad es una propiedad no negociable que deben tener todos los componentes.

Un sistema de manejo de bases de datos confiable es aquel que puede continua procesando las solicitudes de usuario aún cuando el sistema sobre el que opera no es confiable. En otras palabras, aun cuando los componentes de un sistema distribuido fallen, un DDMBS confiable debe seguir ejecutando las solicitudes de usuario sin violar la consistencia de la base de datos.

4.3.1 Conceptos básicos de confiabilidad.

La confiabilidad engloba varias actividades y una de ellas es el planteamiento de modelos de confiabilidad, esto es fundamentalmente la probabilidad de supervivencia del sistema.

Se expresa como una función de las confiabilidades de los componentes o subsistemas, que generalmente, estos modelos se encuentran dependiendo del tiempo.

4.3.2 Protocolos REDO/UNDO.

El registro de la base de datos contiene información que es utilizada por el proceso de recuperación para restablecer la base de datos a un estado consistente. Esta información puede incluir entre otras cosas:

el identificador de la transacción,
el tipo de operación realizada,
los datos accesados por la transacción para realizar la acción,
el valor anterior del dato (imagen anterior), y
el valor nuevo del dato (imagen nueva).

Considere el escenario mostrado en la Figura de abajo. El DBMS inicia la ejecución en el tiempo 0 y en el tiempo t se presenta una falla del sistema. Durante el periodo [0, t] ocurren dos transacciones, T₁ y T₂. T₁ ha sido concluida (ha realizado su commit) pero T₂ no pudo ser concluida.

La propiedad de durabilidad requiere que los efectos de T₁ sean reflejados en la base de datos estable. De forma similar, la propiedad de atomicidad requiere que la base de datos estable no contenga alguno de los efectos de T₂.

Ejemplo de una falla del sistema.

A pesar que T₁ haya sido terminada, puede suceder que el buffer correspondiente a la página de la base de datos modificada no haya sido escrito a la base de datos estable. Así, para este caso la recuperación tiene que volver a realizar los cambios hechos por T₁. A esta operación se le conoce como REDO y se presenta en la Figura de abajo.

La operación de REDO utiliza la información del registro de la base de datos y realiza de nuevo las acciones que pudieron haber sido realizadas antes de la falla. La operación REDO genera una nueva imagen.

Operación REDO.

Por otra parte, es posible que el administrador del buffer haya realizado la escritura en la base de datos estable de algunas de las páginas de la base de datos volátil correspondientes a la transacción T₂.

Así, la información de recuperación debe incluir datos suficientes para permitir deshacer ciertas actualizaciones en el nuevo estado de la base de datos y regrasarla al estado anterior. A esta operación se le conoce como UNDO y se muestra en la Figura de abajo. La operación UNDO restablece un dato a su imagen anterior utilizando la información del registro de la base de datos.

Operación UNDO.

De forma similar a la base de datos volátil, el registro de la base de datos se mantiene en memoria principal (llamada los buffers de registro) y se escribe al almacenamiento estable (llamadoregistro estable). Las páginas de registro se pueden escribir en el registro estable de dos formas: síncrona o asíncrona. En forma síncrona, también llamada un registro forzado, la adición de cada dato en el registro requiere que la página del registro correspondiente se mueva al almacenamiento estable. De manera asíncrona, las páginas del registro se mueven en forma periódica o cuando los buffers se llenan.

4.3.3 Puntos de verificación (checkpoints).

Cuando ocurre una falla en el sistema es necesario consultar la bitácora para determinar cuáles son las transacciones que necesitan volver a hacerse y cuando no necesitan hacerse. Estos puntos de verificación nos ayudan para reducir el gasto de tiempo consultando la bitácora. El punto de verificación es un registro que se genera en la bitácora para concluir en todo lo que se encuentra antes de ese punto está correcto y verificado.

4.3.4 Protocolo 2PC de confiabilidad distribuida.

El protocolo 2PC básico un agente (un agente-DTM en el modelo) con un rol especial. Este es llamado el coordinador; todos los demás agentes que deben hacer commit a la vez son llamados participantes.

El coordinador es responsable de tomar la decisión de llevar a cabo un commit o abort finalmente. Cada participante corresponde a una subtransacción la cual ha realizado alguna acción de escritura en su base de datos local.

Se puede asumir que cada participante está en un sitio diferente. Aun si un participante y el coordinador se encuentran en el mismo sitio, se sigue el protocolo como si estuvieran en distintos sitios.

La idea básica del 2PC es determinar una decisión única para todos los participantes con respecto a hacer commit o abort en todas las subtransacciones locales.

El protocolo consiste en dos fases:

La primera fase tiene como objetivo alcanzar una decisión común,

La meta de la segunda fase es implementar esta decisión.

El protocolo procede como sigue:

Fase uno:

• El coordinador escribe “prepare” en la bitácora y envía un mensaje donde pregunta a todos los participantes si preparan el commit (PREPARE).

• Cada participante escribe “ready” (y registra las subtransacciones) en su propia bitácora si está listo o “abort” de lo contrario.

• Cada participante responde con un mensaje READY o ABORT al coordinador.

• El coordinador decide el commit o abort en la transacción como un resultado de las respuestas que ha recibido de los participantes. Si todos respondieron READY, decide hacer un commit. Si alguno ha respondido ABORT o no ha respondido en un intervalo de tiempo determinado se aborta la transacción.

Fase dos:

• El coordinador registra la decisión tomada en almacenamiento estable; es decir, escribe “global_commit” o “global_abort” en la bitácora.

• El coordinador envía mensaje de COMMIT o ABORT según sea el caso para su ejecución.

• Todos los participantes escriben un commit o abort en la bitácora basados en el mensaje recibido del coordinador (desde este momento el procedimiento de recuperación es capaz de asegurar que el efecto de la subtransacción no será perdido).

Finalmente:

Todos los participantes envían un mensaje de acuse de recibo (ACK) al coordinador, y ejecutan las acciones requeridas para terminar (commit) o abortar (abort) la subtransacción.
Cuando el coordinador ha recibido un mensaje ACK de todos los participantes, escribe un nuevo tipo de registro en la bitácora, llamado un registro “completo”.

Disciplinas de Interbloque

Definición y tratamiento de interbloqueo

Conjunto de procesos tal que cada uno está esperando un recurso

que sólo puede liberar otro proceso del conjunto.

Tratamiento del interbloqueo.

•

Detección y recuperación: Se detecta y se recupera

Coste de algoritmo + pérdida del trabajo realizado.

•

Prevención: Asegura que no ocurre fijando reglas

Infrautilización de rec. se deben pedir antes de necesitarlos.

•

Predicción: Asegura que no ocurre basándose en

conocimiento de necesidades futuras de los procesos

*Dificultad de conocer futuro

*Coste de algoritmo + Infrautilización de recursos

•

Ignorar el problema:Utilizada por la mayoría de los SS.OO.
Detección del interbloqueo

Algoritmo que comprueba si se cumplen condiciones de interbl.

Condiciones necesarias pero no suficientes (Coffman):

•

Exclusión mutua.

•

Retención y espera.

•

Sin expropiación.

•

Espera circular.

Si restricciones (1 unid/rec), cond. son necesarias y suficientes:

•

Ejemplo 2: Ciclo en grafo → espera circular → interbloqueo

•

Ejemplo 1: Ciclo en grafo → espera circular → No interbloq.

•

Ejemplo 3: Ciclo en grafo → espera circular → interbloq.

○ Se necesita condición necesaria y suficiente para sist. general
Condición necesaria y suficiente

Proceso no bloqueado debería devolver recursos en el futuro:

•

Recursos liberados desbloquearían otros procesos...

Reducción (Red) del sistema por proceso P

•

Si se pueden satisfacer necesidades de P con r. disponibles

•

Nuevo estado hipotético donde P ha liberado todos sus rec.

Condición necesaria y suficiente:

•

∃ secuencia de Red desde estado actual ⊂ todos los procesos• Si no: procesos ⊄ están en interbloqueo

lunes, 12 de noviembre de 2012

CONTROL DE CONCURRENCIA

ALGORITMO DE ESTAMPAS DE TIEMPO DISTRIBUIDO

*DESCRIPCIÓN GENERAL

En un sistema distribuido, cada transaccion debe tener una estampilla de tiempo unica para usar en la

decision del orden de serializabilidad. Para la generacion de estampillas unicas, en el modelo

distribuido: cada transaccion tiene una estampilla de tiempo que surge de concatenar la estampilla de

tiempo local con el identificador de sitio.

El problema del modelo distribuido es que un sitio podria generar estampillas de tiempo a mayor

velocidad que otros sitios. En ese caso, las estampillas de tiempo generadas por el sitio mas rapido seran

mayores que las generadas por otros sitios. Esto se evita si cada sitio utiliza un reloj logico,

implementado mediante un contador que se incrementa cada vez que se genera una nueva estampilla de

tiempo local. Para sincronizar los relojes logicos, se requiere que cada sitio Si avance su reloj logico

cuando arriba una nueva transaccion a ese sitio.

A diferencia de los algoritmos basados en candados, los algoritmos basados en estampas de tiempo no

pretenden mantener la seriabilidad por exclusion mutua. En lugar de eso, ellos seleccionan un orden de

serializacion a priori y ejecutan las transacciones de acuerdo a ellas. Para establecer este ordenamiento, el

administrador de transacciones le asigna a cada transaccion

Ti una estampa de tiempo unica ts( Ti )

cuando esta inicia. Una

estampa de tiempo es un identificador simple que sirve para identificar cadatransaccion de manera unica.

*CARACTERÍSTICAS

Existen varias formas en que las estampas de tiempo se pueden asignar. Un metodo es usar un contador

global monotonicamente creciente. Sin embargo, el mantenimiento de contadores globales es un

problema en sistemas distribuidos. Por lo tanto, es preferible que cada nodo asigne de manera autonoma

las estampas de tiempos basandose en un contador local. Para obtener la unicidad, cada nodo le agrega

al contador su propio identificador. Asi, la estampa de tiempo es un par de la forma

Note que el identificador de nodo se agrega en la posicion menos significativa, de manera que, este sirve

solo en el caso en que dos nodos diferentes le asignen el mismo contador local a dos transacciones

diferentes.

El administrador de transacciones asigna tambien una estampa de tiempo a todas las operaciones

solicitadas por una transaccion. Mas aun, a cada elemento de datos x se le asigna una estampa de tiempo

de escritura, wts(x), y una estampa de tiempo de lectura, rts(x); sus valores indican la estampa de tiempo

mas grande para cualquier lectura y escritura de x, respectivamente.

Regla TO

: dadas dos operaciones en conflicto, Oij y Okl, perteneciendo a las transacciones Ti y Tk, respectivamente,

Oij es ejecutada antes de Okl, si y solamente si, ts ( Ti ) < ts (Tk ). En este caso Ti se dice ser un transacción más vieja yTk se dice ser una transacciónmás joven .

ALGORITMO DE CONTROL DE CONCURRENCIA BASADOS EN EL BLOQUEO.

*Bloqueos
Un bloqueo en general es cuando una acción que debe ser realizada está esperando a un evento. Para manejar los bloqueos hay distintos acercamientos: prevención, detección, y recuperación. También es necesario considerar factores como que hay sistemas en los que permitir un bloqueo es inaceptable y catastrófico, y sistemas en los que la detección del bloqueo es demasiado costosa.

En el caso específico de las bases de datos distribuidas usar bloqueo de recursos, peticiones para probar, establecer o liberar bloqueos requiere mensajes entre los manejadores de transacciones y el calendarizador. Para esto existen dos formas básicas:

Autónoma: cada nodo es responsable por sus propios bloqueos de recursos.
- Una transacción sobre un elemento con n replicas requiere 5n mensajes
- Petición del recurso
- Aprobación de la petición
- Mensaje de la transacción
- Reconocimientos de transacción exitosa
- Peticiones de liberación de recursos
Copia Primaria: un nodo primario es responsable para todos los bloqueos de recursos
- Una transacción sobre un elemento con n copias requiere 2n+3 mensajes
- Una petición del recurso
- Una aprobación de la petición
- n mensajes de la transacción
- n reconocimientos de transacción exitosa
- Una petición de liberación de recurso

Podemos definir que dos operaciones entran en conflicto que debe ser resuelto si ambas acceden a la misma data, y una de ellas es de escritura y si fueron realizadas por transacciones distintas.

Pruebas de validación optimistas.

miércoles, 7 de noviembre de 2012

MANEJO DE TRANSACCIONES

Se llama Transacción a una colección de operaciones que forman una unidad lógica de trabajo en una BD realizada por una o más sentencias SQL estrechamente relacionadas.

Una transacción es una unidad de la ejecución de un programa que lee y escribe datos a y desde la Base de Datos. Puede consistir en varias operaciones de acceso a la base de datos. Una Transacción está delimitada por instrucciones de inicio transacción y fin transacción (la transacción consiste en todas las operaciones que se ejecutan entre inicio transacción y fin transacción).

El concepto de transacción se desarrolló para atender los casos en los que el estado resultante de la base de datos depende del éxito completo en una serie de operaciones. Este concepto vio la luz debido a que varias operaciones sucesivas pueden modificar el resultado de operaciones anteriores. En esos casos, si alguna operación produce un error, el estado resultante puede ser indeterminado.

Para solucionar este problema, las transacciones agrupan una serie de operaciones de manera que es posible garantizar la integridad del resultado final. O todas las operaciones se ejecutan con éxito y se confirman (se escriben en la base de datos), o toda la transacción se considera no realizada. La acción de cancelar una transacción se denomina deshacer la transacción. Deshacer una transacción permite anular los cambios y recuperar el estado de la base de datos previo a la transacción.

Por ejemplo, en una transacción bancaria automatizada, si un banco transfiere dinero desde la cuenta A a la cuenta B, la retirada de fondos de A y el depósito en B deben producirse con éxito para procesar los fondos correctamente, de lo contrario la transacción entera debe cancelarse.

Esquematizando el proceso de transacciones temos: O se ejecutan todas las operaciones que componen la transacción, o no se realiza ninguna.

En SQL
Éxito	Fracaso
Begin transacction Instrucción 1 Instrucción 2 ... Commit workEnd transacction	Begin transacction Instrucción 1 Instrucción 2 ... Rollback workEnd transacction

Propiedades de la Transacción
Una unidad lógica de trabajo debe exhibir cuatro propiedades, conocidas como propiedades ACID (atomicidad, coherencia, aislamiento y durabilidad), para ser calificacada como transacción.

Atomicity : Una Transacción (Tx) se ejecuta completamente ó de otra manera se eliminan los cambios parciales realizados.
Begin Transaction - Programa - End Transaction
Responsable: El método de recuperación, de no completar todas las operaciones, devuelve la BD a su estado anterior a empezar esa Tx (rollback).
Coherencia: Asegura que los datos queobservamos no cambian (por otros usuarios) hasta que acabemos la Transacción.
Después de terminar una Transacción la Base de datos no viola ninguna de sus reglas: valores obligatorios, claves únicas,etc.
Responsable: los programadores mediante la definición adecuada de la integridad referencial: check, triggers, primary key, foreign key,…
Aislamiento: Los efectos de una Tx no son visibles a otros usuarios mientras no se confirmen.
Una Transacción en ejecución no puede revelar sus resultados a otras transacciones concurrentes antes de finalizar.
Más aun, si varias transacciones, se ejecutan concurrentemente, los resultados deben ser los mismos que si ellas se hubieran ejecutado secuencialmente. Esto se conoce como seriabilidad debido a que su resultado es la capacidad de volver a cargar los datos iniciales y reproducir una serie de transacciones para finalizar con los datos en el mismo estado en que estaban después de realizar transacciones originales.d
Responsable: el método de concurrencia: mecanismos, reglas, protocolos
Durabilidad: Si el sistema falla no debe permitir que se pierdan las operaciones realizadas por Tx ya confirmadas.
Responsable: el método o gestor de recuperación.

Estados y operaciones de una transacción

Control de transacciones en Oracle

Inicio de transacción

Cuando no hay ya una transacción en progreso, y se ejecuta una sentencia LDD o LMD (interactivamente o dentro de una aplicación)

Cada sentencia LDD es tratada como una transacción N

No existe sentencia de tipo BEGIN TRANSACTION

Fin de transacción

COMMIT: Finaliza la transacción actual y hace permanentes (confirma) los cambios realizados
ROLLBACK: Finaliza la transacción actual y deshace los cambios realizados

Sentencia COMMIT

Una sentencia COMMIT marca el final de una transacción correcta, implícita o definida por el usuario. COMMIT hace que todas las modificaciones efectuadas sobre los datos desde el inicio de la transacción sean parte permanente de la base de datos, y además, libera los recursos mantenidos por la conexión. Su sintaxis es la siguiente:

COMMIT COMMENT 'mensaje' | FORCE 'texto']

COMMENT sirve para comentar la transacción en un máximo 255 caracteres. FORCE fuera de modo manual una transacción dudosa y es de uso exclusivo en sistemas distribuidos de base de datos.

Sentencia SAVEPOINT

Esta sentencia permite crear un punto de restauración dentro de una transacción, es decir, un punto al que podremos retroceder deshaciendo todo lo hecho deshaciendo todo lo hecho desde él en adelante. Su sintaxis es la siguiente

SAVEPOINT nombrePuntoRestauración;

Sentencia ROLLBACK

Señala el final sin éxito de una transacción, elimina todas las modificaciones de datos realizadas desde el inicio de la transacción y también libera los recursos que retiene la transacción. Su sintaxis es la siguiente:

ROLLBACK [WORK] [TO SAVEPOINT nombrePuntoRestauración | FORCE 'texto'];

PREGUNTAS

Que es algebra relacional?

El álgebra relacional es un conjunto de operaciones que describen paso a paso como computar una respuesta sobre las relaciones, tal y como éstas son definidas en el modelo relacional.

Como se aplica el algebra relacional a la optimizacion de consultas en Mysql?

MySQL registra las consultas de tipo SELECT y su resultado. Como lo normal es que se acceda a la base de datos a través de una aplicación, las consultas repetidas son muy frecuentes (listas de poblaciones, de códigos, de nombres…).•Si MySQL recibe una consulta que tiene en la caché, simplemente entrega al cliente el mismo conjunto de resultados que produjo en su ejecución anterior. Naturalmente, las consultas de modificación de datos (INSERT, DELETE, UPDATE…) invalidan las consultas afectadas de la caché y provocan la eliminación de estas de la caché.

RESUMEN

El procesamiento de consultas tiene varias etapas a seguir para resolver una consulta SQL, las características del modelo relacional permiten que cada motor de base de datos elija su propia representación que, comúnmente, resulta ser el álgebra relacional. La optimización de consultas es, entonces, una de estas etapas.

Existen distintos métodos para optimizar consultas relacionales, sin embargo el enfoque de optimización basada en costos combinado con heurísticas que permitan reducir el espacio de búsqueda de la solución es el método mayormente utilizado por los motores de base de datos relaciones de la actualidad, en todo caso, independiente del método elegido para optimizar la consulta, la salida de este proceso debe ser un plan de ejecución, el cual comúnmente es representado en su forma de árbol relacional.

Optimización de consultas

El objetivo del procesamiento de consultas en un ambiente distribuido es transformar una consulta sobre una base de datos distribuida en una especificación de alto nivel a una estrategia de ejecución eficiente expresada en un lenguaje de bajo nivel sobre bases de datos locales.

Por ejemplo:

En las redes de área amplia (WAN), normalmente el costo de comunicación domina dado que hay una velocidad de comunicación relativamente baja, los canales están saturados y el trabajo adición al requerido por los protocolos de comunicación es considerable.

Así, los algoritmos diseñados para trabajar en una WAN, por lo general, ignoran los costos de CPU y de I/O. En redes de área local (LAN) el costo de comunicación no es tan dominante, así que se consideran los tres factores con pesos variables.

Optimización Global de Consultas

Dada una consulta algebraica sobre fragmentos, el objetivo de esta capa es hallar una estrategia de ejecución para la consulta cercana a la óptima. La estrategia de ejecución para una consulta distribuida puede ser descrita con los operadores del álgebra relacional y con primitivas de comunicación para transferir datos entre nodos.

Optimización Local de Consultas

El trabajo de la última capa se efectúa en todos los nodos con fragmentos involucrados en la consulta.

martes, 6 de noviembre de 2012

Algebra Relacional

Álgebra relacional

El álgebra relacional es un conjunto de operaciones que describen paso a paso como computar una respuesta sobre las relaciones, tal y como éstas son definidas en el modelo relacional. Denominada de tipo procedimental, a diferencia del Cálculo relacional que es de tipo declarativo.

Describe el aspecto de la manipulación de datos. Estas operaciones se usan como una representación intermedia de una consulta a una base de datos y, debido a sus propiedades algebraicas, sirven para obtener una versión más optimizada y eficiente de dicha consulta.

Las operaciones

Básicas

Cada operador del álgebra acepta una o dos relaciones y retorna una relación como resultado. σ y Π son operadores unarios, el resto de los operadores son binarios. Las operaciones básicas del álgebra relacional son:

Seleccióna (σ)

Permite seleccionar un subconjunto de tuplas de una relación (R), todas aquellas que cumplan la(s) condición(es) P, esto es:

$\sigma_P(R) \!$

Ejemplo:

$\sigma_{Apellido=Gomez}(Alumnos) \!$

Selecciona todas las tuplas que contengan Gómez como apellido en la relación Alumnos.
Una condición puede ser una combinación booleana, donde se pueden usar operadores como: $\wedge$ , $\vee$ , combinándolos con operadores $<, >, \le, \ge, =, \ne$ .

Proyección (Π)

Permite extraer columnas (atributos) de una relación, dando como resultado un subconjunto vertical de atributos de la relación, esto es:

$\Pi_{A_1,A_2,\dots,A_n} \!$

donde $A_1,A_2,\dots,A_n$ son atributos de la relación R .
Ejemplo:

$\Pi_{Apellido,Semestre,NumeroControl}(Alumnos) \!$

Selecciona los atributos Apellido, Semestre y NumeroControl de la relación Alumnos, mostrados como un subconjunto de la relación Alumnos

Producto cartesiano (x)

El producto cartesiano de dos relaciones se escribe como:

$R \times S$

y entrega una relación, cuyo esquema corresponde a una combinación de todas las tuplas de R con cada una de las tuplas de S, y sus atributos corresponden a los de R seguidos por los de S.
Ejemplo:

$Alumnos \times Maestros$

Muestra una nueva relación, cuyo esquema contiene cada una de las tuplas de la relación Alumnos junto con las tuplas de la relación Maestros, mostrando primero los atributos de la relación Alumnos seguidos por las tuplas de la relación Maestros.

Unión (∪)

La operación

$R \cup S$

retorna el conjunto de tuplas que están en R, o en S, o en ambas. R y S deben ser uniones compatibles.

Diferencia (-)

La diferencia de dos relaciones, R y S denotada por:

$R - S \!$

entrega todas aquellas tuplas que están en R, pero no en S. R y S deben ser uniones compatibles.

Estas operaciones son fundamentales en el sentido en que (1) todas las demás operaciones pueden ser expresadas como una combinación de éstas y (2) ninguna de estas operaciones pueden ser omitidas sin que con ello se pierda información.

No básicas o Derivadas

Entre los operadores no básicos tenemos:

Intersección (∩)

La intersección de dos relaciones se puede especificar en función de otros operadores básicos:

$R \cap S = R - (R - S)$

La intersección, como en Teoría de conjuntos, corresponde al conjunto de todas las tuplas que están en R y en S, siendo R y S uniones compatibles.

Unión natural ( $\bowtie$ ) (Natural Join)

La operación unión natural en el álgebra relacional es la que permite reconstruir las tablas originales previas al proceso de normalización. Consiste en combinar las proyección, selección y producto cartesiano en una sola operación, donde la condición $\theta$ es la igualdad Clave Primaria = Clave Externa (o Foranea), y la proyección elimina la columna duplicada (clave externa).
Expresada en las operaciones básicas, queda

$R \bowtie S = \Pi_{A1,A2...An} ( \sigma_\theta (R\times S) )$

Una reunión theta ( θ-Join) de dos relaciones es equivalente a:

$R \bowtie_\theta S = \sigma_\theta (R\times S)$

donde la condición $\theta$ es libre.
Si la condición $\theta$ es una igualdad se denomina EquiJoin.

División (/)

Supongamos que tenemos dos relaciones A(x, y) y B(y) donde el dominio de y en A y B, es el mismo.
El operador división A / B retorna todos los distintos valores de x tales que para todo valor y en B existe una tupla $\langle x,y \rangle$ en A.

Agrupación (Ģ)

Permite agrupar conjuntos de valores en función de un campo determinado y hacer operaciones con otros campos.
Por ejemplo: Ģ _{sum(puntos) as Total Equipo} (PARTIDOS).

Ejemplos!

*Alumno*
ID	NOMBRE	CIUDAD	EDAD
01	Pedro	Bogota	14
11	Juan	Cali	18
21	Diego	Cartagena	12
31	Rosita	Medellin	15
41	Manuel	Cartagena	17

*Apoderado*
ID	NOMBRE	FONO	ID_ALUMNO
054	Víctor	654644	21
457	José	454654	11
354	María	997455	31
444	Paz	747423	01

*Curso*
COD	NOMBRE	FECHA_INICIO	DURACION	VALOR
01142	Sicología	13-01	15	3.000
02145	Biología	15-02	12	2.500
03547	Matemáticas	01-03	30	4.000
04578	Música	05-04	10	1.500
05478	Física	20-04	15	3.200

*Inscrito*
ID	ID_AL	COD
1	01	05478
2	01	02145
3	11	03547
4	21	02145
5	41	03547

Mostrar los nombres de los alumnos y su apoderado
Primero, realizaremos una combinación entre alumnos y apoderados (pues necesitamos saber a que alumno le corresponde tal apoderado). La combinación realizará un producto cartesiano, es decir, para cada tupla de alumnos (todas las filas de alumnos) hará una mezcla con cada una tupla de apoderados y seleccionará aquellas nuevas tuplas en que alumnos.id sea igual a apoderados.id_alumno, esto es:

ID (alumno)	NOMBRE (alumno)	CIUDAD	EDAD	ID (apoderado)	NOMBRE (apoderado)	FONO	ID_ALUMNO
01	Pedro	Santiago	14	054	Víctor	654644	21
01	Pedro	Santiago	14	457	José	454654	11
01	Pedro	Santiago	14	354	María	997455	31
01	Pedro	Santiago	14	444	Paz	747423	01
11	Juan	Buenos Aires	18	054	Víctor	654644	21
11	Juan	Buenos Aires	18	457	José	454654	11
11	Juan	Buenos Aires	18	354	María	997455	31
11	Juan	Buenos Aires	18	444	Paz	747423	01
21	Diego	Lima	12	054	Víctor	654644	21
21	Diego	Lima	12	457	José	454654	11
21	Diego	Lima	12	354	María	997455	31
21	Diego	Lima	12	444	Paz	747423	01
31	Rosita	Concepción	15	054	Víctor	654644	21
31	Rosita	Concepción	15	457	José	454654	11
31	Rosita	Concepción	15	354	María	997455	31
31	Rosita	Concepción	15	444	Paz	747423	01
41	Manuel	Lima	17	054	Víctor	654644	21
41	Manuel	Lima	17	457	José	454654	11
41	Manuel	Lima	17	354	María	997455	31
41	Manuel	Lima	17	444	Paz	747423	01

Analizador sintáctico

Un analizador sintáctico (en inglés parser) es una de las partes de un compilador que transforma su entrada en un árbol de derivación.

El análisis sintáctico convierte el texto de entrada en otras estructuras (comúnmente árboles), que son más útiles para el posterior análisis y capturan la jerarquía implícita de la entrada. Un analizador léxico crea tokens de una secuencia de caracteres de entrada y son estos tokens los que son procesados por el analizador sintáctico para construir la estructura de datos, por ejemplo un árbol de análisis o árboles de sintaxis abstracta.
El análisis sintáctico también es un estado inicial del análisis de frases de lenguaje natural. Es usado para generar diagramas de lenguajes que usan flexión gramatical, como los idiomas romances o el latín. Los lenguajes habitualmente reconocidos por los analizadores sintácticos son los lenguajes libres de contexto. Cabe notar que existe una justificación formal que establece que los lenguajes libres de contexto son aquellos reconocibles por un autómata de pila, de modo que todo analizador sintáctico que reconozca un lenguaje libre de contexto es equivalente en capacidad computacional a un autómata de pila.
Los analizadores sintácticos fueron extensivamente estudiados durante los años 70 del siglo XX, detectándose numerosos patrones de funcionamiento en ellos, cosa que permitió la creación de programas generadores de analizadores sintáticos a partir de una especificación de la sintaxis del lenguaje en forma Backus-Naur por ejemplo, tales como yacc, GNU bison y javaCC.

Heurística (informática)

En computación, dos objetivos fundamentales son encontrar algoritmos con buenos tiempos de ejecución y buenas soluciones, usualmente las óptimas. Una heurística es un algoritmo que abandona uno o ambos objetivos; por ejemplo, normalmente encuentran buenas soluciones, aunque no hay pruebas de que la solución no pueda ser arbitrariamente errónea en algunos casos; o se ejecuta razonablemente rápido, aunque no existe tampoco prueba de que siempre será así. Las heurísticas generalmente son usadas cuando no existe una solución óptima bajo las restricciones dadas (tiempo, espacio, etc.), o cuando no existe del todo.
A menudo, pueden encontrarse instancias concretas del problema donde la heurística producirá resultados muy malos o se ejecutará muy lentamente. Aun así, estas instancias concretas pueden ser ignoradas porque no deberían ocurrir nunca en la práctica por ser de origen teórico. Por tanto, el uso de heurísticas es muy común en el mundo real.

Objetivos de los sistemas de bases de datos

Corregir anomalías en el acceso concurrente: Para mejorar el funcionamiento del sistema y tener un tiempo de respuesta más corto, muchos sistemas permiten que varios usuarios actualicen la información simultáneamente. En un ambiente de este tipo, la interacción de las actualizaciones concurrentes puede resultar en información inconsistente. Para prevenir estas situaciones debe mantenerse alguna forma de supervisión en el sistema.

Arboles de consultas

Transformaciones equivalentes

1.-el servidor recive una peticion de un nodo

2.-el servidor es atacado por el acceso concurrente a la base de datos cargada localmente

3.-el servidor muestra un resultado y le da un hilo a cada una de las maquinas nodo de la red local.

Una base de datos es accesada de esta manera la técnica que se utiliza es la de fragmentación de datos que puede ser hibrida, horizontal y vertical.

En esta fragmentación lo que no se quiere es perder la consistencia de los datos, por lo tanto se respetan las formas normales de la base de datos ok.

Bueno para realizar una transformación en la consulta primero desfragmentamos siguiendo los estandares marcados por las reglas formales y posteriormente realizamos el envio y la maquina que recibe es la que muestra el resultado pertinente para el usuario, de esta se puede producir una copia que sera la equivalente a la original.