FITXERS I BASES DE DADES TEMA 1.− COMPLEMENTS A FITXERS TEMA 1.− COMPLEMENTS A FITXERS Evolució dels fitxers Primer els fitxers els imaginavem com N registres on cada registre contenia M camps tot de longitud fixe. Camp1 Camp2 ...

...

Registre1 R2 R3 ... Després podriem imaginar un fitxer amb registres de mida variable Camp1 Camp2 R1 R2 R3 ... En aquest cas no sabem la longitud del camp dos, per tant no sabem quants bytes hem de llegir en aquest camp. Ara llegir un registre sencer es mescomplicat ja que no sabem quan ocupen els registres anteriors i per tant no sabem on comença el registre desitjat. Una tercera visió d'un fitxer es mitjançant buckets i dins d'aquests buckets trobem els registres. Aquests buckets són de longitud fixe però encara no sabem on comença i finalitza un registre longitud fixe Bucket1 R1 B2 R3 R4 B3 R6 R7 ..

R2 R8

R5 R9

En les base de dades s'utilitzen grans buckets anomenats pages. Camps Els camps responen al que s'anomenen atributs. El que ens interesa dels camps és la seva longitud que es mesura en el nombre de bytes. Els camps es classifiquen segons la longitud: • Longitud fixa: totes les instancies tenen la mateixa longitud • Longitud variable: instancies amb diferents longituds (per exemple un cap NOM)

1

La longitud dels camps pot ser de dos tipus: • Implicita: la longitud del camp ve determinada pel llenguatge de programació, compilador i la plataforma . Ex: PASCAL VAX integer ! 4 bytes. • Explicita: depen del programador. Ex: COBOL ! permet decidir el que ocupa un tipus. SQL tipus number (precissió, escala) precissió: indica el nombre total de xifres. escala: indica el nombre de decimals. NOTA: number (3,1) ! 2 bytes NOTA: integer ! 4 bytes Registres Un registre és de longitud fixa si te sempre el mateix nombre de camps i tots ells son de longitud fixa. Algunes de les causes de que un registre sigui de longitud variables podrien ser les següents: • Existeix algun camp de longitud variable. • Existeix algun camp que pot tenir valors NULL's (camps que poden ser presents o no). • Existeix algun camp multivalor (camps amb un nombre de variables d'instancies). Implementacions Les següents implementacions venen a implementar fitxers amb registres de longitud variables. • Ocupar sempre el màxim de la longitud real. L'avantatge fundamental d'aquesta implementació es que es facil d'implementar, però pel contrari es perd espai i per tant es perd eficiencia. 100 bytes 100 200 bytes 200 bytes ! 200 200 bytes 50 bytes 50 200 bytes 75 btes 75 200 bytes Exemple: 10 milions de registres amb un camp de 100 bytes d'observacions on el 99% de les vegades esta buit. Utilitzem un disc IBM 3380 amb blocs de 2400 bytes amb un temps de lectura seqüèncial d'un bloc de 1 ms, i amb un temps de lectura random (acces directe) d'un bloc de 25 ms. Quan triguem en llegir tot el fitxer? 10M+ 10 bytes = 1Giga d'observacions basura 1G/2400 = 400.000 blocs. Lectura seq: 400.000 ms ! 6 min Blocs de 512 ! 24 min Lectura random: 400.000 · 25 ms ! 3 hores 2

Blocs de 512 ! 12 hores • Gastar una longitud fixa promig mes zones d'overflow. S'utilitza punters per saber on es troba la zona variable per cada registre. Els punters tenen un accés random per tant hem de saber quina longitud fixa posar, per no tenir massa punters. Aquests punters son a disc i no a memòria central per tant si calculem bé el promig hem de fer molts accessos. • Descriptors: afegim a cada registre un descriptor de la informació que conté. El descriptor hauria de ser de longitud fixa. El descriptor ens diria la longitud del registre, la longitud de cada camp, etc. Al ser, el descriptor, de longitud fixa sabem on comença i on acaba el descriptor i al tenir el descriptor gastem l'espai necessari per cada registre. Ara l'accés seqüèncial es simplifica però per realitzar un acces directe hauriem d'accedir directament al descriptor i per fer aixó, el descriptor hauria d'apuntar al resgitre i no estar continus. Els diferents tipus de descriptors són els seguents: · Prefix Descriptor LR Lc1 Lc2 Lc3 Registre 1 Registre 2 Registre 3 · Infix: es com s'implementa habitualment la majoria dels SGBD dels fitxers de longitud variable. LR Dc1 C1

Dc2 C2

· Separadors: s'utilitzen en les cintes degut als type mark (marques fisques de les cintes). LR C1

C2 type mark

C3

Els inconvenients dels descriptors són que gasten espai pel descriptor i que no podem fer accesos totalment directes. En canvi l'avantatge es que qualsevol camp ocuparà l'espai que necessita. • Buckets/pàgina: tenim els busckets de longitud fixa i dins trobem els registres. Per l'acces seqüèncial va molt bé, però no sabem encara on comença cada registre dins del bucket. Per solucionar això tenim un descriptor de bucket que indica el nombre de registres que te el bucket i a més els descriptors de cada registre. R1

R3

R4 DB DR1R1

Disseny dels primers buckets

Disseny dels buckets amd descriptors

