postgresqlf

PostgreSQLfImplementación de Cuantificadores Difusos

Sobre el SGBD PostgreSQL

Autor:Gustavo Bazán

Tutora:Ana Aguilera

Introducción El Problema Objetivos Justificación Marco Teórico Metodología Resultados Conclusiones

Agenda

Introducción

Agenda• Introducción• El Problema• Objetivos• Justificación• Marco Teórico• Metodología• Resultados• Conclusiones

Datos Precisos


ContraDatos Imprecisos

Un objeto de 1500Kg se aproxima a tu cabeza a 50Km/s ¡CUIDADO

!

Cuantificación Lingüística: “Un hotel que satisface la mayoría de los

siguientes criterios: no muy caro, cercano al centro de convenciones, cercano a una estación del metro, con piscina, con buenas áreas de recreación, cercano a un centro comercial”

“Los pacientes que presenten la mayoría de los síntomas: fiebre alta, tensión baja, tos grave”

“Los empleados tengan al menos 2 de las siguientes características: ser buen trabajador, mal pagado y vivir lejos”

El Problema


Consulta Clásica

"Un hotel que no cuesta más de Bs. 500 por día, con piscina y a no más de 5 Km de distancia del centro de convenciones, del metro y de un centro comercial ".

• En SQL:SELECT * FROM HOTELS

WHERE price < 500 AND distance_conference < 5 AND distance_sub < 5 AND distance_mall < 5 AND pool=true

El Problema


Requerimientos que impliquen términos como “la mayoría” o “aproximadamente 4” no pueden ser expresados por medio de lenguajes de consultas, basados en el paradigma relacional.

Los requerimientos del usuario deben ser expresados de forma precisa.

Los Sistemas Clásicos de Manipulación de Bases de Datos no permiten expresar requerimientos graduales.

El Problema


Aplicaciones a nivel de capa lógica resuelven el problema, pero sus costos computacionales son muy elevados.

El Problema


Objetivo General Desarrollar un sistema que permita hacer consultas de tipo flexible haciendo uso de cuantificadores difusos en un Sistema Gestor de bases de Datos Relacionales (SGBDR).

Requerimientos: Deberá acoplarse de manera fuerte con el

SGBDR PostgreSQL Debe brindar mecanismos que puedan

ayudar de cierta forma a manejar la imprecisión del lenguaje natural.

Objetivos de la Investigación


Objetivos Específicos

Estudiar el uso de los diferentes tipos de Cuantificadores difusos, así como su interpretación en consultas cuantificadas.

Analizar la infraestructura del SGBDR PostgreSQL con la finalidad de poder determinar las diferentes áreas que se deben modificar para la implementación de PostgreSQLf.



Objetivos Específicos

Implementar la funcionalidad de creación y evaluación de Cuantificadores difusos.

Integrar la implementación de Cuantificadores Difusos con el resto de PostgreSQLf.

Evaluar el desempeño de PostgreSQLf en términos de eficiencia y funcionalidad de los cuantificadores difusos.



Mecanismos de calidad para accesos a datos:

◦ Mejorar la expresividad del lenguaje mediante el uso de cuantificadores lingüísticos.

◦ Flexibilizar el acceso a la información.

La resistencia al uso por su costo computacional.

Aplicabilidad en áreas reales.

Desarrollo en el marco de transferencia tecnológica.

Justificación e Importancia


Trabajos Relacionados: SQLf: A Relational Database Language for Fuzzy

Querying. (Bosc, P., & Pivert, O. (1995)).

Interrogaciones Flexibles en Bases de Datos Relacionales. (Tineo, L. (1998)).

Una Contribución a la Interrogación Flexible de Bases de Datos: Evaluación de Consultas Cuantificadas Difusas. (Tineo, L. (2005)).

Reingeniería del Sistema de Consultas Difusas a Bases de Datos SQLfi. (Crespo, V. (2006)).

Antecedentes


Trabajos Relacionados: Una Contribución a la Interrogación Flexible de

