Databasteknik II: Lösningar till tentamen 2008-03-29

Uppgift 1 (6 p)

a) (4p)

Ange en stor fördel med var och en av dessa, jämfört med de andra.

b) (2p)

Om du personligen skulle skriva ett tillämpningsprogram som arbetar mot databasen i scenariot ovan, vilken av dessa tekniker skulle du välja? Utgå från din egen tillgång till verktyg, och egna kunskaper inom programmeringsspråk med mera. Motivera varför du valde just den tekniken.

Uppgift 2 (6 p)

a) (2p)

Vad är skillnaden mellan giltighetstid och transaktionstid? Förklara, med tabellen Personer från scenariot som exempel.

b) (1p)

De flesta databashanteraren har inget inbyggt stöd för tidsdimensioner, utan om man behöver hantera tidsdimensioner måste man göra det i form av vanliga tabeller (om det nu är en relationsdatabas). Hur skulle man implementera giltighetstid i Personer-tabellen?

c) (1p)

Hur skulle man implementera transaktionstid i Personer-tabellen?

d) (2p)

Visa med exempel från scenariodatabasen vilka problem med referensintegritet som man kan få, när man lägger till tidsdimensioner.

Uppgift 3 (6 p)

a) (2p)

Här användes ingen metod för att hålla transaktionerna isolerade från varandra. Vilket eller vilka fel kan ha uppstått i databasen på grund av detta?

b) (4p)

Välj någon av metoderna för isolering av transaktioner, förklara kort hur metoden fungerar, och visa hur tidsschemat ovan skulle förändras om den metoden användes.

Uppgift 4 (6 p)

select Namn, Adress
from Personer
where Pid = 4711;

a) utan något index (eller annan sökväg) på Pid

b) med ett primärindex i form av ett B⁺-träd på Pid

c) med ett sekundärindex i form av ett B⁺-träd på Pid

Här är en SQL-fråga som tar fram namn och adress på de personer som Thomas Padron-McCarthy:

select Namn, Adress
from Personer
where Namn = 'Thomas Padron-McCarthy';

d) utan något index (eller annan sökväg) på Namn

e) med ett sekundärindex i form av ett B⁺-träd på Namn

Ange antagandena, och visa hur du räknat!

Uppgift 5 (6 p)

a) (1p)

b) (1p)

c) (4p)

Vi börjar med att dela upp selektionen i flera, och "trycker ner" varje del så långt det går i frågeträdet:

Vi gör om varje kartesisk produkt som följs av en (lämplig) selektion, till en join:

För att slippa onödiga kolumner i delresultaten kan man lägga in projektioner. Här låter vi varje selektion och join följas av en sådan projektion, eftersom vi ändå går igenom alla raderna då. Däremot lägger vi inte in några projektioner direkt på de ursprungliga tabellerna, för arbetet med att gå igenom alla raderna och göra en extra operation är förmodligen mer än vad vi tjänar på att ha färre kolumner (men lika många rader) i de direkt efterföljande operationerna.

Uppgift 6 (6 p)

a) (2p)

b) (1p)

c) (3p)

Vilka saker finns i det optimerade uttrycket som en kostnadsbaserad frågeoptimerare (eller en heuristisk optimerare som bryr sig om datamängder och lagringsstrukturer) skulle kunna gjort bättre? (Alternativt, ifall det redan råkat bli helt perfekt, vad kunde den heuristiska optimeraren ha missat?)

Uppgift 7 (6 p)

Uppgift 8 (6 p)

a) (1p)

hur ett fragementeringsschema kan se ut

b) (1p)

hur rekonstruktionsprogrammet (även kallat återskapandeprogrammet) ser ut, givet fragementeringsschemat ovan

c) (2p)

hur en global fråga kan lokaliseras genom att globala relationer ersätts med med sina rekonstruktionsprogram

d) (2p)

hur detta relationsalgebrauttryck kan förenklas genom att man reducerar bort tomma deluttryck

.........................................

Uppgift 1 (6 p)

ODBC. Står för Open Database Connectivity. En metod att låta program kommunicera med varandra med hjälp av SQL-frågor, och skicka data till varandra. Normalt är det ett applikationsprogram som kommunicerar med en databashanterare. Man lägger in SQL-satser i ett program skrivet i C eller C++. ODBC kommer från Microsoft men är en öppen standard och fungerar på många olika system och med många olika databashanterare. Nästan alla relationsdatabashanterare erbjuder möjligheter att ansluta till dem via ODBC. Man kan byta databashanterare genom att byta ODBC-drivrutin, vilket inte påverkar tillämpningsprogrammets källkod.