Blocs El que es passa de disc a memòria es un bloc (unitat mínima de transferencia, i el factor de bloqueig és el número de registres per bloc. Dins de cada bloc poden haver un o més registres. Els consideravem de longitud fixa, però de fet poden ser de longitud variable i molt grans. En bases de dades (B.D.), tipicament, els blocs són de longitud fixa, per qualsevol que sigui la relació/tupla entre disc i memòria central. Els tamanys típics dels blocs son: 2K, 4K, 8K.

3

En B.D. el concepte de bloc coincideix amb el concepte de bucket(pagina), en canvi en els fitxers no necessariament ha de coincidir. En fitxers els blocs són de longitud fxa, però els blocs poden ser de diferent longitud segons el fitxer que utilitzem, es a dir, els blocs són de longitud fixa per un fitxer determinat. Ara el bloc es diferent al bucket, de fet un bucket de fitxer pot ser de qualsevol longitud, però el bloc sempre serà un multiple de 512 bytes. En un bloc de fitxers pot ser que no hi cabi un registre complet, llavors hi ha dos possibilitats: • No spanned o deixar basura: en aquest cas el següent registre comença en el següent bloc. • Spanned o començar el registre: en aquest cas comencem un registre encara que no hi cabi en el bloc actual, si es així continua en el següent bloc. D'aquesta forma aprofitem més el disc, però per accedir al registre que es troba entre els blocs haurem de fer dos accesos i en l'altra cas només en necessitavem un acces. Aquesta estructura penalitza l'accés random (puntual) però afavoreix la lectura seqüèncial. En B.D. no es poden dividir els registres entre els diferents buckets, si hi ha algun registre que ocupa més d'un bucket, aquesta informació es guarda en pagines molt mes grans que un bucket. Fitxers: tipus, Index, operacions Tipus Des d'un punt de vista funcional els fitxers es classifiquen en: • Permanents. • De moviments: recull les actualitzacions en un cert periode. • De maniobra: fitxers de suport per fer cadenes entre programes, fitxers de treball entre programes. Els fitxers permanents poden ser: • Historics: fitxers de vida llarga i que no s'actualitzen. Així poden reflexar la situació del passat. S'utilitzen per fer consultes de caire estadistic. • Mestres: aquest fitxers mestres formen el nucli del sistema d'informació, reflexen l'estat d'una organització en un cert moment. Els fitxers mestres es poden actualitzar de dues formes: · On line: actualització i validació es fan al mateix moment que es fa el moviment. · Batch o diferida: actualització i validació es fa de forma diferida en el temps. Hi ha dos maneres de fer efectives aquestes actualitzacions segons com fem el recorregut del fitxer, de forma directe o de forma seqüèncial. (algorisme de Feijen−Dwyer) En la forma directa agafem el registre del moviment i fem una actualització directa al fitxer mestre, al registre que ens indica el fitxer de moviment. En la forma seqüèncial no fem accesos directes per cada registre del fitxer de moviments, sino que es va llegint seqüèncialment tots dos fitxers i al final tenim un fitxer mestre nou. Es pot fer en batch perque:

4

−no es pot fer on−lne −no es vol fer (cas de les targetes VISA) • De constant: fitxers de vida llarga que s'actualitzen poc (assignatures FIB). Index Hi han dos tipus d'indexos: index de volatilitat i index d'activitat. Index d'activitat

Index de volatilitat Per una certa unitat de temps:

Per una certa unitat de temps

IA=

IV= Mesuren la manera de creixer i decreixer del fitxer. Mesura el grau d'utilitació dels registres.

Exemples:

Exemples:

·Volatilitat Alta:

·Activitat Alta

Empleats actius d'una empresa de treball temporal.

Cataleg de la B.D

·Volatiltat Baixa

·Activitat Baixa

Cataleg de BD

Fitxer de CCC de nens

·Volatilitat 0 Fitxer historic.

IV! IA! ! El fitxer ha de primar, necessariament les consultes. Aquest fitxer podria estar en una zona de disc on no augmenti (no es fragmentarà), i no cal preveure un creixement, per tant podem utilitzar estructures estàtiques. No cal fer backup frquentment. Operacions Les operacions poden ser a nivell de camp, de registre, de fitxer o a nivell de N fitxers. • A nivell camp: alta, baixa, modificació. • A nivell de registre: alta, baixa, modificació. • A nivell de fitxer: crear, esborrar, ordenar, distribuir, Sort. Sort: es tracta de fer una ordenació d'un fitxer per camps, aquest fitxer normalment no es podrà posar a memoria central. Portem a memoria una porció, l'ordenenm i escribim en un fitxers. Quan tenim els N fitxers corresponents a les porcions es fa una fusió de fitxers.

5

L'ordenació es farà usant un criteri lexicografic. • A nivell de N fitxers: fusionar. TEMA 2.− ACCES PER POSICIÓ Implementació general de fitxers seqüèncials i relatius Visió lògica Fitxer seqüèncial: tenim un acces seqüèncial per posició. Fitxer relatiu: també te la possibilitat de l'acces seqüèncial per posició i a més permet accedir a una posició concreta sense haver de passar pels registres que hi ha abans del registre que desitgem. En aquests fitxers hi ha la possibiltat de que vinguin accesos directes a zones de memòria fora del nostre rang. Visió Física Fitxers seqüèncials Per sota d'aquests fitxers hi ha d'haver una estructura de dades que tenen el concepte de consecutivitat o seqüència dels registres. Aquesta consecutiitat es pot veure a diferents nivells: • Espai fisic: es a dir, el propi medi obliga a la consulta seqüèncial. Per exemple una cinta. • Estructra de dades consecutives en el temps: un exemple d'aquest cas és el disc. Hi ha dues maneres d'implementar aquesta forma: · Utilitzar el mateix cilindre d'un disc, o en el mateix pla. Amb aquest mètode el problema que ens apareix es que quan en el tros de cilindre dedicat al fitxer s'esgota, es a dir, que passa el límit amb les actualitzacions. L'uúnica possibiltat per aquest problema es treure el fitxer del cilindre i posar−lo en un altre cilindre per conservar la consecutvitat en el temps. per tant aquesta opció va be si el fitxer no creix, ja que per realitzar les consultes es molt eficient. · Interliving factor: factor que ens diu quans sectors es saltan mentre es tracta un sector. Això només es efectiu per un programa, amb un únic usuari i un sol sistema operatiu, però en canvi es molt bo per sistemes en temps real. • Estructures de dades consecutives lògiques: existeixen dues solucions. · A traves d'encadenaments físics (links): el problema de les actualitzacions del cas anterior desapareix (només cal demanar memòria secundaria), però en canvi empitjora l'eficiencia de les consultes (entre els sectors hi ha un link/punter i podria ser que el següent sector estigues en un altre cilindre i er tant s'hauria de moure el capçal). · Tenir una taula de sectors dels fitxers. La taula ens indica on es troba cada sector. En aquestc as tampoc hi ha el problema de les actualitzacions però tampoc milloren les consultes. Normalment s'utilitza una combinació del primer cas (utiltzar un mateix cilindre) i alguna de les altres. Es a dir, li donem un espai determinat al fitxer i quan les expansions necessiten més espai, es fa un link o una taula de sectors a un altre espai (es a dir, es fa un extend, del quales pot determinar la qunatitat d'espai de cada extend).

6

Fitxer relatiu De les implementacions anteriors només son possibles, la de les estructures de dades consecutves en el temps i la taula e sectors, les altres implementacions no permeten l'acces directe a un sector o registre del fitxer. Amb aquests fitxers podem accedir a una posició que encara no estigui declarada, per això hi ha dues solucions. • Fitxers relatius limitats: per crear un fitxer d'aquest tipus necessitem saber el nombre total (màxim) de posicions, per tant, no es pot llegir ni escriure en alguna posició més gran que el màxim declarat. inicialment l'espai es L*max on L es la longitud d'un sector o registre. aquest espai pot ser consecutiu i en el mateix cilindre per tant tenim una gran eficiencia alhora de les consultes. Si el màxim es tria molt gran podenm desaprofitar molt d'espai i si es petit ens podem quedar curts. • Fitxers relatius no limitats: en quest cas no tenim el concepte de màxim, llavors inicialment es creen les posicions necesaries (en posicions consecutives del mateix cilindre) per les dades. Si es vol escriure en un aposició nova es van fer extends i es van inicialitzant els blocs com verges fins arribar a la posició que l'usuari ha demant (els registres entre l'últim sector del fitxer i la nova posició demanada es reserven i per tant no poden ser aprofitats per d'altres fitxers). Buckets Un bucket és allò que es adreçable en un fitxer relatiu. A partir d¡ara un fitxer relatiu serà per a nosaltres una seqüència de buckets. Les caracteristiques dels buckets són: • Sempre de longitud fixe. • 1 bucket pot contenir 1 registre o més registres (longitud variable). Per tant un bucket no te per que ser el mateix que un registre. • En fitxers mestres i de moviments un bucket nome contindrà un registre. Les possibles causes per a que un bucket no sigui un registre són: • Quan parlem de hashing : 1 bucket seran n registres (sinonims). • En el cas d'indexos: 1 bucket seran n registres (nodes). • En base de dades: 1 bucket seran n registres de diverses relacions. Implementació al VAX CLASSE Buffer de memòria central BN = Bucket bN = Bloc (unitat minima de trasnferencia de mem a disc) Sector

VAX Buffer Cell Bucket [1..64 sectors] block

L'implementació dels fitxers es dierent segons el tipus d'acces. Fitxer Relatiu Aquests fitxers no estan limitats, amb increments dinàmics de 3 sectors, i són no spanned.

7

Hi ha dierents cassos: BN " 512 bytes Prenem com a exemple buckets de 152 bytes. ! Tenim que els buckets per sector = buckets

Capçalera Sector1

152 152 B1 B2 Sector 2

152 B3

56

152 152 B4 B5 Sector 3

152 B6

56

Quan demanem l'espai ens donen tots l'espai dels 3 sectors, ja que preformateja tot aquest espai i per tant es reserva encara que no s'utilitzi. Tenim 56 bytes de basura per sector. ! El bucket n es troba al sector:

! En aquest cas es diu que el Bucket_Size = 1. Es a dir que el bucket nostre equival a un bucket del vax de 512 bytes. Per reduir l'espai basura hauria d'augmentar la longitud del bucket o reduir els buckets per sector. Per tant hem d'aconseguir que 512 sigui un multiple de la longitud dels buckets. =512 ! L'increment dinamic dels VAX es de 3 sectors per tant si afegim nomes el bucket 7 ens reservarem tres sectors mes, encara que amb un de sol tindriem suficient. BN > 512 bytes Prenem com a exemple buckets de 600 bytes. Capçalera Sector 1 B2 Sector 4 B3 Sector 7

