BDA-Unidad I. Base de datos orientadas por objetos (BDOO)

UNIVERSIDAD DE LOS ANDES
FACULTAD DE INGENIERÍA
POSTGRADO EN COMPUTACIÓN

Tema 5. Lenguajes de definición, manipulación y control, y su procesamiento

Prof. Isabel Besembel Carrera

Núcleo La Hechicera. Edif. Economía. 3er. piso. Ala 3S. Mérida. Venezuela.

Sesión 6. OSQL y OQL. Cálculo de predicados OO. Procesamiento de consultas en BDOO.

En la década de los 90, los lenguajes de definición y manipulación de datos orientados por objetos eran numerosos debido a la falta de normalización, pero hoy en día está reconocido el lenguaje ODMG como el estándar a seguir por las compañías que producen SGBDOO. El estándar ODMG presenta el lenguaje ODL como el lenguaje de definición y el OQL como lenguaje de consulta. A continuación se describen brevemente los lenguajes OSQL y OQL, ambos surgen como posibles estándares, con similitudes interesantes dado que ambos fueron diseñados por grupos de trabajo de OMG.

Lenguaje OSQL

Es un lenguaje para bases de datos que combina las expresiones de los lenguajes de programación orientados por objetos con los lenguajes de definición y manipulación de datos, como un superconjunto de SQL. Fue desarrollado en el proyecto Iris por HP entre 1989 y 1991. Está influenciado por Daplex y Taxis. Provee las ventajas de:

la orientación por objetos (modelo más intuitivo, reusabilidad de código y extensibilidad)
los lenguajes de bases de datos (Optimización de consultas, restricciones de integridad, multiusuarios concurrentes, autorización y seguridad)

Se diferencia de C++ en que no mezcla la definición de la interfaz de un tipo con una representación particular de sus instancias.

Permite la definición de la interfaz de un tipo independientemente de una implementación específica de dicha interfaz, la cual puede cambiar a través del tiempo.

El estado de los objetos se define con funciones que devuelven el valor de los atributos, sus interrelaciones con otros objetos y cálculos adicionales.

Disociando la interfaz del tipo de la representación de sus instancias, los objetos pueden perder y adquirir dinámicamente su tipo, permitiendo el modelado de la evolución de los objetos durante su tiempo de vida.

OSQL chequea tipos a tiempo de compilación y deberá tenerlo también a tiempo de ejecución para permitir los cambios dinámicos.

El principal constructo de modelado es la función:

almacenadas (teniendo el valor)
calculadas (con un cuerpo de la función en OSQL)
externas (con un cuerpo de la función en un LP)

Funciones:

Una función puede modelar atributos y relaciones almacenadas o derivadas y cálculos arbitrarios. Se aceptan múltiples nombres iguales de funciones pero con diferentes argumentos, pero actualmente todas ellas deben tener el mismo tipo de resultado. Una función que no regrese nada se declara con el tipo Void. Los transformadores NO pueden ser invocados como parte de una consulta. Toda función tiene una extensión que es la función desde sus argumentos a sus resultados. Las funciones con extensiones calculadas pueden ser implementadas como expresiones en OSQL o como programas en un LPAN (funciones externas). Las funciones son actualizables.

Una función f actualizable tiene una función compañera set_f que coloca el valor que regresará f para un argumento dado, cuando f es invocada. Si f regresa un tipo agregado, entonces tendrá tres funciones: set, add y remove, las cuales pueden ser especificadas explicitamente o ser generadas automaticamente por el sistema.
Ejemplo:
create function translate (Char inglés) -> Char /* francés */,
translate(‘one’) -> ‘un’;

Lenguaje de consulta: Su semántica está basada en el cálculo de dominios soportando dominios agregados y funciones. Sintaxis:

    select:= resStruct : ResStruct          (opcional) 
	          resList : Expr+ 
	          forEach : Declaration*         (opcional) 
	          where : Expr                   (opcional) 
	          groupBy : Group*               (opcional) 
	          having : Expr                  (opcional) 
	          orderBy : orderSpec*;          (opcional)

En OpenODB, la consulta de encontrar el nombre del profesor cuyo identificador es p se expresa como
select nombre(p)
el compilador inferirá el tipo de la expresión como BagType(TupleType(Char)).

Para cambiar el tipo de resultado se utiliza la palabra atomic para tener una bolsa de cadenas. Para tener solo un valor se anexa la palabra single, ejemplo: select single atomic nombre(p)

Las expresiones de selección se evaluan pasándolas como argumento a la función definida en el sistema que hace dicho trabajo. Dicha función compila la consulta creando una función sin nombre y sin argumentos cuyo cuerpo es la consulta compilada y optimizada. La consulta se evalúa llamando a esa función sin nombre. Si la consulta está fuera de una función, la función sin nombre es transiente y se elimina luego de evaluarla, de lo contrario ella forma parte de la función.

Para tener un conjunto como resultado se usa la palabra distinct. Si se usa orderBy se regresará una lista en vez de una bolsa.