b) (1p) ESQL

ESQL, Embedded SQL. "Inbäddad SQL". En variant av SQL som är avsedd att stoppas in i ett program, kallat "värdprogram", skrivet i ett konventionellt programmeringsspråk som C eller Ada. På det viset kan man anropa en databashanterare från programmet. Embedded SQL är standardiserat, och gör det möjligt att lägga in SQL-satser i programmet på ett mer integrerat sätt än med vanliga CLI-API:er som ODBC. Man skriver SQL-koden mitt bland den vanliga C-koden, men markerad med orden EXEC SQL. EXEC SQL-satserna översätts sen av en preprocessor till C-kod, huvudsakligen funktionsanrop, som kan kompileras med en vanlig C-kompilator.

c) (1p) ADO.NET

ADO.NET. En uppsättning klasser i Microsofts .NET-miljö som kan användas för att låta ett program hantera data och kommunicera med databaser och andra datakällor.

d) (2p) Vilka är de största skillnaderna mellan ODBC och ADO.NET?

• ADO.NET är nyare.
• ADO.NET är fungerar med .NET under Windows, medan ODBC är mycket mer portabelt, och fungerar både i många programmeringsmiljöer och (i andra änden) med många databashanterare.
• ADO.NET är ett klassbibliotek, medan ODBC erbjuder ett gränssnitt i form av ett funktionsbibliotek.
• ADO.NET kan hantera olika sorters datakällor, till exempel XML-filer, och har funktioner för hantering av data i minnet, medan ODBC bara är till för att kommunicera med SQL-databaser.
• ADO.NET ger möjlighet att arbeta i "nedkopplat läge" eller "ej uppkopplad lösning" (på engelska "disconnected approach"), där en kopia av relevanta delar av databasen mellanlagras i tillämpningsprogrammet, med hjälp av ADO.NET-klasser. ODBC har inga sådana möjligeter (men man kan förstås skriva det själv, med egen kod).
• ODBC är mer databasoberoende. Man kan byta databashanterare genom att byta ODBC-drivrutin, vilket inte påverkar tillämpningsprogrammets källkod. ADO.NET har olika klasser beroende på vilken databashanterare man använder.

Uppgift 2 (4 p)

I en relationsdatabas utanm inbyggt stöd för tidsdimensionen giltighetstid lägger man till två kolumner, ofta kallade VST (Valid Start Time) och VET (Valid End Time):

Transaktionstid, som anger när uppgifterna gällde i databasen, eller "vad databasen vid ett visst tillfälle trodde om verkligheten", till exempel att 24 mars 2007 la man in i databasen att en viss person hade en viss adress, men 27 mars 2007 ändrade man adressen, eftersom man kommit på att den först inlagda adressen var felaktig. (Inget hade ändrats ute i verkligheten, utan det var bara en ändring i databasen.)

Med transaktionstid tas aldrig några data bort fysiskt ur databasen, utan alla gamla felaktiga uppgifter finns kvar, men markerade som att de inte längre gäller.

I en relationsdatabas utanm inbyggt stöd för tidsdimensionen transaktionstid lägger man till två kolumner, ofta kallade TST (Transaction Start Time) och TET (Transaction End Time):

Uppgift 3 (3 p)

I objekt-relationella databaser, ibland kallade "andra generationens objekt-orienterade databaser", har man i stället tagit en databashanterare, med all dess funktionalitet, och sen lagt till en objektorienterad datamodell med klasser, arv, objekt och kanske metoder. Det kan antingen vara en nyutvecklad databashanterare, som använder sig av en en helt objektorienterad datamodell (till exempel forskningssystemet Amos), med det kan också vara en relationsdatabashanterare där man, förutom relationsfunktionaliteten, lagt till möjligheter för objektorientering (till exempel nyare versioner av Oracle).

De objekt-relationella databaserna har därför mer databasfunktionalitet i form av deklarativt frågespråk, med mera, och fungerar mer likt en traditionell (relations-)databashanterare. Den objekt-relationella databasen blir mer dataoberoende (till följd av det deklarativa frågespråket), och därför blir det inte bara lättare att skriva frågor, utan också lättare att ändra i schemat.