B1 Sector2 B2 Sector5 reservat Sector 8

B1 Sector3 B3 Sector 6 reservat Sector 9

! En aquest cas tenim un Bucket_size = =2

8

I que un BN = 2 bv = 2 sectors, i per tant la unitat minima de transferencia seran dos sectors. El Bucket_size màxim es de 64 sectors. ! En interessa que la longitud del bucket estigui aprop d'un multiple de 512. long= ! Per localtzar el sector on comença un bucket hem d'utilitzar la següent formula: primer sector 1+ (n−1) · bucket_size

+1 últim sector +bucket_size

Fitxers seqüèncial Els fitxers seqüèncials són spanned, donen 3 sectors de memòria cada vegada que volem més memòria. En aquest cas no es preformateja l'espai i per tant gastem l'espai necessari (1/3). Us de fitxers relatius Els fitxers relatius s'utilitzen per implementar el fitxers d'acces per valor. Utilitzem els fitxers relatius per: • Implementar indexos per l'acces per valor, ja estiguin implementats amb arbres (cada node de l'arbre tindrà N valors i apuntadors als següents nodes. Cada node s'implementa en un bucket d'un fitxer relatiu i els apuntadors als nodes seran apuntadors a d'altres buckets) o amb una taula de hashing (amb una sola lectura recuperem tots els sinònims, busquem el valors que volem i ens posicionem al valors desitjat amb un altre acces, en la taula de hashing cada bucket contindrà tots els sinònims). • Implementar Dades: Per fitxers mestres/moviments un bucket es correspondrà amb un registre del fitxer mestre. Cada bucket contindrà un registre de dades. Accedim per posició per part l'index, al afegir un registre, s'afegeix a la posició n+1, es a dir, s'afegeixen per ordre d'arribada, i lanova adreça s'afegeix a l'index. Al de dades no hi ha cap ordre, per tant es fan expansions del fitxers quan s'inserten nous registres. • Implementar Base de dades: ara els buckets contindran n registres enlloc d'un de sol • Implementar encadenaments: els encadenaments s'implementen en un fitxer relatiu perque un eadenament a disc és un accés per posició. • Implementar dades hashing: aquesta implementació realitza el hashing directament sobre les dades. Això no s''tilitza, ja que els buckets contenen propiament els registres i per tant en un bucket no hi cabrien tots els sinònims i haurien de ser molt grans. Aquest sistema no és flexible alhora decrear nous indexos, ja que segons l'index un registre estar en una posició, i segons un altre index el mateix registre estaria en una altra posició. TEMA 3.− ACCES PER VALOR En un fitxer per valor tenim les dades (n registres) i volem localitzar un registre que te un valor determinat. Per implementar aquest acces es pot fer de dierents formes: • En seqüència s'anava recorrent fins trobar el valor (cost N), si el fitxer està ordenat el temps es redueix a N/2. Nosaltres només hauriem d'implementar el fitxer seqüèncial i axiò és molt costos. 9

• En taula suposavem els elements ordenats i la cerca utilitzada era la dicotomica amb cost log2N, per nosaltres una taula s'implementaria amb un fitxer relatiu (accés per posició al igual que la taula). Implementació particular sobre fitxers relatus ordenats Ordre físic En la implementació de la taula suposem un ordre físic, per tant ara les insercions es fan de forma ordenada, es a dir, que s'han de moure els registres majors que el nou registre per posar el registre al fitxer i que aquest continui ordenat. Existeixen diferents metodes per cerca un element en aquestess estructures de dades: • Cerca dicotomica: en aquesta cerca el punt de tall és elmig del fitxer, i és un metode estable ja queel cost mig i el màxim s'assemblen molt. Cost mig Cost màxim log2N ølog2Nø+1 • Interpolació lineal: en aquest metode el punt de tall es proporcional al que busquem. Per poder implementar això s'ha de cumplir l'hipotesis de tenir una distribució uniforme de valors (el nombre de registres per un element és el mateix que per als altres. Per poder reduir el temps màxim d'acces es poden utilitzar taules de proporcionalitat, aquestes taules s'han d'anar mantenint. Hi hauria una taula de proporcionalitat per cada clau. Cost mig Cost màxim log2(log2N) N • Mixte: és una combinació dels mètodes anteriors. Cost mig Cost màxim 2·log2(log2N) 2·log2N Ordre Lògic Per implementar l'ordre lògic necessitem una llista encadenada, en aquest cas l'inserció es més fàcil ja que només s'han d'actualitzar els punters. No es pot realtzar cerca dicotomica i per tant s'ha de fer la cerca seqüèncial. En aquesta llista tenim dos punters: un paunta al següent registre i l'altre es salta m registres. Es fan recorreguts per la cadena de salts grans i quan ens passem tornem enrera i recorrem la cadena de salts petits. Exemple:

N=100.000 mig max Dicotomica 16 17 I.L. 4 lineal Mixte 8 32 Ordre lògic 316 632

N=4.000 milions mig max 32 33 5 lineal 10 64 63245 126490

Conceptes Previs Fitxer per valor

10

• Dades amb hashing Dades F(v) ! Temps mig per localitzar un registres es de 1,2 a 1,4 accessos a disc • Index amb hashing Index F(v) !

Dades

V@

Cost : 1,2 a 1,4 + 1 En aquest cas no tenim ordre de dades (ni físic ni lògic) • Index amb arbre B. Fitxer seqüèncial per valor • Index amb arbre B+: les fulles tenen un encadenament i per tant no hem d'anar a l'arrel de l'arbre per fer un recoregut seqüèncial. Exemple: Ent. nodes 20 100 200 300

D\nº reg 10 50 100 150

1000 3 2 2 2

10000 4 3 2 2

100000 5 3 3 3

1M 6 4 3 3

10 M 7 4 4 4

L'ordre bo es entre 50 i 100. Si l'arel de l'arbre fos a memòria el nombre d'accesos es reduiria en una unitat. Exemple: En una BD 1 bucket equival a 1 blo de longitud fixa (2K, 4k, 8K) Tenim un ordre (d) de 50, els valors ocupen 6 bytes i els punters 4 bytes. Nodes 2d entrades (V | @) i 2d+1 apuntadors. 100 entrades * 10 bytes 101 apuntadors * 4 bytes

1000 bytes 404 bytes 1404 bytes

Si el valor ocupés 26 bytes (camp texte) tindirem 3400 bytes

11