Ejemplo: Encontrar la lista de nombres y Oids de los profesores cuyo nombre es mayor que fr

    create function ProfxNom(Char fr, Integer n) -> ListType(TupleType(Char, Profesor)) as osql 
	 begin 
	    declare Cursor c; 
	    declare ListType(TupleType(Char, Profesor)) r; 
		if (n > 0) then 
		    open cursor c for select nombre (p), p  for each Profesor p 
			                  where nombre (p) >= fr 
							  orderBy nombre (p); 
		else begin 
            open cursor c for select nombre (p), p for each Profesor p 
			                   where nombre (p) >= fr 
							   orderBy nombre (p) desc; 
			n := n * -1; 
			end; 
		endif; 
		r := fetch(c,n);          /* Obtener los primeros n elementos del cursor c */ 
		close (c); 
		return r; 
	end

Dicha función puede ser usada para encontrar un profesor si n=1, también puede ser usada para barrer el conjunto de profesores con un n dado. La claúsula for each define el dominio de la búsqueda declarando la lista de identificadores y sus tipos. La claúsula where es una expresión funcional que regresa cualquier número natural (0: Falso, 1 o más: Verdadero)

Lenguaje OQL

El estándar ODMG contiene el lenguaje Object Query Language (OQL) que incluye el lenguaje Object Definition Language (ODL) que define el esquema de la base de datos orientada por objetos. Este esquema debe seguir las directrices del modelo de objetos del ODMG, descrito en la sesión que lleva su nombre.

Las consultas en OQL utilizan una sintaxis similar al SQL del modelo relacional, trata objetos complejos sin privilegiar al constructor Set y la cláusula SELECT-FROM-WHERE.

No es computacionalmente completo, pero las consultas pueden invocar métodos.
Provee acceso declarativo a los objetos.
Tiene una sintaxis del tipo SQL.
Provee primitivas de alto nivel para manejar conjuntos, estructuras y listas en forma eficiente.
No tiene operadores de actualización pero permite la ejecución de operaciones con esa responsabilidad.
Permite las consultas sobre los objetos denotables del modelo indicando su nombre.
Como lenguaje embebido permite la consulta desde cualquier LPAN.
Una consulta en OQL es una función que aplicada a una entrada da como resultado un objeto cuyo tipo puede ser inferido por el operador inmerso en la consulta.

Ejemplo: Regresa un literal del tipo Set <Integer>

     select distinct x.edad
     from x in personas
     where x.nombre = ”Manuel”

Ejemplo que regresa un literal del tipo Set<Struct>, donde a y s son los nombres de las columnas de despliegue que no tiene porque coincidir con los nombres de los atributos almacenados

      select distinct struct( a:e.edad, s:x.sexo )
      from x in Personas
      where x.nombre = ”Manuel”

Ejemplos que regresan un set<struct( nombre: String, su: Bag<Empleado> ) >

 
(1)   select dictinct struct( nombre:x.nombre, su: (select y 
                                                    from y in x.subordinados
                                                    where y.salario > 200000 ))
      from x in Empleados

(2)      select struct( a:e.edad, s:x.sexo )
         from x in ( select y from y in Empleados where y.salario > 150000 )
         where x.nombre = ”Mauel”

no siempre hay que usar la cláusula select, si se coloca únicamente

     Personas

regresa el conjunto de todas las personas.

Creación de objetos:

Para crear un objeto con identidad (mutable)

     Persona( nombre: ”Manuel”, apellido: “Fuente”, fechaDeNac: ”12/4/62”, sexo: ”M”, dir: ”Av.5 Nro.21-14”, ciudad: “Mérida”, tel: ”445455” )

Para crear un objeto sin identidad (literal) con dos ranuras denominadas a y b cuyo contenido es a = 10 y b = 'Carlos'

     struct( a: 10, b: Carlos )

Definición de tipos

Se pueden definir los siguientes tipos

(1)     type bolEnt: Bag<Integer>;
(2)     type stat
            attributes a: Integer
                       s: Char
        end_type;
(3)     type stats: Bag<stat>;

entonces la consulta siguiente regresa un objeto mutable del tipo bolEnt, es decir una bolsa de valores enteros que son las edades de todas las personas que se llaman Manuel

      bolEnt( select distinct x.edad
              from x in Personas  
              where x.nombre = ”Manuel” )

y la consulta expresada a continuación regresa un objeto mutable del tipo stats que contiene una bolsa de tuplas con la edad y el sexo de todas las personas que se llaman Manuel

      stats( select distinct struct( a: x.edad, s: x.sexo )
             from x in Personas
             where x.nombre = ”Manuel” )

Definición de expresiones de consultas:

Una consulta se compone de un conjunto, posiblemente vacío y no recursivo, de definiciones de consultas seguido por una expresión. El ejemplo siguiente define el conjunto de empleados de apellido Vivas con su cédula respectiva

     define Vivas as select distinct x from x in Empleados where x.apellido = ”Vivas”;
     select distinct x.cedula from x in Vivas

Para definir una consulta cuyo nombre es q según la expresión e. Si se usa distinct es un conjunto (set)..

     define q as e

Definición de expresiones elementales:

Si x es una variable, entonces x es una expresión.
Si a es un átomo, entonces a es una expresión, que define al átomo mismo,
Si e es un objeto con nombre, entonces e es una expresión.
Si q es el nombre de una consulta ya definida, entonces q es una expresión.

Ejemplos:

45 regresa 45
Nil regresa el objeto nil (no existe)
Empleados regresa el conjunto de empleados, siendo este conjunto la extensión de la clase Empleado.
Vivas regresa el conjunto de estudiantes cuiyo apellido es Vivas.

Construcción de expresiones:

Para construir objetos:

Si t es un tipo con p₁, p₂,…, p_n propiedades y e₁, e₂,…, e_n son expresiones, entonces t( p₁: e₁,…, p_n: e_n ) es una expresión. Los tipos deben ser compatibles.
Si t es un tipo colección y e es una colección inmutable, entonces t (e) es un objeto colección.

Ejemplo de construcción de objetos:

      Empleado( apellido: ”Rivas”, jefe: ”Mendez” )
      bolEnt ( set ( 2, 4, 6 ) )

Construcción de estructuras: Si p1,…, pn son propiedades y e1,…, en son expresiones entonces struct ( p1: e1,…, pn: en ) es una expresión.
Ejemplo de construcción de estructuras:

     struct( nombre: ”Manuel”, edad: 28 )

Construcción de conjuntos: si e₁,…, e_n son expresines, entonces set ( e₁,…, e_n ) es una expresión.
Ejemplo de construcción de conjuntos:

     set( 2, 4, 6, 8 )

Construcción de listas: si e₁,…, e_n son expresiones, entonces list ( e₁,…, e_n ) una expresión.
Ejemplo de construcción de una lista de números enteros:

       list( 1, 1, 2, 5, 9 )

Construcción de bolsas (Bag): si e₁,…, e_n son expresiones, entonces bag ( e₁,…, e_n ) una expresión.
Ejemplo de construcción de una bolsa de números enteros:

     bag( 1, 1, 2, 5, 5, 9 )

Construcción de arreglos: si e₁,…, e_n son expresiones, entonces array ( e₁,…, e_n ) una expresión.
Ejemplo de construcción de un arreglo de números enteros:

     array( 1, 2, 5, 9 )

Construcción de expresiones aritméticas: pueden ser unarias o binarias
Unarias: Si e es una expresión y op un operador unario, entonces op( e ) es una expresión. Ejm: not( true )
Binarias: Si e₁ y e₂ son expresiones y op es un operador binario, entonces e₁ op e₂ es una expresión. Ejm: count( Empleados ) - count( Preparadores )
Construcción de expresiones de tipo colección:
Cuantificación universal: Si x es una variable, e₁ y e₂ son expresiones donde e1 denota una colección y e₂ un predicado, entonces for all x in e₁ : e₂ es una expresión que regresa verdadero si todos los elementos de la colección e₁ satisfacen el predicado e₂, de lo contrario regresa falso.
Cuantificación existencial: Si x es una variable, e₁ y e₂ son expresiones donde e₁ denota una colección y e₂ un predicado, entonces exists x in e₁ : e₂ es una expresión que regresa verdadero si hay al menos un elemento de la colección e₁ satisface el predicado e₂, de lo contrario regresa falso.
Prueba de membresía: Si e₁ y e₂ son expresiones donde e₂ es una colección y e₁ tiene el mismo tipo de los elementos de e₂, entonces e₁ in e₂ es una expresión que regresa verdadero si e₁ pertenece a la colección e₂.

Consultas con la instrucción select-from-where:

Si e, e’, e₁,…, e_n son expresiones y x₁,…, x_n son variables, entonces select[distinct] e from x₁ in e₁,…, x_n in e_n where e’
es una expresión.
El resultado de la consulta es un conjunto si se usa distinct y una bolsa (bag) si no.
Si cada expresión en la lista de expresiones e₁,…, e_n es un conjunto en una bolsa (bag), entonces el resultado se obtiene aplicando el producto cartesiano de los conjuntos y filtrando el resultado con e’, y luego se aplica e a cada uno de los elementos del conjunto filtrado y se obtiene el resultado.
Si alguna de las colecciones está indexada, primero se convierten todas las colecciones a conjuntos y luego se aplica lo anterior.

Uso del operador sort-by: si e, e₁, …, e_n son expresiones y x una variable libre, entonces sort x in e by e₁, …, e_n es una expresión que regresa la lista de los elementos de e ordenados lexicograficamente por las funciones e₁, …, e_n. Ejemplo de ordenación del conjunto de personas x por edad y nombre: sort x in Personas by x. edad, x. nombre

Conjunto de operadores unarios: si e es una expresión que denota una colección y op es un operador en el conjunto { min, max, count, sum, avg }, entonces op( e ) es una expresión. Ejemplo de la aplicación del operador unario calcular el máximo salario de los empleados: max( select x.salario from x in Empleado )

Uso del operador group-by: si e es una expresión que denota una colección, p₁, …, p_n son propiedades, e₁, …, e_n son expresiones con una variable libre x, p’₁, …, p’_n son propiedades y e’₁, …, e’_n son expresiones con una variable libre partición, entonces
group x in e by( p₁: e₁, …, p_n: e_n ) es una expresión y
group x in e by( p₁: e₁, …, p_n: e_n ) with ( p’₁: e’₁, …, p’_n: e’_n ) es una expresión
Ejemplo de agrupación de empleados en tres categorías, con bajo, medio y alto salario

 
     group x in Empleados by ( bajo: x.salario < 100000, 
                               medio: x.salario >= 100000 and x.salario < 300000,
                               alto: x.salario >= 300000 )

     group x in Empleados by ( dpto: x.nroDpto ) with ( salProm: avg( select w.salario from w in partition ))

