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 : bidoit@lri.frAvertissement : 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,bidoit@lri.fr11 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 ...
Contact : Nicole Bidoit LRI UMR 8623 CNRS - Bat 490 Universite´deParisSud, 91405 Orsay Cedex, France email : bidoit@lri.fr
Avertissement : Cesupport de cours est dans une version non sta-ble; il peut donc contenir des erreurs (typos, fautes d’orthographe, ...) etje vous remercie de me les signaler; il n’est pas complet; ilcontientdessectionsquineserontpaspre´sente´estellesqu’elles encoursouquineserontpasprs´ent´eesdutout.
•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
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{A1,A2, ...,An}est une fonction ude{A1,A2, ...,An}dans Dom tel queu(A1)∈Dom peut aussi dire. On plus simplement queutins´etudeeoctsnvaleurs (a1,a2, ...,an) telles que pour touti= 1..n, la valeuraiappartient au domaine de l’attributAi. (Cetted´efinitionsupposequelesattributssoientordonnes).Onnoteu[Ai] ´ la valeuraidu n-upletuque l’on appelle la composante de u surAi. Un n-uplet sur (A1,A2, ...,Anp)ueatsuisˆetred´efinicomme´´lmenedtu un e produitcart´esienDom(A1)×...×Dom(An) et une instance de R comme un sous ensemblefinide Dom(A1)×...×Dom(An). 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={R1,R2, ...,Rm}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{R1,R2, ...,Rm}(auquel on ajoute le pre´dicatd’e´galite´)telquel’arit´edupr´edicatRira’la`lage´tiosdu´eit sche´maderelationRi. Celangage´etantd´efini,onpeutmaintenant´ecriredesformulesdecelan-gageenutilisantlesr`eglesbienconnuesrappele´esmaintenant.Uneformule atomique est de la forme ` t constante, •x=youx=aouaes une •Ri(t1 ... tnu`o)needt´ri’atlesRiettj variable uneest un terme i.e. ou une constante (puisque pas de symboles de fonction). Uneformulebienform´eeestd´efiniere´cursivementpar: •uotfoen´erme,nufeeetselibroumrmultefomiqueato •soientϕ1etϕ2dfxueumroolsrlesbienform´eesa¬ϕ1,ϕ1∧ϕ2sont desformulesbienform´ees •soitϕ1 sune formule bien for ´ l∃xϕ1stee.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,Ic,IP) ouIcest une fonction de l’ensemble des constantes dansDetIPest une ` 5