A partir del tamany del bucket y del valor es defineix l'ordre d. En fitxers de blocs de longitud variables y on el bucket es diferent d'un bloc, a partir de l'ordre i el valor obtenim el valor del bucket. Indexos Index total: hi ha una entrada de l'index per a cada valor del fitxer de dades Index cluster: es un index total però amb les dades ordenades fisicament pel camp Ci. En aquest cas tenim el problema de les actualitzacions ja que les dades han d'estar ordenades, però el que es fa es que cada cert temps es va ordenant el fitxer per no haver d'ordenar el fitxer en cada inserció. Nomes pot haver un unic index cluster sobre un fitxer (ja que tenim un ordre físic de les dades). En la consulta puntual no es guanya eficiencia, en canvi en la consulta seqüèncial si que es guanya, també es guanya amb les consultes puntuals amb duplicats. Multindex: index sobre un fitxer de dades on tenim N indexos, un per cada camp. Index multicamp: index definit per diversos camps. Només poden aprofitxer l'index multicamp per fer accesos eficients sobre un dels camps. També es poden fer accesos pels camps que composen l'index. En fitxers no acostuma ha haver−hi index multicamp, però en canvi, en base de dades es bastant clàssic trobar−ne (una clau primaria composta per dos camps C1 i C2). La manera més simple de declarar indexs multicamps és mitjançant els index unidimensionals que consideren els dos camps com un de sol composat per la concatenació dels dos camps. Així la inserció, consulta, etc. continuan sent iguals. Les consultes puntuals i seqüèncials per les dues claus segueix sent igual, però ¿es pot aprofitar l'index per realitzar consultes per un dels camps?. Si que es pot aprofitar. Per una consulta pel camp C1 seria com una consulta generica, però amb petites diferencies, ja que s'ha d'explorar un conjunt de branques de l'arbre i no només una branca com abans. Per una consulta pel camp C2, també s'aprofita però s'haura de recorrer tot l'arbre i no només una part com pel camp C1. Per no haver de recorrer tot l'arbre podriem definir un altre idex pel camp C2 però seria estúpid definir un altre index pel camp C1. Index multidimensional: amb aquests indexs no prioritzem cap clau, al contrari dels unidimensionals. En el cas de dos claus (binari) se li diu Quad−Tree (dividim l'espai en 4 trossos enlloc de en dos). Per resoldre consultes també podriem posar el valor d'un camp a l'index i d'questa fora ens enstalviem un acces (normalment seràn valors de camps que es consulten habitualment. Implementació general Per realitzar l'implementació podem escollir entre dos métodes: hashing i arbres (aquesta s'explica a problemes). Hashing Estàtic Existeixen dos tipus de realitzar hashing: de forma estàtica i dinàmica. En l'implementació hashing tenim un camp V sobre el qual volem consultar, els valors possibles son molts, però al fitxer tindrem menys elemnts. Per tant s'aplica una funció de hash al camp i la funció ens diu la posició on es troba l'element desitjat. Si els alors dels camps son diferents i la funció de hash dona el mateix valor, llavors diem que els valors són 12

sinònims. De la funció de hash s'espera que faci una distribució uniforme. Per nosaltres cada acces mitjançant un punter, es convertirà en un acces random a disc i per tant nosaltres no utiltzarem un hashing d'aquesta forma sino una variant. En la variant la funció de hash retornarà l'adreça d'un bucket. Dintre de cada bucket tenim les entrades valor, adreça que hem vist fins ara. Dintre d'un bucket trobariem tots els sinònims d'aquella posició. en aquest cas potser que un bucket s'ompli i no hi hagi espai per tots els sinònims, en aquest cas parlem excedents (sinònim que no hi cap), per tant hem de mirar que fer amb aquests excedents: • La funció de hash dimensiona la zona principal, i quan hi ha algun excedent, aquest es coloca en una altra zona (zona d'excedents). • La funció de hash dimensiona la zona principal i els excedents es col.loquen en un altre bucket dins de la zona principal. Els buckets excedents se'ls anomena intrus(sinonims que ocupen posicions que o li pertoquen). Terminologia N = nombre de buckets. L = nombre de registres per bucket (bucketsize). R = N * L = nombre total de registres en ZP. M = nombre màxim de registres a guardar. C = M / R = factor de càrrega. Si no hi ha ZE i només hi ha ZP llavors: 0 " C " 1 Si hi ha ZE llavors: C > 1 Decisions de disseny Problemes Sinònims

Solucions definir bucket

Excedents

gestió d'excedents

Funció de hash diferents Tamany del fitxer N fixa N ha de ser fxa

Decissió Disseny L? Open Adresing Chaining Modul quina N? Extendible Hash

hashing dinàmic Linear Hash

Funció de hash • Decidir el valor de N i L en funció de M i C. ! Hipotesi sobre el valor de M: cas màxim, cas en que hi hauria mes registres a guardar.

13

! Decidi C, per decidir el valor hem de mrar quina gestió d'execedents es fa: · Open adressing: C=0,7 · Chaining: C=0,9 Si C! : llavors tenim molt espai desaprofitat !, l'eficiencia augmenta ! ja que haurà menys excedents i així no huriem de sortir del bucket per trobar un determinat registre. Si C! : llavors l'espai desaprofitat es menor !, però en canvi l'eficiencia yambé disminueix !. Per tant hem d'arribar a un compromis entre eficienca i espai. ! Calculem R amb R= M / C. i R = N * L per tant hem de decidir N i L per a que tinguem el valor R conegut. Si L=1 ! N=R: L petits fan que el hashing sigui menys eficient. Si N=1 ! L=R: no es pot donar per motius tecnologics (limitació del tamany dels buckets o pàgines, i l'accés lògic es diferent que l'accés físic). Ens hem de quedar amb elc as intermig. Si sabem el tamany del bucket (2K) hem de dedicir aquest valor (R), segons el que ocupa cada entrada: valor = 26 bytes adreça = 4 bytes

2048 bytes 30 bytes

= 68 entrades =L

• Retallar els digits no significatius: si tenim una part del valor que es mol similar en totes les dades, no considerarem esa part en el càlcu de la funció de hash. Per exemple els prefixos dels números de telefons. • Pasar a valor númeric: pasem de caracter a ASCII o EBCDIC, o alguna codificació que escollim nosaltres. Aquesta transformació es pot fer mitjançant una suma ponderada dels caracters. • Divisó (f(v)=V mod N): utilitzarem la funció modul per obtenir el valor de la funció de hash, així f(v) pren valors en tot el rang del fitxer. L'N escollit hauria de ser un N primer o be que no tingui divisors primers menors a 20 (2, 3, 5, 7, 11, 13, 17, 19). Això es fa per evitar acumulacions en el fitxer. • Técniques d'aleatorització: s'apliquen si tenim un V massa gran o massa petit: 1− recortar: apliquem un algoritme de FOLDING/PLEGAT: 12|34567|890 ! 34567 12890 47457 Per exemple, escollim un nombre del centre del valor i li sumem la resta del nombre. a més, el nombre resultant es més aleatori que el valor inicial. 2− Engrandir: escollim el centre del quadrat:

14