Colecciones indexadas:

Para obtener el i-ésimo elemento de la colección: si e₁ y e₂ son expresiones, e₁ es una lista o un arreglo y e₂ es un entero, entonces e₁ [e₂] es una expresión. El subíndice se inicia en 0. Ejemplo de selección del segundo elemento de una lista: list( a, b, c, d )[1] regresa b.
Extraer una subcolección de una colección: si e₁, e₂ y e₃ son expresiones, e₁ es una lista o un arreglo, e₂ y e₃ son enteros, entonces e₁ [ e₂: e₃ ] es una expresión que extrae la subcolección de e₁ que se inicia en e₂ y termina en e₃. Ejemplo de selección de una lista de 3 elementos de la lista empezando en el elemento en la segunda posición: list( a, b, c, d )[ 1: 3 ] regresa la lista list( b, c, d ) Ejemplo de selección de los tres primeros empleados subordinados del empleado de apellido Barrera element( select x from x in Empleado where x.apellido = ”Barrera” ).subordinado[ 0: 2 ]

Concatenar dos colecciones indexadas: si e₁ y e₂ son expresiones y e₁ y e₂ son listas o arreglos, entonces e₁ + e₂ es una expresión. Ejemplo de la concatenación de dos listas de números enteros: list( 1, 2 ) + list( 2, 3 ) regresa la lista list( 1, 2, 2, 3 )

Expresiones de conjuntos:

Si e₁ y e₂ son expresiones, si op es una operador en el conjunto { union, except, intersect }, si e₁ y e₂ son conjuntos o bags, entonces e₁ op e₂ es una expresión. Cuando los tipos son diferentes, set y bag, el conjunto se convierte a bag y el resultado es bag. Ejemplo de selección de los empleados que no son preparadores: Empleados except preparadores. Ejemplo de unión de dos bolsas de números enteros en otra bolsa: bag( 2, 2, 3, 3, 3, 3 ) union bag( 2, 3, 4 ) regresa bag( 2, 2, 2, 3, 3, 3, 3, 3, 4 )

Expresiones para estructuras: si e es una expresión y p es una propiedad, entonces e -> p y e . p son expresiones. Si la propiedad no existe o ha sido eliminada regresa nulo. Ejemplo de selección del teléfono del primer estudiante en el conjunto definido como Vivas que tenga el teléfono diferente de nulo: Vivas -> telefono != ni1 regresa el teléfono si existe.

Conversión de expresiones:

Extrayendo un elemento: Si e es una expresión de valores de colección, element( e ) es una expresión. Ejemplo de selección del primer empleado con cargo de analista: element( select x from x in Empleados where x.cargo = ”analista” )

Pase de lista a conjunto: si e es una expresión lista, listtoset( e ) es una expresión. Ejemplo de conversión de una lista de enteros a un conjunto de enteros: littoset( list( 1, 2, 3, 2 )) regresa el conjunto { 1, 2, 3 }

Conversión de colecciones de colecciones a colección: Si e es una expresión de valores de colección, flatten( e ) es una expresión que convierte la colección de colecciones de t en una colección de t. Solo opera en el primer nivel. col1<col2<t>>

Si col2 es un set ( bag ), la union de todas las col2<t> es un set<t>( bag<t> )
Si col2 es una list ( array ) y col1 es una list ( array ), se concatenan todas las col2<t> siguiendo el orden en col1 y el resultado es col2<t>. Se mantienen los duplicados.
Si col2 es una list ( array ) y col1 es un set (bag), las listas o arreglos se convierten a conjuntos y se calcula la union de los conjuntos resultados set<t>.

Ejemplo de conversión de una lista de conjuntos de enteros en un conjunto de enteros: flatten( list( set( 1, 2, 3 ), set( 3, 4, 5, 6 ), set( 7 ))) regresa el conjunto{1,2,3,4,5,6,7}donde el elemento 3 solo aparece una vez, ya que es un conjunto y no una bolsa.

Afirmando el tipo de una expresión: Si e es una expresión y c su tipo, entonces ( c )e es una expresión. Es una aserción sobre el tipo de e. Si no es verdad se obtiene una excepción.

Expresiones de objetos: Si e, e₁, …, e_n son expresiones y f es un nombre de operación, entonces e -> f ( e₁, …, e_n ) y e . f( e₁, …, e_n ) son expresiones que aplican la operación f con los parámetros e₁, …, e_n al objeto e.

Cálculo de predicados

Cálculo de predicados de primer orden:

Especificación de un alfabeto de símbolos
Definición de las expresiones llamadas fórmulas bien formadas construidas a partir de los símbolos

Alfabeto:

Parentesis,
símbolo implica (=>),
símbolo negación lógica (¬),
constantes (a, b, c, ...),
variables (X, Y, Z, ...),
predicados con m argumentos (Q, R, S, ...) y
funciones con n argumentos (f, g, h, ...)

Las fórmulas se construyen en el alfabeto a partir de términos y fórmulas atómicas.