Uppgift 4 (5 p)

a) datautvinning ("data mining")

Analyser av en databas eller ett datalager för att hitta samband och trender i datamängden. Ofta är datat insamlat för andra ändamål än datautvinning. Oftast menar man att analysen utförs med någon typ av automatiska verktyg. Brukar kräva komplexa frågor över väldigt stora mängder data.

b) datalager ("data warehouse")

En sorts databas (fast man kallar den datalager i stället för databas) som är avsedd för analyser (se datautvinning) snarare än enskilda sökningar. Innehåller stora mängde data, som kan ha överförts från de vanliga databaser som är avsedda för den dagliga driften i företaget eller organisationen. Uppdateras mer sällan än en vanlig databas, och kan hanteras med annan programvara och organiseras efter andra datamodeller.

c) dimensionsdatabas ("dimensional database")

En databas som organiserats enligt dimensionsmodellen, som är en datamodell som är vanlig i datalager. Det är inte en vanlig relationsdatabas med tabeller och godtyckliga kopplingar mellan dem, utan data betraktas som en kub med flera dimensioner. Dimensionerna kan vara till exempel tid, pris, varuslag eller ort.

d) faktatabell

Om en dimensionsdatabas ska lagras med en relationsdatabashanterare, lagras cellerna i datakuben i en faktatabell, och varje rad representerar en cell i datakuben. På raden finns dels de data som finns i cellen, och dessutom värdena på de olika dimensionerna för den cellen.

e) dimensionstabell

Om en dimensionsdatabas ska lagras med en relationsdatabashanterare, representeras varje dimension i datakuben av en dimensionstabell. Varje värde som kan förekomma på en dimension representeras som en rad i den motsvarande dimensionstabellen. Det kan vara fördelaktigt att inte normalisera dimensionstabellerna enligt tredje normalformen.

Uppgift 5 (4 p)

• Varje objekt (som i olika databashanterare kan vara alltifrån ett enda värde, till exempel ett heltal, till att omfatta hela databasen) har ett lås, och ingen transaktion får vare sig läsa eller skriva något objekt i databasen utan att först låsa det.
• En transaktion som vill ändra ("skriva") innehållet i ett dataobjekt måste ha ett skrivlås.
• En transaktion som vill läsa innehållet i ett dataobjekt måste ha ett läslås. (Eller ett skrivlås.)
• Endast en enda transaktion kan ha ett skrivlås, och då får ingen annan transaktion ha några skriv- eller läslås.
• Flera transaktioner kan samtidigt ha läslås, men då får ingen transaktion ha ett skrivlås.
• Om en transaktion försöker låsa ett objekt, och inte får låsa det eftersom en eller flera andra transaktioner redan har lås som hindrar detta, måste den transaktionen vänta på att objektet blir upplåst.
• De två faserna i tvåfaslåsning är låsningsfasen och upplåsningsfasen. En transaktion låser först de objekt den behöver, och befinner sig då i låsningsfasen, men så fort den låst upp ett enda objekt har den gått över i upplåsningsfasen, och får inte låsa några fler objekt.

Flera olika exempel, med två objekt (X och Y) och två transaktioner (T1 och T2):

Först visar vi ett exempel med (samtidiga) läslås på samma objekt:

Ett exempel med ett skrivlås, som visar att man inte kan skrivlåsa ett objekt som en annan transaktion har ett (läs- eller skriv-)lås på. Skrivlås måste vara exklusiva, dvs det enda låset på objektet.

Ett exempel till med ett skrivlås, som visar att man inte kan läslåsa ett objekt som en annan transaktion har ett skrivlås på. Skrivlås måste fortfarande vara exklusiva.

Ett exempel med flera objekt, som visar de två faserna i tvåfaslåsning:

Ett exempel med uppgradering från läslås till skrivlås:

Ett exempel till, bara för att visa att två olika objekt kan vara skrivlåsta samtidigt:

Uppgift 6 (6 p)

Vi antar att både heltal och flyttal lagras som 64 bitar (8 byte). En rad i tabellen kräver 5 * 8 byte, dvs 40 byte. Hela tabellens data blir 4 * 10¹⁴ byte, dvs 400000 gigabyte (med decimal-giga) eller 400 terabyte. (Så stora diskar finns inte idag, men om några år. Idag får vi dela upp databasen på ungefär tusen fysiska hårddiskar, men om vi inte läser parallellt från dem spelar det ingen roll för beräkningen.)

