PDF de programación - Tesis: Dante Torres - Optimizacion de consultas en bases de datos distribuidas

Fjo 1e-ol
i(_:,._ ·:1 i~

CENTRO DE INVESTIGACIOH Y M
ESTUOIOS ~.VANZI;DOS DEL
B I B L I 0 T E C 'A ·
INGENIERIA ELECTRICA

I.P.N.

CENTRO DE INVESTIGACION Y DE ESTUDIOS
AVANZADOS DEL INSTITUTO POLITECNICO

NACIONAL

DEPARTAMENTO DE INGENIERiA ELECTRICA

SECCION DE COMPUTACION

CIN V ESTAY

lPN

ADOUISI C ION
DE LIBROS

"Optimizacion de consultas en bases de

datos distribuidas "

CENUO OE INVESTIGACJaN Y 1!£

EST U!'HOS AVANB OOS OEL

I. P . N.

BI BL I O T EC A
IN GENIERIA ELECTRICA

TESIS QUE PRESENT A

Lie. Dante Torres Estrada
Para obtener ef grado de MAESTRO EN
de
CIENCIAS
INGENIERiA ELECTRICA con opci6n de
COMPUTACION.

especialidad

en

Ia

DIRECTOR DE TESIS

M. en C. Feliu Sagols Troncoso

MEXICO, D.F.

1996

-

XM

Oplimizacitm de con.mllas en ba~c.~ de datos distribuidas J

Resumen

Se presenta un modelo para procesar consultas en bases de datos distribuidas, el
cual consta de cuatro etapas. En Ia primera, el usuario especifica su consulta en el
Ienguaje de consulta que se encuentre instalado en su nodo y esta se traduce a una
consulta expresada en algebra relacional. En la segunda etapa, se obtiene un
conjunto de expresiones can6nicas a partir de la expresi6n conseguida en la primera
fase . En la tercera etapa, se elige el plan de acceso distribuido 6ptimo a partir de las
expresiones can6nicas y en la cuarta se ejecuta este plan, cuyo prop6sito es entregar
la respuesta al usuario en el nodo donde este se encuentre.

En este trabajo se construyen las herramientas de software que permiten
representar el entomo de distribuci6n y que automatizan las dos primeras etapas del
modelo anterior, con la limitante de que el Ienguaje en el que el usuario plantea sus
consultas es el algebra relacional. El sistema desarrollado permite plantear consultas
en algebra relacional de manera que se produzca un conjunto de expresiones
can6nicas que arrojan el mismo resultado que la primera, pero cuya ejecuci6n puede
ser mas econ6mica. La economia que se obtiene de ejecutar alguna de las
expresiones can6nicas producidas mediante la aplicaci6n de
los metodos de
optimizaci6n expuestos en este trabajo, implican un ahorro en tiempo y recursos.
Este ahorro se produce al eliminar trabajo innecesario o bien de aplicar heuristicas
para reescribir la consulta de una manera mas conveniente.

Palabras y frases para catalogar: bases de datos distribuidas, algebra
relacional , procesamiento de la consulta, l6gica matematica, satisfactibilidad, plan de
acceso distribuido.

Cfi'HI!O DE IHVESTIGACit!N y BE

f'STUOit!S AVANZADOS DEL

I. P. N.

BIBLIOTECA
INGENIERfA ELECTRICA

Resumen

Optimizaci6n de consultas en bases de datos clist.ribuldm;

Dante Tones Estrada

(Revision)

G uillermo i\ loralcs- Luua

I"cbrero de ! 99G

A lo largo rlc Ia presentc critica, me rcferirC a Ia Las f orm as co11j1mtivns so n co njmwiorH"s d1· pn·dit"a -
pUgina n del t.cxt.o como pcig. n.

dos mixtos disy untivos,

1 Opinion general

PrcscntarC aqui algunas o piniones gener a les sohrc cl
texto.

I. Dcsde el ptmto de vista de analisis creo que es
nm y iutcresa ntc cl tratami ento que hace el autor a las
co nsultas para dccid ir previam ente su satisfactibili
dad. En res umen:

Sea A = {A 1 ,
, A N} un esquema rclacional. Gn Ia
hasc de datos hay conjuntos de objetos 0, de uaT'iables
V, de funcion es :F y de comparo dores, aqui C = {:~}.
Las cxpresiones sc forman como siguc:

o E 0
x E V
AEA
!E:F,e , , .. ,ekEExp

En otras palabras,

o E Exp
x E Exp
AEExp
f (e,, .

. ,ek)EExp

(Exp)

(O) I(V) I(A) I
(:F)(Exp) '

Los citomos so n de Ia forma

(Atom):: = (A)(C)(E.,p) I (Exp)(C)(A).

Los Jn-edicodos miJ:t.os conjuntivos son conjunciones
de atomos,

(PM(,): := ( A/ om) I ( At om) 1\ (I'M(.)

Los pn-dicnrlos mixtos disyuntivos so n d isy unciOJws
d( ! {d.O ill OS,

(I'M/J) :·

(,1/om) I (Atom) V (PM/J)

( l'r:) :: = (l'i\IU) I (/'i\1/))/\(H)

Las Jonrws disyuTltivns son di:;;y uncioJu•s dP pn ·dil'a
dos mixtos co njuntivos,

(I'D):: = (!'A/C) I (f'Mr.) v (1-"JJ)

Las f Ormulas so n dC' Ia fonua

(Form)

( Atom)l

~((Form))l
((Form) 1\ (l:'" ·m))l
((Form) V (Form))

Toda fOrmula se t.ra ns fo rm a. digatuos qur nH ·di anl l'
e l a lgoritmo d e \\'ang. a un a for111a conjuntin1 f'qlli\'
alcnt.e. E n particular. si Ia fc) n unla f11C'ra una tan
tologia e nt onccs Ia fonna co njnnli\'a Pf!lli\';tkntP f's
vacia. As!, si Ia n<'gaci6n de una
r~·>nnnla t il'lll'
una forma conjunliva Pq ni vu l<'nf<> vacla Plllonr·(•s Ia
fOrmula dada cs inconsistf'nL<'

AI ap li car c l algor it m ode \Va11 ~ a Ia n q~al'itl u dt· 1111:1
fOrmula se ohticne propiam£' 111<• Ia fon na
de Ia fOrmula dada. La fOrmula SC'r<l ills.< I islr,wti l >l<•
si cada uno de los prcdicado~ mi xtos
aparecen en Ia forma di sy ltnt.i\·a <·~

E l algoritlllO dP no~C' llkranlz· llll lll
cni111do un pr(•d kad o mix to conjunt i\·o
facti hiP.

JH 'rlll ilt' dt•l'idiJ
ins at is

t•s

f'll Ia ha~c d f' datos !-'t' fo r nnll a c·o1no

l !na !i€lerr:irin
"(!/) = {x l <~(x) 1\ /l(x)}. Asi qno
lr<~IISfonn<~ Ia ft.JI'lllllla 'i' (x) a llll:t
st• t•lin1i11a a lo:-; pn•di cado :-; Jnixtoo.;
tis foll'tihlt•s.

nl~> rJ f •·. S•'.fJ'irJ if1S l ••y• '$ d,.f ti!g, .f,, ., ,-. ·J,rr·ionfll. '11
d q rt l! los o p~>_ rn dm·,•.<; 1u11u·i,.'> _..,, 111'lin111 "1',-j,,,.,._
am~r~ l l! ".

Las tr a n s fnn u ac io rws a dnli s ihl <•s sc> prt•st•JI I an «' II
Ia SN.'ci6n ·I. I d('l lra hajo . S< ' JHH •dc • VP rif it"a r <[ ll<'
i-st as so n <·o rr<'c. Las.
Es imp ort a ntf' a qni f' nfat izar Ia c•st ra l Pgi a d P
"dcri\'ac i6 n'' qn<> 5(' r ca li za )Hl('S. c·o n1 o lo a pn nt a
('X is tc un a gr a n ca nt. itlad d(• ;"tr!lCI I<·s
el a ut o r ~
e<tlliYalcnt es a l d a d o.

4. R l!rl ucci6n el tirbo l obl~11ido mr·diaTtfP r•L lt.'>o d ··

, -e l nriorlPS 1·rs t ri11gid n.s.

:\111Hj1 H' JH I H'<"C II n a t.nr a lc•s las t. ra n ~ fonJJa ci ol l f 'S
realizad a<; po r cl au to r cn •o qtl<' aqni c•s iltq HJ r
ta nle prf's('nta r ex plic-il a nwnt f' los c-ri krios d 1•
"minim alidad'' S<'guidos por <' I aut o r

.). P roc'!rhr recw·sivnmenl~ ~11

Lo

1.,.,J11 r·r·iriTI

tf,.

s ubexpn?s iones.

3 Recomendacion

1. Te ner en cttc nta Ill is ohs(•rvacio nf's g('rH'ralc ·s
una ult erior presf'nt aci6 n t(~<.·n i<.:a dc·l l.ra hajo.
que scria intncsantc prC' pa r nr till JH'<j llt"I-Jo d 'H" 111 l ll'lll o
en in g iCs y CIIYi arlo n mm rc•mJi<)n d e• " \·c·ry h rr:c·
d a tabases' 0 "para llel and dis trihlll('d rLd : d>asr·.s''

Cuili<·n no J\ lora k s- l,n na

Es tn t.ra nsfonnn ci6n p ermit <> localiza r pr('c: isa!ll('flt('
a los frn g nwnt.os d e infonn aci6 n que participa n ncti
vnnw ntc en Ia soluci6n de Ia cons ulta. Se disminuyc
asi cl nlmwro d e accesos en una base de dat os dis
t. ribuid a.

2.
Lns hcurfs t.icas o cstra t.('g ius que ut ili za cl a n
to r pa r a r <'dncir un n consulta a una consult-a min i
m al cqui val('nt c pa reccn nmy e fccti vos y ad-hoc pa ra
esqucm ns dis trihuidos .

fg ualm cnt.<\ Ia implc mcnt.aci6 n p arcce ad ccuad a
3.
y de much a nt.ilidad po tencia l pa ra programado res de
bases rlc d a tos.

J\·1e lmhria gus t.a do que sc tra ta ra co n mayo r d <"
tf .
tall c Ia influE'JKia que t.e nd ria en Ia d is tribuciO n risica
d e Ia b ase d e d atos Ia norma lizaci6n de Ia ba'ie (' ll
tcn·cras form as o en fo rmas d e 13oyce-Co rld.

El a u tor sc ce nt ra tn\lcho, lo cua l no cs d ctn eritorio
rlc uin gu na form a, en el proccsarniento d e cons ult as:
Dccidi r su sat. isfactil>ilid ad , s u t.raducciOn a p redica
d os mi x t.os, y, Ia traducci On Op tim a de los prcdicados
sa tisfactibl<'s.

Estos pro ccsos corrcsp ondcn ya a Ia et a pa de "ex-
plot ac i6 n'' de Ia base de d a tos y no ta nt o a la ctapa
de di scl10 de Ia b ase.

2 Detalles particulares

2.1 Acot a ciones al texto

Aq ui m e r efl cro a a lgunos dc t a llcs en el texto.

Sie nto que cl primer capit ulo (pa g .

1.
1-pil.g.
38 ) cs d C'm asiad o ex t ens o. P ara fin es de Ia t.eAc; is cs
adec uad a Ia prcscntaciO n. P ar a tm rep orte ul terior
rec.o m <'nd aria s in te ti zar est.c ca pit ulo en una ulntro
ducci6n".

2. Cons idero que Ia 1·epres entaci6n de j lujo de dntos
cs hucn a y asi vicne a scr un a de las princi pal cs con
tril>ucio ncs del tra ba jo.

3. E l proccso d e optim.izaci6n que present a el a u to r
es cJ s iguicnt.c (en esta crf t ica yo s intct izo a lgunos
" procesos" d el a uto r en uno solo ):

] . 1111nliz.111· llrir:a !I .<;in t rirt.irrn rtf'71 / e U11fl rrmsu l tn

glolwl.

2. T m11.-.j onnnr d drbol s i nlrirtico r1 WI rirJ,,, / d r: ''1'-

j1_ mi ~adre,
~iPadre
ry mis liermanas

;Igraaecimientos

Agradezco y felicito a los profesores de Ia Secci6n de Computaci6n del
Departamento de lngenieria Electrica del CJNVESTAV, porIa hermosa labor que
desarrollan (docencia e
investigaci6n). En particular deseo expresar mi
agradecimiento, por sus contribuciones en este trabajo de tesis, a las siguientes
personas: Dr. Sergio V. Chap