Download - 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
Agenda• Introducción• El Problema• Objetivos• Justificación• Marco Teórico• Metodología• Resultados• Conclusiones
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
Agenda• Introducción• El Problema• Objetivos• Justificación• Marco Teórico• Metodología• Resultados• Conclusiones
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
Agenda• Introducción• El Problema• Objetivos• Justificación• Marco Teórico• Metodología• Resultados• Conclusiones
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
Agenda• Introducción• El Problema• Objetivos• Justificación• Marco Teórico• Metodología• Resultados• Conclusiones
Aplicaciones a nivel de capa lógica resuelven el problema, pero sus costos computacionales son muy elevados.
El Problema
Agenda• Introducción• El Problema• Objetivos• Justificación• Marco Teórico• Metodología• Resultados• Conclusiones
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
Agenda• Introducción• El Problema• Objetivos• Justificación• Marco Teórico• Metodología• Resultados• Conclusiones
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 de la Investigación
Agenda• Introducción• El Problema• Objetivos• Justificación• Marco Teórico• Metodología• Resultados• Conclusiones
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.
Objetivos de la Investigación
Agenda• Introducción• El Problema• Objetivos• Justificación• Marco Teórico• Metodología• Resultados• Conclusiones
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
Agenda• Introducción• El Problema• Objetivos• Justificación• Marco Teórico• Metodología• Resultados• Conclusiones
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
Agenda• Introducción• El Problema• Objetivos• Justificación• Marco Teórico• Metodología• Resultados• Conclusiones
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
Agenda• Introducción• El Problema• Objetivos• Justificación• Marco Teórico• Metodología• Resultados• Conclusiones
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
Agenda• Introducción• El Problema• Objetivos• Justificación• Marco Teórico• Metodología• Resultados• Conclusiones
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
Agenda• Introducción• El Problema• Objetivos• Justificación• Marco Teórico• Metodología• Resultados• Conclusiones
Teoría Difusa
Agenda• Introducción• El Problema• Objetivos• Justificación• Marco Teórico• Metodología• Resultados• Conclusiones
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
Agenda• Introducción• El Problema• Objetivos• Justificación• Marco Teórico• Metodología• Resultados• Conclusiones
Por su naturaleza Cuantificador Absoluto o Relativo
Por su Comportamiento Cuantificador Creciente, Decreciente o
Unimodal
Cuantificación Difusa
Agenda• Introducción• El Problema• Objetivos• Justificación• Marco Teórico• Metodología• Resultados• Conclusiones
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
Agenda• Introducción• El Problema• Objetivos• Justificación• Marco Teórico• Metodología• Resultados• Conclusiones
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
Agenda• Introducción• El Problema• Objetivos• Justificación• Marco Teórico• Metodología• Resultados• Conclusiones
SGDB de Código Abierto
PostgreSQL
Agenda• Introducción• El Problema• Objetivos• Justificación• Marco Teórico• Metodología• Resultados• Conclusiones
Backend de Postgres
PostgreSQL
Agenda• Introducción• El Problema• Objetivos• Justificación• Marco Teórico• Metodología• Resultados• Conclusiones
Metodología
Cascada
Agenda• Introducción• El Problema• Objetivos• Justificación• Marco Teórico• Metodología• Resultados• Conclusiones
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
Agenda• Introducción• El Problema• Objetivos• Justificación• Marco Teórico• Metodología• Resultados• Conclusiones
Fase de Diseño Requerimientos:
◦ CREATE [ABSOLUTE/RELATIVE] QUANTIFIER <nombre> AS <conj>
◦ SELECT Att FROM R WHERE Q(fc1, fc2, …, fcn)
PostgreSQLf
Agenda• Introducción• El Problema• Objetivos• Justificación• Marco Teórico• Metodología• Resultados• Conclusiones
Fase de Implementación Catálogo
◦ Almacenamiento de los cuantificadores◦ Tabla del sistema pg_fuzzyquan.◦ Manejo del catalogo.
PostgreSQLf
Agenda• Introducción• El Problema• Objetivos• Justificación• Marco Teórico• Metodología• Resultados• Conclusiones
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
Agenda• Introducción• El Problema• Objetivos• Justificación• Marco Teórico• Metodología• Resultados• Conclusiones
Fase de Implementación Parser
◦ Árbol de consulta Difuso
PostgreSQLf
Agenda• Introducción• El Problema• Objetivos• Justificación• Marco Teórico• Metodología• Resultados• Conclusiones
Select
TablasAtributos Where
Cuantificador Difuso
Predicado difuso Predicado difuso
Fase de Implementación Parser
◦ Consulta difusa
PostgreSQLf
Agenda• Introducción• El Problema• Objetivos• Justificación• Marco Teórico• Metodología• Resultados• Conclusiones
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
Fase de Implementación Parser
◦ Derivación de una consulta difusa
PostgreSQLf
Agenda• Introducción• El Problema• Objetivos• Justificación• Marco Teórico• Metodología• Resultados• Conclusiones
tfcDNCWHERERFROMAttSELECT iIilbncombI
ANDOR ,,,
Select
TablasAtributos Where
OR
AND AND
Condición derivada …Condición
derivada
Fase de Implementación Parser
◦ Consulta derivada
PostgreSQLf
Agenda• Introducción• El Problema• Objetivos• Justificación• Marco Teórico• Metodología• Resultados• Conclusiones
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
Agenda• Introducción• El Problema• Objetivos• Justificación• Marco Teórico• Metodología• Resultados• Conclusiones
Fase de Implementación Executor
◦ Calculo del grado de membrecía.
PostgreSQLf
Agenda• Introducción• El Problema• Objetivos• Justificación• Marco Teórico• Metodología• Resultados• Conclusiones
Fase de Integración Integrar con el resto de las
funcionalidades de PostgreSQLf
Fase de Pruebas Pruebas de funcionalidad y rendimiento
PostgreSQLf
Agenda• Introducción• El Problema• Objetivos• Justificación• Marco Teórico• Metodología• Resultados• Conclusiones
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
Agenda• Introducción• El Problema• Objetivos• Justificación• Marco Teórico• Metodología• Resultados• Conclusiones
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
Pruebas y Resultados
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.
Pruebas y Resultados
Agenda• Introducción• El Problema• Objetivos• Justificación• Marco Teórico• Metodología• Resultados• Conclusiones
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 y Resultados
Agenda• Introducción• El Problema• Objetivos• Justificación• Marco Teórico• Metodología• Resultados• Conclusiones
Pruebas de RendimientoTabla ANOVA
Pruebas y Resultados
Agenda• Introducción• El Problema• Objetivos• Justificación• Marco Teórico• Metodología• Resultados• Conclusiones
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
Pruebas y Resultados
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
Agenda• Introducción• El Problema• Objetivos• Justificación• Marco Teórico• Metodología• Resultados• 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
Agenda• Introducción• El Problema• Objetivos• Justificación• Marco Teórico• Metodología• Resultados• 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
Agenda• Introducción• El Problema• Objetivos• Justificación• Marco Teórico• Metodología• Resultados• Conclusiones
Gracias por su Atención
¿Preguntas?