För att göra det lätt för oss att räkna antar vi att (logiska) diskblock är på 40 kilobyte, och att det går in 1000 dataposter i ett block (plus lite administrativ information). Blockningsfaktorn är alltså 1000, och det behövs 10 miljarder datablock, dvs 10¹⁰ stycken.

Vi räknar med att det tar 10 millisekunder att läsa ett godtyckligt diskblock, och 1 millisekund att läsa block som ligger i följd, vilket blocken i datafilen gör. (I synnerhet den andra tidsuppskattningen är nog väl pessimistisk.)

a) Utan index.

Det står inget om att id är deklarerad som nyckel, så vi antar att vi måste läsa alla posterna. Det finns 10¹⁰ block som ligger i följd, så varje läsning tar 1 millisekund, vilket ger 10⁷ sekunder (knappt 4 månader).

Svar: 4 månader.

Alternativt, och kanske mer realistiskt, räknar vi så här: En modern SATA-disk kan överföra 300 megabyte per sekund. Om vi läser för fullt från disken tar det (4 * 10¹⁴) / (300 * 10⁶) sekunder att läsa hela datamängden, dvs 1.33 * 10⁶ sekunder, eller 15 dygn.

Ännu ett alternativ är att räkna med de där tusen diskarna ovan, och att databashanteraren faktiskt är smart nog att läsa parallellt från allihop, och att hårdvaran i övrigt gör det möjligt att läsa med full fart parallellt från tusen diskar. Då kan vi få ner tiden till en tusendel, dvs 22 minuter.

b) Med ett sekundärindex i form av ett B⁺-träd.

Vi antar att diskblockspekare är 8 byte (det räcker inte med 32-bitarspekare!), och att även indexblocken är 40 kilobyte. Ett indexblock kan då innehålla (40*1024-8)/(8+8)+1 = 2560 pekare till subträd. Det blir jobbigt, så vi antar i stället att indexblockens storlek är 16 kilobyte, vilket ger 1000 pekare till subträd.

Om man räknar med att indexet byggts upp dyamiskt, dvs allteftersom vi la in rader i tabellen, blir indexblocken inte fullpackade, och man bör räkna med en effektiv ordning på 2/3 av trädets verkliga ordning. För enkelhets skull tänker vi oss nu att man skapade indexet efter att tabellen fyllts, och att databashanteraren då fyllde indexblocken helt fulla.

Eftersom det är ett sekundärindex, behövs på indexets lägsta nivå en pekare till varje post i datafilen, vilket är 10¹³ stycken. Med 1000 pekare i varje block, behövs 10¹⁰ indexblock på lägsta indexnivån. På nästa nivå, den andra, behövs 10⁷ indexblock. På nästa nivå, den tredje, behövs 10⁴ indexblock (10000 stycken). På nästa nivå, den fjärde, behövs 10¹ indexblock (10 stycken). På nästa nivå, den femte, behövs ett enda indexblock, som blir rotblocket. Indexet innehåller alltså fem nivåer (inklusive rotblocket).

Alternativt räknar vi ut djupet på indexträdet genom att beräkna 1000-logaritmen för 10¹³, vilket är 4.33. Vi avrundar uppåt, och får indexdjupet 5.

Om vi antar att det bara finns ett enda sandkorn med id 1000000, krävs sex diskläsningar (fem indexblock plus datablocket), där varje diskläsning tar 10 millisekunder. Total tid alltså 60 millisekunder (0.06 sekunder).

Svar: 0.06 sekunder.

Uppgift 7: Relationsalgebra, frågeexekvering, frågeoptimering (15 p)

PROJECT_{Anr, Pnamn}(SELECT_{AP.P = P.Pnr and A.Lön > 30000 and P.Adress = "Gnesta"} (A x AP x P))

(PROJECT ska egentligen vara grekiska bokstaven lilla pi, och SELECT ska egentligen vara grekiska bokstaven lilla sigma.) Frågan finns också uppritat som ett träd här nedan.

b) (1p)

Med materialiserade mellanresultat räknas varje mellanresultat ut och lagras i sin helhet (förmodligen på disk), innan det kan användas i efterföljande operationer. Operationerna utförs en i taget, utan någon parallellitet.

