Cours sur les bases de données avancées

Description

Bases de donn´ees avanc´eesMaster 1`ere ann´eeUniversit´e Paris Sud, Facult´e des Sciences d’Orsay∗Mme Nicole Bidoit-TolluContact : Nicole BidoitLRI UMR 8623 CNRS - Bat 490Universit´e de Paris Sud,91405 Orsay Cedex, Franceemail : [e-mail] : Cesupport de cours estdansune version non sta-ble; ilpeutdonccontenirdeserreurs(typos, fautesd’orthographe,...) et je vous remercie de me les signaler; il n’est pas complet;il contient des sections qui ne seront pas pr´esent´ees telles qu’ellesen cours ou qui ne seront pas pr´sent´ees du tout.∗LRI UMR 8623 CNRS- Bat 490, Universit´e de Paris Sud, 91405 Orsay Cedex, France,[e-mail]11 IntroductionObjectifs :• acqu´erir de nouvelles connaissances• d´ecouvrir de nouvelles techniques• apprendre `a poser les bonnes questionsUn petit historique de la th´eorie des BDs• avant 1970 : BD = fichier d’enregistrementsCOBOL/CODASYLmod`ele r´eseau• en 1970 : BD = structure du 1er ordremod`ele relationnel (Codd)une avanc´ee importante !!!!!!!!!!20 ans pour l’adopter !!!!!!!!!!succ`es : th´eorie + pratique + commercialUn petit historique : les ann´ees 80 et 90• El´ements fondamentaux du relationnelth´eorie des d´ependances fonctionnellesgestion des transactions (concurrence)• Etude de nouveaux mod`elesmod`ele non normalis´e (imbrication)mod`eles a` valeurs complexes, a` objets• Etude de nouveaux langagesDatalog, WHILE, Fixpoint ...complexit´e, expressivit´e• Etude de nouvelles ...

Informations

• Publié par: Zolot
• Nombre de lectures: 68
• Langue: Français

Extrait

Basesdedonn´eesavanc´ees Master1`ereann´ee Universit´eParisSud,Facult´edesSciencesd’Orsay Mme NicoleBidoit-Tollu ∗

Contact : Nicole Bidoit LRI UMR 8623 CNRS - Bat 490 Universite´deParisSud, 91405 Orsay Cedex, France email : [e-mail]

Avertissement : Ce support de cours est dans une version non sta- ble; il peut donc contenir des erreurs (typos, fautes d’orthographe, ...) et je vous remercie de me les signaler; il n’est pas complet; ilcontientdessectionsquineserontpaspre´sente´estellesqu’elles encoursouquineserontpasprs´ent´eesdutout.

∗ ,ceanFredePsit´Sud,arisO5sr1904ed,xyaeCiver0,Unat49RS-B32NCRM68RLUI [e-mail]

1

1 Introduction Objectifs : ´erirdenouvelleonnaissances •acqu s c •seuqetseinhcde´enouvellcouvrird •ppasepoesrlndre`arequesnnbosonties

Unpetithistoriquedelath´eoriedesBDs

• BDavant 1970 : = fichier d’enregistrements COBOL/CODASYL mod`eler´eseau

•en 1970 : BD = structure du 1er ordre mode`lerelationnel(Codd) uneavanc´eeimportante!!!!!!!!!! 20 ans pour l’adopter !!!!!!!!!!

succe`s:th´eorie+pratique+commercial

Unpetithistorique:lesann´ees80et90

•nnelatiourelElme´etnemdxuafstnadno th´eoriedesde´pendancesfonctionnelles gestion des transactions (concurrence) •xuae`domseleEtudedenouv mod`elenonnormalis´e(imbrication) mod`eles`avaleurscomplexes,a`objets •Etude de nouveaux langages Datalog, WHILE, Fixpoint ... complexit´e,expiit´ ress v e •Etude de nouvelles applications informationincompl`ete basesdedonne´esdistribue´es bases de d ´ ´ ra hiques onnees geog p

2

•Point de vue pratique unseullanguage : SQL une application : OLTP une architecture : client – serveur

Aujourd’hui : l’age du Web •le-t?sellseodnn´eesduWeb:queson donne´essemi-structure´es,XML XML-sch´ema,DTD •li?sno-tquestes:quˆederesegagnalsel X-path, UNQL, XML-query ... •les architectures : 3-tiers

LecoursdeBasesdeDonn´eesAvance´es:

CONCEPTS FONDAMENTAUX : MODELES et LANGAGES •mod`Duelateleri-emrusturct´ennoiuale`domsele •es:Lnaagegdsreqeˆute qu’est-ce qu’u ˆte ? ne reque qu’est-cequ’unbonlangagederequeˆtes? –diversparadigmes/diversprobl`emes –complexite´/optimisation (inclusion, minimisation, ...) –expressivit´e(comparerleslangages) Organisation (classique) :cours, tds, devoir, ..., discussion