5864 ! (5864)2 = 3438649 nou valor= 43864 Això només te sentit si V no és un identificador (si V es identificador, no necesitem un valor més gran, ja que estará relacionat amb el yamany del fitxer). Gestió d'excedents Un excedent és un registre que o hi cab en el seu bucket primari (f(v)=@ del bucket). Hi han dues técniques: • Open Adressing (no utilitza apuntadors): només hi ha zona principal. • Chaining (apuntadors) pot tenr zona principal o zona principal mes zona d'excedents Open Adressing És una familia de técniques/metodes, amb variants. No utilitza apuntadors, i només te una zona principal (no hi ha zona d'excedents), on es col.loquen els excedents, per tant, un excedent ocuparà una posició que no li correspon (intrus). En aquest cas es recomana C " 0,7 (per exemple C=0.65). Creació: S'ha de preformatejar els buckets, marcar els registres com verges (no hi ha valor en el registre ni hi ha constancia de que hi hagi hagut). Inserció: Aplicant f al valor v obtenim una adreça: f(v)=@ Si queda espai en el bucket de @, podem col.locar el registre (posem el registre en el seu buckt primari). Si no queda espai, el registre es un intrus (haurà de posar−se fora del seu bucket primari). Busquem lloc segons una certa norma: @+1, @+2, .... Busquem seqüèncialment fins que trobem una posició lliure (circularment). Si fent això tornem a l'adreça @, això significa que el fitxer està ple, i tenim que donar un misatje d'error. Per tant, els llocs on es pogui posar un registre son: • registres verges. • un registre marcat (aquells dels que es va el.liminar un registre anteriorment). Consulta: Calculem l'adreça mitjançant la funció de hash (f(v)=@). Si el registre està en el bucket @, significa que l'hem trobat. Si no, haurem de buscar una norma: @+1, @+2, ... Podem parar aquesta cerca si: • trobem un valor. • si es troba un registre verge. No pot estar v en el fitxer, ja que d'haver estat, s'hauria insertat en el registre verge. Si es troba una marca d'esborrat, hauriem de seguir buscant. 15

• arribem a @. Hem donat una volta sencera al fitxer, per tant hem fet N accessos a disc sense èxit. Supressió: Busquem el registre (com en consulta ) i maruqem el registre com lliure. Tot això funciona si v no te repetits, si v te repetits, només hauriem de parar si trobem un verge o tornem a @ (si trobem v, no hi ha que para, perque pot haver−hi més). Problemes de l'open adressing: • Si el fitxer esta molt plé (C gran ! 1), l'eficiencia degenera per les cerques que s'han de fer en inserció, consulta o supressió. • Si hi han molts marcats, succeix el mateix: el fitxer també degenera. Si el fitxer creix molt o és molt volàtil (hi han moltes supressions en un mateix moment) llavors hem de regenerar el fitxer. • Regenerar: el.limanr els marcats, i opcionalment augmentar el tamany del fitxer. En qualsevol dels cassos, reconstruim el fitxer (buidar e insertar tots els registres). Conclusions: L'Open Adressin va be si el fitxer no és vlàtil. El nombre d'accessos es petit: si C es petit, com mitja es pot aconseguir de 1,2 a 1,4 accesos més un acces a dades. En aquestes condicions és molt utilitzat. Possibles millores: En la creació del fitxer, si creem el fitxer amb dades inicials (per exemple si estem en regenerant): • guardem els intrussos en un fitxer temporal i no els insertem fins finalitzar amb la resta. • d'aquesta forma evitem que els intrussos provoquin més intrussos. En funcionament podem millorar la inserció mitjançant els intrussos errants: • Al insertar un registre, si es troba un intrus en el seu bucket primari i el registre es va a convertir en intrus, llavors treiem fora l'intrus i el reinsertem. Això millora la consulta però ralentitza l'inserció. En l'eliminació: • podem evitar utilitzar marques, quan esborrem un registre el posem com verge i fem una reinsercció de tots els registres fins al pròxim verge. Aquesta tècnica s'anomena rehashing i millora la consulta encara que ralentitza les supressions.. Chaining És una familia de mètodes que te les seves variants. Els excedents estàn encadenats. hi han dues opcions: • només zona principal. • zona principal més zona d'excedents. En general es pot tenir una C major que en Open Adressing. C"0,9 ( si hi ha zona d'excedents). Les cadenes que tenim podràn ser: 16

• de registres (a nivell de registre). • de buckets (a nivell de bucket). * SEPARATE LISTS: els registres de la cadena són tots sinònims. * COALESCED LISTS: en la cadena poden haber registres que no siguin sìnònims. El sistema que més s'utilitza és el SEPARATE LISTS per tant és el que estudiarem a continuació: • Necessitem un apuntador al primer bucket lliure (APL), en una free list. • Si no hi ha lloc, reservem buckets complets de la zona d'excedents (pèrdua d'espai). • No hi ha intrussos. • El fi de la consulta és el fi de la cadena o un verge en el bucket. • Esborrar consisteix en marcar o (millora) refent les cadenes (compactant les cadenes), estirant de la zona d'excedents. • Els buckets són especialitzats, tant en la zona principal com en la zona d'excedents. • Les llistes són separate lists. Programació 1) Calcular el format del fitxer sense ZE. M, C ! R=M/C, L=10 ! N=R/L Exemple: M= 100.000 registres; C= 0,65; L=10 R = M/C = 100000/0,65= 153846 N= R/L = 153846/10 = 15384,6 ! 15385 buckets , aquest és multiple de 5. N final = 15391 buckets 2) Calcular format amb ZE M= 100000; C=0,9; L=10 R= M/C = 100000/0,9 = 111111 registres N = R/L = 111111/10 = 11111,1 buckets ! 111112 buckets. Zona d'excedents: Si L creix hi haurà menys excedents, en canvi si C creix, creixarà tmabé el nombe d'excedents. Si tenim C=0,9 i L=10 tindrem un 8,6% de registres excedents. 100000*8,6% = 8600 registres excedents ! 860 buckets en mitja. En el cas pitjor tindrem ! Max=860+4·"860 = 977, 3 buckets

17

3) Construir amb fitxer relatiu: els buckets es programen com un array (només funciona si són registres de longitud fixa); si no, tenim que utiltzar tires de bytes amb descriptors. 4) Preformatejar els buckets: han de preformatejar−se a verge en la creació. Hauren de distingir entre verge, marcat i ple. Hashing dinàmic Els hashings fins ara es dimensionaven les N posicions, però això te dos problemes: • Si hi ha pocs registres perdem espai si hem considerat un M massa gran. • Quan hi ha més registres dels esperats el rendiment del hashing degenera. Amb Open Adressing pot donar un error si tenim tot el fitxer ple. Amb Chaining les cadenes dels excedents augmentarà i per tant degenera el rendient. El fitxer hash pot creixer dinàmicament. Els hashings dinàmics imaginen un N molt mes gran que el necessari però només es creen uns quants buckets, aleshores la funció de hash direcciona tot l'N però fisicament només tenim els pocs buckets. Quan els buckets s'omplen es van afegint nous buckets fins arribar al màxim hipotètic que hem declarat. D'aquesta forma no es perd espai i quan hi han més registres dels esperats només haurem d¡afegir buckets. Existeixen dues técniques: • Extendible hashing: col.loca els registres en funció dels bits mes significatius de la funció de ahsh, imai hi ha excedents i per tant seria el hash perfecte (1 acces). • Linear hashing: col.loca els registres en funció dels bits menys significatius, aquesta tècnica provoca excedents que són gestionats amb chaining, en canvi manté el factor de carrega (C) constant. El valor de la funció de hash te una certa codificació binaria, en h bits, sent h un nombre prou gran Mentre el fitxer es petit, es consideraran només els primers d bits (en extendible) o els últims (en linear). A mesura que creix el fitxer, anem considerant més bits de f(v). Extendible hashing (figura 6.9 i 6.10 de la documentació) En aquest cas tenim un directori que contindrà: • d bits que s'exploren en un cert moment • 2d apuntadors a buckets.

buckets: v,@ v,@ n n és el numero de bits de l'inici de la clau que com a mínim tene en comú, es a dir, el numero que com a mínim tenen en comú els registres d'aquest bucket.

18

Els registres tal que la seva funció de hash comença per 0 es troba en el bucket a on apunta el directori amb entrada 0. n=0 inidica que els registres poden tenir zero bits en comú. Les consultes són molt eficients, ja que trobem l'adreça, la transformem a base dos i mirem el nombre de bits que indica el directori i després agafem l'apuntador que ens correspon. Si el directori es troba a memòria principal llavors la consulta te per cost un sol acces, però el diectori pot ser que sigui massa gran i que no hi capiga en memòria i per tant s'ha d'emmagatzemar en disc, i així creix el nombre d'accesos al disc. L'algorisme d'inserció és el següent: Buscar bucket corresponent si hi cap ! posarlo sino Absorvir excedent. Absorvir excedent: si bucket està apuntat per més d'un apuntador " n
19

Linear Hashing (fig 6.5, 6.6, 6.7 de la documentació) h: és el tamany màxim de l'adreça. Comencem considerant el k bits de menys pes (a l'inreves que l'estendible hashing). En el moment del disseny escollim C( factor de carrega). Per exemple, c=0,65. En temps d'execució intentem mantenir aquest C. Quan creix el nombre de registres insertats, creix proporcionalment el tamany del fitxer. Per tant l'idea del linear hashing es mantenir constant el factor de carrega C. Per mantenir C constant i augmentem els registres llavors hem d'augmentar l'espai a zona principal. Si al insertar un registre C es sobrepases aleshores s'afegeix un bucket (split del bucket que toca) i redistribuïm els registres. En linear hashing cal determinar C, L (al igual que el hahing estatic) i l'N molt gran, llavors hem de determinar els buckets inicials. El Linear Hashing col.loca els buckets en funció dels k bits de menys pes. Inicialment els buckets inicials han de ser potencia de dos. k=log2øbuckets inicialsø Figura 6.6 (Linear Hashing)