Bases de Datos: Optimización y Evaluación a Nivel Físico. (Cadenas, J. (2006)).

PostgreSQLf: Sistema de Consultas Flexibles Fuertemente Acoplado con el SGBD PostgreSQL. (Rossodivita, A.).

PostgreSQLf: Implementación de Extensiones Difusas de manera Fuertemente Acoplada sobre el RDBMS PostgreSQLf. (Bracho, A.).

Antecedentes


Trabajos Relacionados: Implementación de Primitivas SQL para Reglas

de Asociación en una Arquitectura Fuertemente Acoplada.(Timarán, R.(2005)).

RT-PostgreSQL: extensión de PostgreSQL para el manejo de datos con Frecuencias Temporales en base a una Arquitectura Fuertemente Acoplada. (García, L. (2008)).

On Extending PostgreSQL with the Skyline Operator. (Reinhard, P. (2009)).

Antecedentes


Trabajo Elaborado por: Implementación

Una Contribución a la Interrogación Flexible de Bases de Datos:

Optimización y Evaluación a Nivel Físico, Universidad Simón Bolívar,

Diciembre (2006).

José T. Cadenas

Tesis de Maestría

Predicados difusos por trapecio, operador AND.

PostgreSQLf: Sistema de Consultas Flexibles Fuertemente Acoplado con

el SGBD PostgreSQL

Arturo Rossodivita Predicados difusos por Expresión y Extensión, operador OR, modificadores difusos.

PostgreSQLf: Implementación de Extensiones Difusas de manera Fuertemente Acoplada sobre el

RDBMS PostgreSQL,

Armando Bracho Consultas particionadas GROUP BY, HAVING, UPDATE vistas, y operación de unión difusa.

PostgreSQLf: Implementación de Cuantificadores Difusos

Sobre el SGBD PostgreSQL

Gustavo Bazán Consultas con Cuantificación Difusa.

Operaciones conjuntistas, sub consultas difusas y comparadores

difusos para PostgreSQLf

Rodolfo Vegas

Trabajo de investigación y desarrollo

Comparadores, operaciones conjuntistas y sub consultas difusas

en el FROM.

Antecedentes

Basado en el concepto matemático de relación.

Lenguajes de consultas para la manipulación de los datos:◦ Procedimentales como el álgebra

relacional.◦ No procedimentales como el SQL

(Structured Query Language) o lenguaje de consulta estructurado.

Modelo Relacional


Teoría Difusa


4321 ,,, xxxxA

x1 x2 x3 x40

1

Conjuntos difusos Gradualidad de membrecía Función en el intervalo [0,1] Representación Trapezoidal

Booleana: Existe (∃) y Para Todo (∀).

Difusa: “la mayoría de”, “pocos de”, “aproximadamente la mitad de”, “aproximadamente cinco”, “cerca de 3”.

Se clasifican según su interpretación.

Cuantificación Difusa


Por su naturaleza Cuantificador Absoluto o Relativo

Por su Comportamiento Cuantificador Creciente, Decreciente o

Unimodal

Cuantificación Difusa


0 2 4 6 8

0

1

0 0.25 0.5 0.75000000000001

5

1

0

1

0 2 4 6 8

0

1

0 0.25 0.5 0.750000000000015

1

0

1

0 1 2 3 4 5 6 7

0

1

0 0.25 0.5 0.750000000000015

1

0

1

Absolutos Relativos

Creciente

Decreciente

Unimodales

Consultas flexibles sobre Bases de Datos Relacionales.

Basado en la Teoría de Conjuntos Difusos.

CREATE [ABSOLUTE/RELATIVE] QUANTIFIER <nombre> AS <cjto difuso>

SELECT <atributos> FROM <tablas> WHERE <condición difusa>

Cuantificación: Q (fc1, fc2, …, fcn)

SQLf


Reducir el número de filas consultadas por cada operación.

Emplea la relación entre condiciones difusas y booleanas.

Transformaciones lógicas. Conseguir las mismas filas con una