Biblio : [AHV95] S.Abiteboul / R. Hull / V. Vianu : Foundations of Databases. Addison-Wesley Publishing Company, 1995. (Chapitres 3, 4 et 5 : no- tionse´l´ementaires-basesdedonne´esrelationnellesetlangagesderequˆetes; Chapitre16:contexteg´ene´raldeslangagesderequeˆtes;Chapitre17: R´esultatsd’expressivit´eetcomplexit´edeslangagesderequetes.) ˆ

3

2Mode`leRelationnel(rappel)etLogiqueclassique Oncommenceparfaireunrappelrapidedequelquesnotionsfamili`eresdans ledomainedesbasesdedonn´ees(niveaulicence).Lerappeleste´galement faitpourquelesnotationsutilise´esdanslasuiteducourssoientexplicite´es. 2.1P´eliminaires r On suppose l’existence de trois ensembles : 1.unensembled’attributsnote´Attr, 2.unensembledeconstantesnote´Dom-ailcfiispm`esepothl’hyferano( tricequetoutattributalemeˆmedomaineDom), 3.unensembledenomsderelationsnote´Relet A chaque nom de relation R dansRelon associe un ensemble d’attributs note´Attr(R).Doncunsche´maderelationestsp´ecifie´parsonnom.La cardinalit´edeAttr(R)estl’arit´edelarelationR,note´e|R|. On notera parfoislesche´maRparR(Attr(R)).SiZ=X∪Y avec X∩Y=φ, on le notera simplement par XY. Unseshce´madebasededonn´eRnutseelbmesnechesidfinesdma´e relation.Lesnotionsden-upletsurunsche´maderelationR, d’instance IsuR¸ retd’instancedesche´madebasededonn´eessontd´efiniesdefacon classique : Un n-uplet sur un ensemble d’attributs{A 1 ,A 2 , ...,A n }est une fonction ude{A 1 ,A 2 , ...,A n }dans Dom tel queu(A 1 )∈Dom peut aussi dire. On plus simplement queutins´etudeeoctsnvaleurs (a 1 ,a 2 , ...,a n ) telles que pour touti= 1..n, la valeura i appartient au domaine de l’attributA i . (Cetted´efinitionsupposequelesattributssoientordonnes).Onnoteu[A i ] ´ la valeura i du n-upletuque l’on appelle la composante de u surA i . Un n-uplet sur (A 1 ,A 2 , ...,A n p)ueatsuisˆetred´efinicomme´´lmenedtu un e produitcart´esienDom(A 1 )×...×Dom(A n ) et une instance de R comme un sous ensemblefinide Dom(A 1 )×...×Dom(A n ). On notera Inst(R) (resp. Inst(Rma´erlsuches))l’ensesnatcnsebmeledis de relationRpserrus.(asedadebh´emlescs´needenoR). Le domaine actif d’une instanceIdeR de toutes les constantes apparaissant, i.e. l’ensemble dansI,estnot´eadom(I).

4

2.2Calculrelationnel–a`variablesdomaines– Lecalculrelationnelestunlangagederequˆetede´finiassezdirectementa` partir de la logique classique du premi ordre. Nous allons donc ´ er commence par construire lepontitalerele`domeleueiqogaltlleneonclassiqueauentr premierordre.Rappelonsquenousavonssuppos´equetouslesattributsont le meme domaine Dom. ˆ Conside´ronsdoncunsche´maR={R 1 ,R 2 , ...,R m }cice`ai-lucosssnoiA. le langage de la logique classique dont le vocabulaire (en dehors de variables x,y,ede:ti´unotssect..). •un ensemble Dom de symboles de constante, •un ensemble vide de symboles de fonction •stnunedelembsecadi´epr{R 1 ,R 2 , ...,R m }(auquel on ajoute le pre´dicatd’e´galite´)telquel’arit´edupr´edicatR i ra’la`lage´tiosdu´eit sche´maderelationR i . Celangage´etantd´efini,onpeutmaintenant´ecriredesformulesdecelan- gageenutilisantlesr`eglesbienconnuesrappele´esmaintenant.Uneformule atomique est de la forme ` t constante, •x=youx=aouaes une •R i (t 1  ... t n u`o)needt´ri’atlesR i ett j  variable uneest un terme i.e. ou une constante (puisque pas de symboles de fonction). Uneformulebienform´eeestd´efiniere´cursivementpar: •uotfoen´erme,nufeeetselibroumrmultefomiqueato •soientϕ 1 etϕ 2 dfxueumroolsrlesbienform´eesa¬ϕ 1 ,ϕ 1 ∧ϕ 2 sont desformulesbienform´ees •soitϕ 1  sune formule bien for ´ l∃xϕ 1 stee.rm´eroumnufeneofelib mee a or Biensuˆrlesconnecteursdedisjonction∨et d’implication→ainsi que la quantification universelle∀itue´siltnevrteˆeupruercti’le´iteracilourfeesp des formules. Las´emantiqued’unlangagedupremierordrene´cessited’introduirela notiond’interpr´etation,devaluationdesvariables,desatisfactiond’unefor- muleparuneinterpr´etation.Uneinterpre´tationIest un triplet (D,I c ,I P ) ouI c est une fonction de l’ensemble des constantes dansDetI P est une ` 5