límit !

k=2 00 56 01 10 11 67 43

79

El límit significa que del límit cap a dalt s'han considerat k+1 dígits, i del límit cap a baix s'han considerat k dígits. per veure si una dreça queda per dalt o sota del límit només hem de considerar els primers k bits. En el límit també es considerarán k bits. Si hi ha massa sinónims en un bucket no fem creixer el fitxer. el fitxer només creix si es supera el factor de càrrega. Al calcular el factor de càrrega hem de tenir en compte només esl buckets de la zona principal, mai hem de tenir en compte els buckets d'excedents. Al insertar un nou bucket, pasem el límit al següent i considerem un dígit més pe al primer bucket, i el nou bucket que afegim. El límit apunta al bucket a desdoblar quan C passi el límit. L'algorisme d'inserció és el següent: Buscar el bucket corresponent. si C no sobepassa llavors s'inserta a ZP o ZE. sino 20

• SPLIT bucket (afegir bucket al final i redistribuir registres, explorant un bit més) apuntat per límit. • límit:=límit+1. • col.locar registre. • si tots buckets desdoblats llavors limit:=0; k:=k+1; L'algorisme de consulta és el següent: si k últims bits < límit aleshores agafem k+1 bits. sino usar k bits. En LH no hi ha el directori auxiliar que hi havia en l'EH, amb els repetits no hi ha cap problema ja que es posen a la zona d'excedents. Una particularitat del LH es que es fan splits cada: C·L Per exemple: L=3 C=2/3, cada dos insercions es fa un split. RESUM COMPARATIU EH Hashing perfecte Considerem d bits de mes pes N= màxim nombre de buckets en ZP

LH No hashing perfecte Considerem els k bits de menys pes N molt gran (irrellevant)

No molt gran (alerta amb el directori) Te diectori No te buckets d'overflow L=registre per bucket

No te directori Te buckets d'overflow

L ha de ser gran Si ens fiquen molt sinònims o repetits, i el bucket es petit no hi cabran per molt que el fitxer creixi.

L pot ser de qualsevol tamany

Es important posar un L molt gran per evitar que es colapsi el fitxer. Informació que es guarda:

Informació que es guarda:

· d únic

· límit únic.

· n per cada bucket C no es te en compte Aventatges:

· k únic C no ha de superar un límit. Aventatges:

· és un hashing perfecte

· no es col.lapsa.

Desaventatges:

Desaventatges:

21

· es pot col.lapsar (gestió dels repetits)

· no es un hahs perfecte

· f distribueix malament ! degeneració

· desdobla buckets per afegir buckets que no s'utilitzen.

Information Retrieval (recuperació d'informació) Es tracta d'implementacions per resldre consultes complexes. Utilitats: • Consultes per camps no identifiadors, amb molts repetts (pocs valors distints). Ex.: un camp que representi el sexe de les persones. • Consulta d'atributs multivalor (relacions 1:N). Ex.: idiomes que parla una persona. • Consultes per condicions lógiques: AND, OR, NOT. Un altra solució a aquestes consultes ( a part de les técniques d'information retrieval) són les técniques de bases de dades. Les técniques fundamentals de Information Retrieval són: • Multillistes • Fitxer invertit. Multillistes No tenim un index com un fitxer apart, sino que encadenem les dades. aquest cas necessita un diectori en el qual es posen tots els valors pssibles d'un camp, i indica on es troba el primer registre amb aquest valor i la longitud. Consulta: • ¿Quants ... hi ha? (empleats amb una carrera determiinada): aqueta consulta es resolt mirant la longitud en el directori. • ¿Quines ... hi ha? (buscar empleats que siguin matemàtics): la consulta és resolt buscant el primer de la llista en el directori i recorrent la llista. • Buscar Físics (F) i Matemàtics (M) (F and M): mirem el directori i seguim la cadena més curta. Hem de comprobar l'altra camp en les dades. Podem realitzar accessos innecessaris, ja que podem trobar registres que només compleixen una condició i per tant l'hem de mirar però en canvi no l'hem de retornar. • Buscar físics (F) o Matemàtics (M) (F or M): seguim les dues cadenes (F i M) i al recorrer la segona llista hem de mirar si s'ha trobat abans o no (visita a ducplicats). Problemes: • Les dades estàn encadenades, cosa que indica que les actualitzacions seran lentes. • La recuperació de dades pot ser lenta si les cadenes apunten a registres llunyans en el fitxer, la consulta impica molts movimients del capçal del disc. Fitxers invertits Tenim una estructura adicional que seria un directori i un fitxer de dades no encadenats.

22

El problema es que la llista te una longitud variable. La solució es agafar la longitud promig de les llistes i formar cadenes. S'anomena fitxer invertit perque les entrades del diectori guardan adreces i no dades. El diectori pot arribar a ser molt gran i potser que no hi capiguen diversos diectoris a memòria, per tant hauriem de reduir el seu tamany. una solució possible és utilitzar un mapa de bits, indicant amb 1 els registres que contenen el valor. 1 1 0 0

M F I Q T

2 1 1 0

3 0 0 0

4 1 0 1

5 ....... 0 0 0

10000 bits