Término: es una constante, una variable o una función cuyos argumentos son términos.

Fórmula atómica: es un predicado con m argumentos que son a su vez términos.

Fórmula:

una fórmula atómica
si A es una fórmula entonces ¬A es también una fórmula
si A y B son fórmulas entonces A => B es también una fórmula

Se anexan al alfabeto los símbolos: y lógico ( /\ ), o lógico ( \/ ), el cuantificador universal para todo y el cuantificador existencial existe

Cálculo de predicados orientado por objetos

Una expresión en Cálculo de Predicados Orientado por Objetos (CPOO) tiene la forma siguiente:

{ destino ; rango ; cualificación }

donde:

toda constante está asociada a un valor particular
toda variable está asociada a un objeto particular
todo predicado está asociado a una clase particular
toda función está asociada a una función particular de alguna clase definida
destino especifica lo que se desea recuperar y se expresa como X o X . Pi, donde X es una variable objeto y X . Pi denota la propiedad i en el rango de clases de X.
rango define la asociación de una variable objeto con una clase y se expresa como X/C, con lo cual se define el tipo de la variable (propiedades y comportamiento) y el rango de la misma (extensión de la clase). El alcance de la variable está definido por el rango y la cualificación de la expresión.
cualificación definida por una fórmula bien formada (combinación de predicados lógicos conectados con operadores lógicos)

Las cláusulas destino y rango son obligatorias.

La igualdad se verifica bajo las siguientes condiciones:

Dos objetos O y O' son idénticos si tienen el mismo identificador de objeto (oid)
Dos literales L y L' son iguales si tienen el mismo valor
Dos objetos O y O' son iguales si cumplen las condiciones siguientes:
- O y O' poseen el mismo número de propiedades
- Para toda Pi de O existe una Pj de O' tal que nombre( Pi ) = nombre( Pj) y Pi y Pj tienen valores iguales según lo siguiente:
  - estructura( Pi ) = estructura( Pj )
  - si estructura( Pi ) = valor monovaluado entonces O.Pi debe ser igual a O'.Pj
  - si estructura( Pi ) = valor multivaluado entonces O.Pi y O'.Pj son colecciones que verifican lo siguiente:
    1. cardinalidad( O.Pi ) = cardinalidad( O'.Pj )
    2. para todo objeto Ok en O.Pi existe un objeto O'k en O'.Pj tal que Ok y O'k tienen los mismos valores o tienen los mismos oids

El operador de igualdad de valores es = y el de igualdad de oids es == (idénticos)

Las colecciones se denotan con C y los predicados que se aplican pueden ser:

Membresía: Y pertenece X.P, donde P es una propiedad multivaluada. El predicado devolverá el valor verdadero si Y es un miembro de la colección X.P
Inclusión: Y.P incluido X.P', donde P y P' son propiedades multivaluadas. El predicado regresa verdadero si los valores de Y en el objeto P están incluidos en X.P'

Los cuantificadores existencial y universal se restringen para enlazar el objeto denotado por la variable a la clase de la propiedad multivaluada P:

para todo X / Y.P
existe X / Y.P

La navegación a través de objetos compuestos se realiza con el operador punto ( . )

Se agrega el sufijo # a una clase particular en la jerarquía de clases para su utilización.

Para usar varias clases de la jerarquía y poder expresar el predicado adecuado a cada una o alguna de ellas, se incluye el operador classOf( X ) = [ c1: pred1, c2: pred2, ..., cn: predn ]

Para consultas recursivas se incluye el operador de recursión µ cuya semántica es:

     S <- O.P
     repita hasta que S cambie
        S = S union { O' ; O'/P ; existe O''/C ( O'' pertenece S /\ ( O' op O''.P ))}
     frh

donde op es el operador == si la propiedad P es monovaluada y es el operador pertenece si P es multivaluada

Introducción al procesamiento de consultas

La mayoría de los procesadores de consultas de objetos propuestos hasta ahora usan las técnicas de optimización de los sistemas relacionales.

Diferencias con los optimizadores en Bases de Datos Relacionales (BDR):

Sistema de tipos: Los resultados de los operadores del algebra de objetos son normalmente colecciones de tipos diferentes, que a su vez pueden ser operandos de otros operadores. Ello requiere el desarrollo de esquemas de inferencia de tipos para determinar que método aplicar a todos los objetos de la colección. Adicionalmente, las colecciones son de tipos diferentes, por lo que hay que determinar el tipo de resultado de las operaciones sobre colecciones de diferentes tipos.

Encapsulación: La estimación de los costos de ejecución de los métodos es más complicada que la estimación de los costos de acceso a los atributos en base a su camino de acceso. Optimización de la ejecución de los métodos y ellos pueden escribirse en cualquier lenguaje de programación.

Proposiciones:

permitir al optimizador el rompimiento de la encapsulación o
que cada objeto mantenga sus costos como parte de su interfaz.

Objetos complejos y herencia: La optimización de los caminos de expresiones involucrados en los objetos complejos es un punto central, que a su vez involucra la jerarquía de herencia.

Modelo de objetos: La falta de un modelo universal de objetos hace que existan diversos enfoques, por lo general incompatibles. Por ello es necesario el desarrollo de enfoques extensibles que permitan la evolución con nuevas ideas.

Metodología

Las consultas se expresan en un lenguaje declarativo que no requiere que el usuario conozca de la implementación de los objetos, de los caminos de acceso o de las estrategias de procesamiento. La expresión del cálculo es primero reducida a una forma normalizada mediante la eliminación de predicados duplicados, aplicando identidades y reescribiendo la consulta.

La expresión normalizada se convierte a su expresión equivalente en algebra, que es un árbol cuyos nodos son los operadores y las hojas las extensiones de las clases de la BD. Luego se chequea la consistencia de los tipos y se le aplican las reglas de reescritura preservando la equivalencia, para luego finalmente, generar el plan de ejecución teniendo en cuenta las implementaciones de los objetos involucrados.

La separación de la reescritura de la consulta y de la generación del plan de ejecución hace la metodología extensible, como se puede observar en la figura 2.

Figura 2. Metodología de procesamiento de consultas de objetos.

Arquitectura del procesador de consultas

Arquitectura del optimizador:

La optimización de consultas puede ser modelada como un problema de optimización cuya solución es la escogencia de un estado óptimo en un espacio de estados.

Cada estado corresponde a una consulta algebraica representada con un árbol de procesamiento.

El espacio de estados es una familia de consultas algebraicas equivalentes.

Los optimizadores de consultas generan y buscan en un espacio de estados a través de una estrategia de búsqueda, aquel estado con costo mínimo según una función de costos aplicada a cada estado.

Un optimizador necesita de:

El espacio de estados y las reglas de transformación que generan las expresiones alternativas de la consulta que constituyen ese espacio de estados.
Un algoritmo de búsqueda para recorrer el espacio de estados.
La función de costos que se le aplicará a cada estado.

Técnicas de optimización

Los aspectos más resaltantes son:

Optimización algebraica y las reglas de transformación: Una expresión algebraica de una consulta se puede transformar usando las propiedades algebraicas de: transitividad, conmutatividad y distributividad. Cada consulta tiene un gran número de expresiones equivalentes que conforman el espacio de búsqueda. Cada una arroja el mismo resultado pero con diferentes costos.Las reglas de transformación dependen del algebra de objetos. La falta de un algebra estándar hace imposible la generalización de los resultados obtenidos en los estudios realizados.

La particularidad del algebra de objetos en relación con la relacional es el uso de las interrelaciones entre los objetos a través de su jerarquía para incluir transformaciones adicionales en el optimizador.

Ejemplo: tomando el algebra de objetos de Straube y Özsu de 1990 se tiene unión (\/), intersección (/\) y selección parametrizada P S_F Q₁,...,Q_k

( P S_F1 [QSet] ) S_F2 [RSet] <=> ( P S_F2 [RSet] ) S_F1 [QSet]
( P \/ Q ) S_F [RSet] <=> ( P S_F [RSet] ) \/ (Q S_F [RSet] )
( P S_F1 [QSet] ) S_F2 [RSet] <=> ( P S_F1 [QSet] ) /\ ( P S_F2 [RSet] )

La regla 1 captura la conmutatividad del select, la regla 2 la distributividad en la unión y la regla 3 es una identidad.

C_i conjunto de objetos de la extensión de la clase c_i

C_j* extensión profunda de la clase c_j ( la extensión de c_j más la de todas sus subclases).

C₁ /\ C₂ <=> vacío si c₁ <> c₂
C₁ \/ C₂* <=> C₂* si c₁ es una subclase de c₂

Estas reglas son semánticas y dependen del modelo de objetos y de consultas.

La primera es verdadera porque el modelo de objetos restringe cada objeto a pertenecer a una sola clase. La segunda porque el modelo de consultas permite la recuperación de objetos en la extensión profunda de la clase tratada.

Algoritmos de búsqueda:

Como todo el espacio está numerado, la búsqueda exhaustiva es la estrategia más obvia. Para mejorarla se utiliza programación dinámica, donde las nuevas expresiones se construye en usando la anterior subexpresión óptima. En general, estos se denominan algoritmos enumerativos, los cuales tienen un gran overhead.

Ya que muchas algebras de objetos tienen el operador producto u otro con una semántica similar, y dichas operaciones son numerosas y comunes en aplicaciones como la IA y sistemas de soporte a las decisiones, es necesario tener métodos para ejecutar expresiones de caminos que representan esos productos.

Los algoritmos de búsqueda aleatorizada son una alternativa para restringir la región de búsqueda, uno de ellos es la Recoción simulada y otro es la mejora iterativa, que combinados arrojan el método de optimización dos-fases. Estos algoritmos comienzan con un estado tomado al azar y viajan a través del espacio de búsqueda, evaluando el costo de cada estado y terminando el proceso cuando se alcanza el óptimo o expira el tiempo.

El paso entre estados está controlado por las reglas de transformación y por una estrategia de control global. El algoritmo de mejora iterativa permite el paso a otro estado cuyo costo sea menor, mientras que el otro permite el paso a otro estado de mayor costo si hay una cierta probabilidad de disminuir el costo a lo largo del proceso. Como estos son algoritmos heurísticos, ellos no garantizan el óptimo, pero convergen a un estado cercano a él.

Función de costos

Las típicas funciones de costos toman en cuenta el costo de E/S y de CPU, en sistemas no distribuídos, y adicionalmente el costo de comunicación en los distribuidos. Así también se teiene en cuenta el número de items (cardinalidad), el tamaño de los mismos y su organización.

La función de costos puede definirse recursivamente basada en el árbol de procesamiento algebraico. Si la estructura interna del objeto no es visible al optimizador, el objeto puede revelar su costo a través de su interfaz, que dependerá de su algoritmo de ejecución y de la colección sobre la que opera.

Parametrización:

El optimizador hace uso de las estadísticas de la BD al tiempo de compilación y ello es independiente de las estadísticas de tiempo de ejecución (carga actual).

No se toman en cuenta los cambios de la BD entre la optimización de la consulta y su ejecución.

Alternativas

Determinar un intervalo de optimización/reoptimización y reoptimizar periodicamente. Intervalos fijos o variables según la diferencia entre el tiempo de ejecución actual y el estimado.

Optimización paramétrica (selección dinámica del plan): el optimizador mantiene múltiples estrategias de optimización a tiempo de compilación, y hace la selección final del plan a tiempo de ejecución basado en varios parámetros del sistema y en las estadísticas actuales de la BD. Su desventaja es la posible explosión exponencial de los planes dinámicos como una función de la complejidad de la consulta y el número de parámetros de optimización desconocidos a tiempo de compilación.

Expresiones de caminos

La mayoría de los lenguajes permiten consultas con predicados que involucran condiciones sobre cadenas de referencias a objetos, denominadas expresiones de caminos o predicados complejos (productos implícitos).

Ellas proveen una notación suscinta y de alto nivel para expresar la navegación a través del grafo de composición de los objetos que permite la formulación de predicados sobre valores profundamente anidados en la estructura de los objetos.

Ellas pueden ser simples o de conjuntos, y pueden aparecer en cualquier parte de la consulta.

Sea p.m₁(l₁).m₂(l₂)....m_n(l_n) una expresión de camino, donde p es una variable que representa una instancia, l_i con 1 <= i <= n que representa una lista de argumentos (posiblemente vacía) para la función mi.

Expresión de camino simple: Si todas las funciones son simplemente valuadas.

Expresión de camino de conjunto: Si al menos una función está valuada en un conjunto.

Ejemplo:

Consulta:

 select c₁(e.nombre(), e.dpto().nombre(), e.cargo().nombre())
 from Empleado e in Empleados
 where e.dpto().planta().ubicación() == “Valencia”;

Luego del “parsing”

select c1 (e.nombre(), e.dpto().nombre(), e.cargo().nombre())
 from Empleado : e 
 where   ==
       /    \
“Valencia”    DOT
            /    \
           DOT    ubicación()
          /   \
         DOT   planta() 
        /   \
Empleados:e  dpto()

Luego de la reescritura (factorización de subexpresiones comunes y heurísticas)

project -> e.nombre(), e.dpto().nombre(), e.cargo().nombre()
 |
select -> e.dpto().planta().ubicación() == “Valencia”
 |           reescritura de los caminos dentro de los productos (caza-del-puntero)
mat -> e.dpto().planta()
 |
mat -> e.dpto()
 |   
mat -> e.cargo()
 |      
get -> Empleados : e

mat: operador de materialización, representa el cálculo de cada referencia explícita del objeto, permitiendo al optimizador expresar la materialización de múltiples componentes como un grupo o de cada componente simple.

Luego de la optimización

          project-alg -> e.nombre(), e.dpto().nombre(), e.cargo().nombre()
              |
          producto-hh-alg -> j.self == e.cargo 
         /                   \
barrido-alg                  producto-hh-alg -> d.self == e.dpto
    |                           /                            \
Extensión(Cargo):j    filtro-alg ->d.ubic == “Valencia”      barrido-alg
                         |                                        |
                ensamblado-alg -> d.planta                   Set(Empleados):e 
                         |
                  barrido-alg -> Extensión(Departamento):d

Ejemplos de reglas de transformación que usan el operador mat

Conmutatividad de mat y select

 mat c₁ (select c₂ (b₁)) select c₃ (mat c₄ (b₁))

 select c₁ (mat c₂ (b₁)) mat 31 (select c₄ (b₁)), si c₁ no depende de c₂

Conmutatividad de mat y producto (join)

mat c₁ (join c₂ (b₁b₂)) join c₃ ((mat c₄ (b₁))b₂), si c₁ solo depende de b₁

join c₁ (b₁ (mat c₂ (b₂))) mat c₃ (join c₄ (b₁b₂)), si c₁ no depende de c₂

Conmutatividad de mat

 mat c1 (mat c₂ (b₁)) mat c₂ (mat c₁ (b₁)), si c₁ no depende de c₂
    
 mat c₁ (mat c₂ (b₁)) mat c₃ (b₁)

De mat a join

 mat c₁ (b₁) join c₂ (b₁ (get c₃ ())), si c₁ es una colección iterable

Si la extensión de Departamento está indexada, el plan óptimo de ejecución equivalente al anterior es:

          project-alg -> e.nombre(), e.dpto().nombre(), e.cargo().nombre()
              |
          producto-hh-alg -> j.self == e.cargo 
         /                   \
barrido-alg                  producto-hh-alg -> d.self == e.dpto
    |                           /              \
Extensión(Cargo) : j   barrido-índice-alg      barrido-alg 
                                     |               |
           dpto.planta.ubic = = “Valencia” : d      Set(Empleados) :e

Ejecución de las consultas:

La ejecución la realiza el manejador de objetos, por lo que la última fase del optimizador genera un conjunto de llamadas a la interfaz del manejador.

En el futuro esos algoritmos de ejecución pueden formar parte de una máquina de ejecución de consultas. Los tipos de algoritmos que se necesitan son: Barrido de una colección, barrido con índice y equiparamiento de colecciones.

Índices de caminos

La estructura más utilizada para soportarlos es el árbol_B+ cuyo costo es O(log N).

En BDOO se utilizan tres tipos de índices: por la jerarquía de clases, por los atributos anidados y el combinado. Adicionalmente, Kemper y Moerkotte, 1994 proponen el uso de las denominadas relaciones para soportar el acceso, que sirven para representar y calcular las expresiones de caminos.

Índice de la jerarquía de clases:

Es un índice construido sobre un atributo de una clase de la jerarquía global, donde dicha clase es la raíz de la subjerarquía.

Ejemplo: sobre el atributo nombre de la clase Empleado.

Índice de atributos anidados:

Es un índice construido sobre un atributo de una clase incluyendo todas aquellas clases donde dicho atributo esté anidado.

Ejemplo: sobre el atributo ubicación de la clase Empleado.

Equiparamiento de colecciones:

Sean dos conjuntos de objetos R y S que mantienen una relación 1:M de R a S, donde R y S están almacenados en archivos de disco separados y cada objeto de R contiene un Oid a su objeto relacionado en S.

Producto hash-híbrido:

Aplica la técnica de divide-y-vencerás dividiendo recursivamente los grandes conjuntos de entrada en pequeños subconjuntos (cubetas) donde cada una cabe en memoria principal, utilizando una función hash sobre el atributo del producto. Al final cada subarchivo contiene los objetos del archivo de entrada que potencialmente pueden estar en el producto. Cada par de subarchivos es juntado para obtener el resultado final. Este algoritmo consiste de B+1 etapas donde B = Max( 0, ( ( | R | * F - | M | ) / ( | M | - 1 ) ) siendo | R | y | M | el tamaño de cada subarchivo y de la memoria principal disponible, respectivamente, F es normalmente 1.2.

Producto hash-híbrido basado en punteros:

Se usa cuando cada objeto de R contiene un puntero al objeto de S. R es particionado por el puntero en vez de usar el atributo del producto. S no se particiona. Se forma la tabla hash para subconjunto de R, todos los objetos que referencien la misma página de S se agrupan en la misma entrada de la tabla hash. Por último, se juntan los objetos de R con los de la misma página en S. Solo se divide R debido a la dirección de los punteros.

El operador ensamblar:

Es una generalización del anterior y se usa para calcular un producto multivías y solo es correcto cuando opera sobre conjuntos, no sobre listas. El operador trabaja con una ventana de ensamblado de tamaño fijo W para ensamblar W objetos complejos simultaneamente. Tan pronto como alguno de los objetos esté ensamblado, este es pasado al árbol de jecución de consultas y un nuevo objeto complejo es cargado. El orden de ensamblado de los objetos es aleatorio.

Ejemplo: se tienen dos objetos del tipo Empleado E1 y E2, donde cada empleado tiene entre sus atributos el departamento donde trabaja (D1 y D2) y el cargo que ocupa (C1 y C2). Cada departamento está ubicado en una planta (P1 y P2). Como los departamentos, cargos y plantas están descritos en tipos aparte, los atributos del tipo Empleado y Departamento tienen referencias a los objetos en los tipos respectivos.
Si se usa W = 2, el algoritmo comienza con dos objetos E1 y E2 (fila a). Si se selecciona E1, se busca y obtienen dos nuevas referencias no resueltas que son D1 y C1 (fila b). Seleccionando E2. se obtienen dos nuevas referencias no resueltas D2 y C2 (fila c) y así sucesivamente hasta que el primer objeto E1 está completamente ensamblado, al encontrar D1, C1 y P1.

Referencias	Objetos parcialmente ensamblados
a. E1, E2
b. E2, D1, C1	E1
c. D1, C1, D2, C2	E1, E2
d. C1, D2, C2, P1	E1, E2 D1
e. D2, C2, P1	E1, E2 D1, C1
f. D2, P1	E1, E2 D1, C1, C2
g. D2	E1, E2 D1, C1, C2 P1

Programa

Introducción OSQL y OQL Lenguaje OSQL Lenguaje OQL Cálculo de predicados Cálculo de predicados orientado por objetos Introducción procesamiento de consultas	Arquitectura del procesador de consultas Técnicas de optimización Algoritmos de búsqueda Función de costos Expresiones de caminos Índices de caminos
Referencia bibliográfica: Atwood, T et al. The object database standard: ODMG-93. Morgan Kaufmann. Cap. 3 y 4. 1994.	Won, K. Modern database systems. The object model, interoperability, and beyond. Addison Wesley / ACM Press. Capítulo 3 y 8. 1995.