Med strömmande mellanresultat skickas tupler från en operation vidare till nästa operation så fort de producerats, så att flera operationer kan utföras parallellt. (Det behöver inte nödvänidgtvis förekomma någon parallellitet, vare sig äkta med flera processorer eller falsk med trådar som körs omväxlande, utan det kan fungera så att operationerna körs växelvis, till exempel genom att en operation efterfrågar tupler från en föregående operation, och då överlåter kontrollen till den så att den kan producera en eller flera tupler.)

c) (2p)

Nej, för mellanresultatet från de tre kartesiska produkterna blir mycket stort (miljarder rader). Om detta mellanresultatet ska materialiserats, tar det lång tid att producera och lagra, stort lagringsutrymme på disken, och sedan lång tid att läsa och bearbeta. Om det i stället strömmas, slipper vi tiden och utrymmet för lagringen, men det tar fortfarande lång tid att producera, och lång tid för de efterföljande operationerna att bearbeta det.

d) (1p)

En fråga i ett deklarativt frågespråk som SQL kan inte köras direkt, utan måste först översättas till en procedurell form, en så kallad exekveringsplan. En och samma deklarativa fråga kan normalt översättas till många olika möjliga exekveringsplaner, som alla ger samma resultat, men som kan variera kraftigt i effektivitet. Normalt betyder "effektivitet" i det här sammanhanget helt enkelt tiden det tar att köra exekveringsplanen. Frågeoptimering går ut på att välja en effektiv exekveringsplan.

e) (1p) Vad innebär heuristisk optimering?

Optimeraren använder några ganska enkla regler för hur man gör en effektiv exekveringsplan, till exempel att selektion bör utföras före join, eller att kartesiska produkter bör undvikas.

f) (5p)

Optimeraren utgår från den ooptimerade relationsalgebrarepresentationen av frågan:

Vi delar upp villkoret i selektionsoperationen i flera, för att senare kunna flytta runt dem:

Vi trycker ner varje selektionsoperation så långt det går i trädet:

Där det går kombinerar vi en kartesisk produkt följd av en selektion till en join:

Vi trycker ner projektioner så långt det går i trädet:

En del av dessa projektioner gör inget, eller är förmodligen onödiga, så dem tar vi bort:

Om den usrpungliga frågan formulerats med tabellerna i ordningen A, P, AP i stället för A, AP, P, hade vi behövt ändra ordningen på de kartesiska produkterna från A X P X AP till exempelvis A X AP X P för att kunna åstadkomma joinen mellan A och AP.

Man vill också utföra den mest restriktiva selektionen först. Om optimeraren antar att en selektion med likhetsvillkor (Adress="Gnesta") är mer restriktiv än en storleksjämförelse (Lön>30000), så kan den ändra ordningen på de kartesiska produkterna från A X AP X P till P X AP X A.

g) (1p)

En kostnadsbaserad frågeoptimerare har en kostnadsfunktion, som givet en ekeveringsplan räknar ut den förväntade kostnaden för att köra den. Normalt betyder "kostnad" i det här sammanhanget helt enkelt tiden det tar att köra exekveringsplanen. Kostnadsfunktionen kan ta hänsyn till olika algoritmer för att utföra en operation, till vilka index som finns, och till statistik om innehållet i databasen. Den kostnadsbaserade frågeoptimeraren jämför den förväntade kostnaden (enligt kostnadsfunktionen) för olika exekveringsplaner (antingen för alla som är möjliga, eller för ett urval av dem), och väljer den billigaste.

Till skillnad från (normal) heuristisk optimerare kan en kostnadsbaserad optimerare ta hänsyn till olika algoritmer för att utföra operationer som join, till vilka index som finns, och till statistik om innehållet i databasen. Det gör att den kan generera bättre (dvs mer effektiva) exekveringsplaner. Den är å andra sidan mer komplicerad än en heuristisk optimerare, vilket gör att den blir svårare att implementera och även mer tidskrävande (för själva optimeringen).

h) (2p)

En kostnadsbaserad frågeoptimerare kan generera bättre (dvs mer effektiva) exekveringsplaner än en heuristisk optimerare. Den är å andra sidan mer komplicerad än en heuristisk optimerare, vilket gör att den blir svårare att implementera och även mer tidskrävande (för själva optimeringen).