Consultes: • ¿Quants ... hi ha?: mirem el directori i agafem la longitud • Buscar matemàtics: mirem l'index del directori, seguim la llista d'adreces i despres anem a dades. • Buscar F and M: mirem el directori i fem una intersecció de les dues llistes. Anem a les dades (a les adreces comuns) si fa falta (si hi ha dades comuns). • Buscar F or M: mirem el directori i fem una unió de les dues llistes. Llavors anem a les dades. • Quants F and M?, Quants F or M?: podem fer com en 3 i 4 però sense anar a les dades. Podem ordenar les adreces per posició en el fitxer de dades i llegir seqüencialment (d'aquesta forma es redueix el moviment del capçal del disc). Quan creem un nou index amb fitxer invertit hem de recorrer les dades i crear el fitxer invertit, en canvi amb les multillistes hem de modificar el fitxer de dades (afegir encadenaments pel nou camp pel qual es vol fer un index). Quan afegim nous registres a les dades en fitxer invertit només s'ha d'afegir o esborrar l'adreça d'aquest registre, en canvi amb les multillistes hem de reconstruir els encadenaments que tenim dins de les dades. Si es consulta molt habitualment un camp, aquest es pot afegir diectament a l'index. En el fitxer invertit es pot afegir però s'ha d'anar amb compte amb el tamany de l'index, en canvi en les multilistes no hi ha més remei que visitar el fitxer de dades. TEMA 4.− IMPLEMENTACIÓ FÍSICA D'ESTRUcTURES DE DADES Introducció En fitxers no hi han limitacions a l'hora de dissenyar, en canvi en base de dades si que estem limitats. Els diferents models utilitzen l'arbre elemental queconsisteix en dues entitats relacionades entre si. Els models lògics varien segons: • combinació dels arbres elementals • lligams entre les ocurrencies pare−fill.

23

Veiem tres models (a nivell de base de dades, no conceptual): • Model jeràrquic. • Model xarxa • Model relacional. Model jeràrquic Una classe o entitat, pot tenir diversos fills però una classe només pot tenir un pare (bosc). És un model molt utilitzat per base de dades on hi han moltes operacions per segon. Aquesta va ser la primera estructura de dades utilitada per implementar base de dades (IMS de IBM). Permet dos tpus de representacions físiques: • Via apuntadors. • Per contigüitat física Model Xarxa Una classe pot tenir diversos pares al contrari que en el mdel jeràrquic. Els arbres elemntals es combinen formant grafs dirigits. Les relacions s'anomenen SETS. La representació física es essencialment via apuntadors. L'estàndard és un llegunatge d'acces i definició de base de dades d'aquest tipus (CODASYL) Un sistema de gestió de base de dades que utilitzan el model en xarxa és DBMS. Model relacional No hi ha limitació en la forma de combinar els arbres elementals. Les relacions es fan mitjaçant claus foranes i no pauntadors, però es pot representar per contigütat física. Cada taula és un conjunt de tuples: sense repetits. Les relacions en els altres moels es feen mitjançant apuntadors relatius (no tenen cap significat per l'usuari). Aquí les relacions s'indiquen mitjançant la clau forana (atributs que són clau en una altra taula). Aquests aputadors s'anomenen apuntadors simbòlics (tenen significat per l'usuari). Representació intra−inter registres Representació intra−registres Guardem registres dins d'altres egistres (no hi han apuntadors), per tant utilitza una representació per contigüitat física, però amb un determinat ordre. En aquest cas els registres hauran de ser de longitud variable (les dades poden creixer). • Les actualitzacions (altes, baixes) no són trivials ja que hem de desplaçar tot el registre i per tant seria molt lent. • En les consultes hem de recorrer totes les ocurrencies de la jerarquia llegint dades que no ens interessa. • En canvi les consultes sobre tota l'ocurrencia (recuperar la jeràrquia completa) són molt trivials ja que només hem de mirar l'ocurrenica desitjada i realtzar un sol accés lògic, en canvi en la representació 24

inter−registre hem d'anar buscant els registres seguint els apuntadors. Representació Inter−Registres Utiltza apuntadors entre els registres de diferents regstres o en un mateix refgistre. En aquest cas els registres poden ser de longitud fixa (dependrà de si el egistre te un camp de longitud variable o no, no s'obliga). • L'actualització es més eficent ja que només cal afegir el registre i actualitzar els apuntadors. • La consulta sobre una entita es molt més eficent ja que mirem el fitxer o part del fitxer on es trobi aquesta entitat i la recorrem sense recorrer dades que no ens interessa. • Per realitar una consulta d'una jeràrquia sencera es mes ineficient que l'anterior degut a que hem d'anar seguint tots els apuntadors d'una jeràrquia. Els apuntadors que utilitzan poden ser de tres tipus diferents: • Absoluts (físics): adreça hardware en disc (canal / dispositiu / cilindre / plat i cara / sector). Això l'utilta el sistema operatiu. • Relatius: posició en un fitxer (desplaçament respecte al principi del fitxer). El sistema operatiu fa una conversió d'apuntador relatiu a apuntador absolut. • Simbòlics: atributs que prenen com valor la clau d'una altra taula (clau forana). El SGBD fa una conversió d'apuntador simbòlic a apuntador relatiu.

Apuntadors Acces a disc Copia Fitxers Reorganitació Absolut 1 No No (hem de tocar els pauntadors) Relatius 1 + traducció SO SI NO Simbòlics conversió SGBD + conversió SO + 1 acces Arbre B+ ! 2, 3 accesos 25

Hash ! 1,2 accesos SI SI Els apuntadors absoluts només els utilitzen els sistemes operatius, en canvi els relaiut i simbòlics els utiltzen els fitxers i bases de dades Una desventatja es quan es canvien claus de registres referenciats. Implementació Física de BD Jerarquiques En aquesta representació tenim la restricció de que un fill només pot tenir un pare. Existeixen tres técniques per representar la informació en disc: • Intra−registre (contigüitat física): tenim la seqüència física en preordre de l'arbre. Aquest mètode només serveix per fer acces seqüèncial i per consultes sobre ocurrencies senceres, però així es pot guardar en cinta. La longitud dels registres serà variable. És ineficient en l'actualització i per tant es pot utilitzar si la volatilitat del fitxer és baixa.

Descriptors C1 P1 P2 F1 L1 L2 L3 C2 P3 F2 L4 L5 F3 L6 F4 L7 • Apuntadors jeràrquics (apuntadors relatius, inter−registre): Els apuntadors formen una seqüència lógica en preordre. Tenim una seqüència d'apuntadors per a cada client. El problema es que per accedir a una dada d'un client abans hem de pasar sequencialment per les dades anteriors del client. • Apuntadors child−twin (inter−registre): cada ocurrencia te un apuntador relatiu al primer fill de cada tipus d'entitat (child) i un apuntador relatiu al següent germà del mateix pare (twin). amb aquest mètode l'acces és més directe, encara que ocupa més espai pels apuntadors. Xarxa No tenim la restricció anterior, es a dir, un fill pot tenir més d'un pare i per tant el camí d'un fill a l'arrel no té perquè ser únic. En el model en xarxa no es pot utilitzar la representació intra−registres (contigüitat física) perquè en contigüitat física només pot haver un pare. Hi han diversos mètodes: 1) Cadenes o anells. Tenim encadenats els elements, es a dir, el pare apunta al primer fill i l'últim fill apunta al pare, formant així l'anell. Amb aquest mètode : · Es díficil l'ordenació dels fills (ja que estàn tots encadenats), s'hauria d'anar insertant ordenadament. 26