consulta clásica que con una difusa.

El Principio de Derivación


SGDB de Código Abierto

PostgreSQL


Backend de Postgres

PostgreSQL


Metodología

Cascada


Fase de Análisis

El reconocimiento del problema implicó:

◦ Estudio del sistema de consultas flexibles SQLf.

◦ Uso de Cuantificación difusa para SQLf.

◦ Estudio del diseño y estructura de PostgreSQL.

PostgreSQLf


Fase de Diseño Requerimientos:

◦ CREATE [ABSOLUTE/RELATIVE] QUANTIFIER <nombre> AS <conj>

◦ SELECT Att FROM R WHERE Q(fc1, fc2, …, fcn)

PostgreSQLf


Fase de Implementación Catálogo

◦ Almacenamiento de los cuantificadores◦ Tabla del sistema pg_fuzzyquan.◦ Manejo del catalogo.

PostgreSQLf


Fase de Implementación Parser

◦ Nuevos Nodos CreateFuzzyQuanStmt A_FuzzyQuan

◦ Nueva semántica para la creación de cuantificadores difusos (gram.y)

◦ Interceptar una consulta cuantificada Validar exista el cuantificador Generar un árbol de consulta difuso Derivar el árbol difuso a un árbol clásico.

PostgreSQLf



◦ Árbol de consulta Difuso

PostgreSQLf


Select

TablasAtributos Where

Cuantificador Difuso

Predicado difuso Predicado difuso


◦ Consulta difusa

PostgreSQLf


SelectStmt

unionall: falseunique

whereClausefromClause

groupClausehavingClause

targetList

sortClause

ResTarget

val “empleado”attr

Attrrelname

“id_num”

Valueval.str

RangeVarnamerelExpr

“empleado”

A_FuzzyQuan

Predname: al_menos3

Core1: 3

Minfp: 1

Core2: 0

Maxfp: 0

Typefp: 3

Typefq: 1

args

A_FuzzyPred

Predname: alto

Core1: 300

Minfp: 100

Core2: 0

Maxfp: 0

Typefp: 3

Begd: 0

Begd: 300


◦ Derivación de una consulta difusa

PostgreSQLf


tfcDNCWHERERFROMAttSELECT iIilbncombI

ANDOR ,,,

Select

TablasAtributos Where

OR

AND AND

Condición derivada …Condición

derivada


◦ Consulta derivada

PostgreSQLf


BoolExpr

OR

args

OpExpr

Opno…

args

…

BoolExpr

AND

args

BoolExpr

AND

args

OpExpr

Opno…

args

OpExpr

Opno…

args

OpExpr

Opno…

args

Var

…

A_FuzzyPred

…

Var

…

A_FuzzyPred

…

Var

…

A_FuzzyPred

…

Var

…

A_FuzzyPred

…

Fase de Implementación Traffic Cop (Tcop)

◦ Manejo de la expresión simple para crear cuantificadores.

Planner/Optimizer◦ Mantener la información de los valores de cada

cuantificador difuso y sus predicados.

PostgreSQLf


Fase de Implementación Executor

◦ Calculo del grado de membrecía.

PostgreSQLf


Fase de Integración Integrar con el resto de las

funcionalidades de PostgreSQLf

Fase de Pruebas Pruebas de funcionalidad y rendimiento

PostgreSQLf


Pruebas Funcionales Uso de la base de datos lab_marcha, facilitada por el

Laboratorio De Marcha Del Hospital Ortopédico Infantil.

Creación de Cuantificadores Difusos

Pruebas y Resultados


lab_marcha=# CREATE ABSOLUTE QUANTIFIER al_menos3 AS (1.0, 3.0, infinite, infinite);CREATE FUZZY QUANTIFIERlab_marcha=#

lab_marcha=# CREATE RELATIVE QUANTIFIER aprox_la_mitad AS (0.25, 0.5, 0.5, 0.75);CREATE FUZZY QUANTIFIERlab_marcha=#

Pruebas Funcionales Validación del catálogo