· En general no es pot accedir al pare, excepte si es posen apuntadors dobles, es a dir, apuntador de fills a pares (però l'acces és molt lent, ja que s'ha d'accedir al primer fill per tenir el punter al pare). · Ha de tenir un nombre de fills petit per a que sigui eficient. 2) Matriu d'apuntadors. Per a cada ocurrencia, tenim una matriu amb apuntadors als seus fills (un vector d'apuntadors per a cada clase de fills). · L'ordenació dels fills es factible: s'ordena la matriu en funció del valor a que apunten i no sobre els apuntadors. · Permet comptar el nombre de fills (sense haver−hi d'accedir). · El problema es que les matrius han de ser de lomgitud variable. 3) Fantasmes. Aquesta técnica es combina amb els mètodes anteriors. Cada ocurrencia tindrà un apuntador al pare. · Aquest mètode permet un accés ràpid al pare. · Segueix sent díficil l'ordenació dels elements. La comparació entre aquests mètodes és equivalent a la comparació entre multillistes i fitxers invertits, on les cadenes equivaldrien a les multillistes i la matriu d'apuntadors al fitxer invertit. Consultes: • Amb fills ordenats: Amb cadenes recuperar el fill ens costarà en mitja n/2 accesos. Amb matrius d'apuntadors, tindrem ordenada la matriu i per tant podem fer cerques dicotòmiques (log2n) • Amb fills desordenats: Amb cadenes ens costarà n accesos recuperar un registre al igual que amb matrius d'adjacència. Altes i Baixes Es fan consultes (per trobar el valor cercat). • En fer altes, hem de mirar que el valor no existeixi. • En fer baixes, hem de mirar que el valors existeixi. Per tant al fer cerques és millor lamatriu d'adjacències. L'incovenient dels fitxers invertits (al igual que la matriu d'apuntadors) és que necessàriament hem de tenir registres de longitud variable. Quan el nombre de fills és molt elevat, aquestes estructures ja no hi cabran a memòra i per tant s'haurà de fragmentar la informació i per tant una consulta seria massa costossa. 27

Relacional Implementació básica • Aprofitament de técniques ja vistes. • Pot ser que tinguem una taula per fitxer, que un fitxer pogui contenir registres de diverses taules o que una taula pogui estar repartida entre diversos fitxers. • S'utilitzan apuntadors simbólics (no relatius: model jeràrquic i en xarxa) Aquestes apuntadors són més flexibles però més lents. • El model relacional no indica implementació. El model relacional és un model lògic, però no es un model físic. • Els fitxers estàn formats pe pàgines que contenen els registres. Les pàgines se'n deriven dels buckets i per tant tenen un tamany més gran. • Tota BD relacional té un catàleg, que indica totes les taules que la BD està utilitzant. • El catàleg utilitza (internament) punters relatius (ja que s'utilitzen molt) però l'usuari no els veu. Indexos S'utiltzen indexos, ja siguin Arbres B+ o hashing. Es vol evitar els accesos seqüèncials als fitxers, fent accesos per valor (per resoldre el problema del apuntadors simbòlics, etc.) Es defineixen sobre: • Clau primaria: això serveix per resoldre JOINs i per controlar repetits. • Clau forana: això serveix per resoldre JOINs i pel control de la integritat referencial. • Altres calus (alternatives). • Altres: per accelerar accesos que sabrem que seràn habituals. Tenim indexos definits automàticament (com es el cas de la clau primaria); altres són definits pel dissenyador. L'idea principal es que els indexos accelerin les consultes encara que ocupin espai y facin més lent les actualitzacions. Indexos cluster Són indexos tals que la taula está ordenada per la clau de l'index. Utilitat: • Consultes per interval dels camps de l'index: anem al primer de l'interval i llegim seqüèncialment. • Consulta de repetits Una desaventatge és que l'actualització es poc eficient, donat que les insercions requereixen que s'ordeni la taula. La solució es deixar espais lliures en les pàgines per insertar els nous registres que vinguin. Aquesta solució pot degenerar, però la técnica PCTFREE fa que es trigui més en degenerar el fitxer, però implica que es vagi reorganitzant el disc. El PCTFREE es el tant per cent de la pàgina que es deixa lliure. Se sol parlar de dos tipus d'indexos cluster: • Clustered: indexos que estàn acabats de reorganitzar. • Clustering: indexos que han anat degenerant 28

El DBS (administrador) decideix cada quan s'ha de reorganitzar. Un altre problema es que només pot haber−hiun index cluster per taula. Estructures Cluster Tenim dos o més taules que s'han guardat ordenades en les mateixes pàgines. Es a dir, no emmagatzemem cada taula en un fitxer, sino que s'emmagatzemen N taules en un únic fitxer de la forma següent: Cli2 Cli1 Fact1 ....

Client+Factura Fact1

.....

Fact2 Fact2 Fact3 Cada bucket conté un client i totes les seves factures: Ventatges: • JOIN precalculada: això es molt eficient. No hem d'utiltzar index, la JOIN ja està calculada. • Lectura seqüèncial per interval de totes les taules del cluster. Desaventatges: • Aquesta solució degenera per actualitzacions, però es pot aliviar amb PCTFREE i necessita reorganitzacions (també hi ha clustered i clustering). • Només pot haber−hi una clau cluster. • Consultes seqüèncials de només una taula es molt ineficient. Al llegir els clients seqüèncialment hem de llegir les factures que no es volen). Comparació CONSULTES Interval Puntuals SELECT * Mètode FROM cli WHERE ncli=100

SELECT * FROM cli WHERE ncli > 100 AND

JOIN SELECT * FROM cli, fact WHERE cli.ncli=fact.nlci

ncli < 200 Bàsica Indexos

rec. seq (N) logd(N+1)/2 (2 o 3 Arbre−B+ accessos) Hashing

rec.seq (N)

Bucles imbricats (M + #fact * N)

#regs de l'interval

M + #fact * (2 o 3)

1 o 2 accessos

N (no hi ha guany)

M + #fact * (1 o 2)

29

No guany ! no repetits Index cluster

Guany:

No hi ha guany

Esta físicament resolt, hem de fer el rec. seq.

Estructura cluster Rec seq de tota l'estructura Compressió i Criptografia La compressió es pot mirar a nivell d'index o a nivell de dades:

• A nivell de dades: si hi han molt caracters repetits consecutius es posa el número de repetecions i despres el caracter que es repeteix. Ex: bbbbbbbbbAB ! 9bAB • A nivell d'index. En aquest cas si el valor de l'index es molt gran, disminueix l'eficiencia ja que hi han disminueix el nombre de registres per node i per tant augmenta el nombre de nivells. Però no necessitem tot el valor per discriminar en els nodes intermedis, només necessitem lo mínm (les tres primeres lletres, etc.). Per tant emmagatzemen un valor més curt en els nodes, per tant l'ordre de l'arbre és més gran i d'aquesta forma el nombre de nivells necessaris disminueix i l'eficiencia augmenta. La criptografia s'utiltza per mantenir un acces segur a les dades. La BD estarà criptografiada per evitar accessos que vinguin de fora del SGBD el qual encriptarà i descriptarà les dades. L'algorisme d'encriptar és públic però en canvi la clau que s'utilitza és secreta. DB2 El DBS es hereditari de System R (1979), el primer prototipus d'un sistema relacional (encara que l'article que definia model relacional era de Codd, del 1969). Format d'una pagina El tamany d'una pàgina va dels 4K a 32 K. Tenim un vector en la pàgina que ens indica la posició de tots els registres de la pàgina. La pàgina ha de tenir un tant per cent lliure per a insertar registres o per a que creixin els registres. Els registres poden moure's dins de la seva pàgina. Els registres de la BD estàn identificats per: • RID: Row Identifier = Nº pàgina + Nº registre Els tegistres també poden moure's a una altra pàgina. Si canviem el registre de pàgina, per no canviar el RID posem en la pàgina on apunta el RID un apuntador (un RID secundario) que ens indica la posició real del registre. Si tenim que tornar a canviar el registre de pàgina, nomès hem de modificar el punter de la pàgina 1. Format d'un registre Prefix Long reg

Descriptor C1 C1

Descr C2

C2

• Prefix: conte la taula a la quepertany el registre, el RID, i d'altra informació. 30

• Descriptor dels camps contenen la longitud del cammp (si es fixe o no) i l'indicador ens indica si el camp te valor null o no. Si un camp te un valor nul, el seu valor no estarà i per tant no ocupa espai. En el registre els camps apareixen en l'ordre del CREATE, i els registres són de longitud variable. Estructura lògica L'estructura lògica es composa de: • Storage Groups: volums de disc, es a dir, els llocs on s'emmagatzema els fitxers. • Spaces: conjunts de pàgines extensibles (que poden creixer), aquests spaces s'emmagatzeman en un o diversos fitxers físics del sistema operatiu. Cada Storage Groups te N fitxers físics, i cada fitxer pertany a un sol Storage Group. Un Storage Group pot tenir diversos Spaces i un Space pot tenir registres de diversos Storage Group. Hi han diversos tipus de Spaces: • TABLESPACES: contenen taules (pàgines de 4K o 32K) • INDEXSPACES: contenen indexos sobre les taules de les TABLESPACES. Els INDEXSPACES noès poden estar en un fitxer, mentre que els TABLESPACES poden estar en 1 o més fitxers. Els Storage Groups tenen diferent tamany, dierent velocitat, etc. A més, els TABLESPACES i els INDEXSPACES tene propietats que varien (el tamany de la pàgina, el nombre de nodes dels arbres dels indexos, etc.) A més molts d'aquests SPACES són admissibles per separat (per fe backups o reorganitzar,...). Tablespaces Taules en pàgines de 4 o 32K en un o diversos fitxers. Existeixen tres tipus : • Simple Tablespaces: normalment contenen una taula, si contenen diverses taules poden formar una estructura cluster implementada en únic fitxer. Les taules estan completament en el Tablespace. Una pàgin te una o més files de una o diverses taules. • Segmented Tablespaces: una taula d'aquest tipus sol contenir diverses taules. Un segment és un conjunt de pàgines multiples de 4, on el tamany oscil.la entre 4 i 64 pàgines (el tamany és el paràmetre SEGSIZE). No pot haber−hi clusters (ja que un segment guarda nomès files d'una taula). Un segment guarda nomès files d'un tipus de taula, es a dir, que no pot tenir dades de dos taules diferents. D'aquesta forma els recorreguts seqüèncials són mès eficients que amb les estructures cluster i el JOIN no està completament resolt, però tampoc s'ha de reproduir des del principi (per a cada segment de Empleats, fem un accès puntual al segment de Departaments associat i no com abans que recorriem tot el fitxer de Departaments).

S1 S2

31

S3 S4 S5

32