lab_marcha=# SELECT * FROM pg_fuzzyquan; quanname | quanminfp | quancore1 | quancore2 | quanmaxfp | quantypefp | quantypefq ----------------+-----------+-----------+-----------+-----------+------------+------------ al_menos3 | 1.0 | 3.0 | 0.0 | 0.0 | 3 | 1 a_lo_sumo_2 | 0.0 | 0.0 | 2.0 | 3.0 | 2 | 1 aprox_5 | 3.0 | 4.0 | 6.0 | 7.0 | 1 | 1 la_mayoria | 0.5 | 0.75 | 1.0 | 1.0 | 3 | 2 la_minoria | 0.0 | 0.0 | 0.25 | 0.5 | 2 | 2 aprox_la_mitad | 0.25 | 0.5 | 0.5 | 0.75 | 1 | 2(6 rows)lab_marcha=#

Pruebas Funcionales Selección de datos

Se desea conocer la edad, talla y peso de los pacientes que cumplan con la mayoría de las siguientes condiciones: ser viejo, alto y gordo.



lab_marcha=# SELECT edad, talla, peso FROM estudio WHERE la_mayoria(edad=viejo, talla=alto, peso=gordo);edad | talla | peso | Gr.Memb. ------+-------+-------+---------- 52 | 1.66 | 85.6 | 0.56 57 | 195.5 | 110.7 | 0.85 57 | 195.5 | 110.2 | 0.85 57 | 195.5 | 109.8 | 0.85 57 | 195.5 | 109.8 | 0.85 57 | 195.5 | 109.6 | 0.85 57 | 195.5 | 110 | 0.85 57 | 195.5 | 110.3 | 0.85 57 | 195.5 | 110.3 | 0.85 57 | 195.5 | 110.1 | 0.85 57 | 195.5 | 110.1 | 0.85 51 | 1.81 | 94 | 0.55(12 rows)lab_marcha=#

Pruebas de Rendimiento Verificar si el uso de cuantificadores afecta el

tiempo de una consulta con respecto a una clásica equivalente.

Herramienta TPC-H. Dos volúmenes de datos (1 y 5 GB). Variación el número de predicados a cuantificar

(2 o 4 predicados). Análisis de Varianza (ANOVA) para varios

factores. 72 pruebas variando los distintos factores.



Pruebas de RendimientoTabla ANOVA



Factor Df Sum Sq Mean Sq F value Pr(>F)

TIPO 2 9377784 4688892 0.3361 0.7159

NUMERO 1 2377027462 2377027462 170.3782 < 2.2e-16 ***

VOLUMEN 1 5101153794 5101153794 365.6354 < 2.2e-16 ***

TIPO:NUMERO 2 244581 122291 0.0088 0.9913

TIPO:VOLUMEN 2 21411603 10705802 0.7674 0.4687

NUMERO:VOLUMEN 1 1568508521 1568508521 112.4260 2.222e-15 ***

TIPO:NUMERO:VOLUMEN 1 3316498 1658249 0.1189 0.8881

Residuals 60 837088575 13951476

Pruebas de Rendimiento


Trabajo Realizado

Implementación de la estrategia del programa derivado para cuantificación difusa sobre el kernel de PostgreSQL.

Nuevas herramientas que faciliten la obtención de información sobre PostgreSQL.

Sencillez para realizar consultas, lenguaje mas natural.

Conclusiones


Aportes

PostgreSQLf, una alternativa para cuantificación basada en lógica difusa.

Una guía de referencia para futuras extensiones sobre PostgreSQL.

Pruebas estadísticas de la mejoras de tiempo al implementar de manera fuertemente acoplada.

Conclusiones


Recomendaciones

Implementación del resto de las características de SQLf sobre PostgreSQLf.

Revisión de la estructura y código final de PostgreSQLf.

Fomentar desarrollos que ayuden a la independencia tecnológica.

Conclusiones


Gracias por su Atención

¿Preguntas?

postgresqlf

Documents