Gagnasafnsfræði, haust 2011

[ Dagskrá  |  Námsefni  |  Verkefni  |  Dæmatímar  |  Orðalisti  |  Námsmat  |  Kennslubók ]

Verkefni 12 - Blandað efni

Lausnum skal skilað í hólf viðkomandi dæmakennara (sjá lista yfir dæmatíma).

Skiladagur: þriðjudaginn 29. nóvember fyrir kl 16:00

Skiladæmi:

1. Hannið gagnasafn fyrir bókasölu á netinu. Bóksalan rekur vefsíðu og þar er meðal annars hægt að skoða bækur, lesa umsagnir og panta bækur.

   Bók hefur titil, ISBN númer, verð í ISK, útgefanda, útgáfudagsetningu, útgáfu númer, stutta lýsingu, og að lokum einn eða fleiri höfunda.

   Notendur geta skráð sig á síðuna. Hver notandi hefur notandanafn, lykilorð og netfang.

   Notandi getur skrifað umsagnir um bækur. Hver umsögn fjallar um tiltekna bók og inniheldur texta ásamt stjörnugjöf á bilinu 0-5 stjörnur.

   Notandi getur sett bækur í "körfu" (shopping cart) og síðan sett körfuna í afgreiðslu og þar með lagt inn pöntun á þeim hlutum sem eru í henni. Karfan inniheldur eina eða fleiri bækur.

   Pöntun inniheldur eina eða fleiri bækur, ásamt verðinu þegar þær voru pantaðar, dagsetningu pöntunar og dagsetningu sendingar (þegar bækurnar voru sendar af stað í pósti)

   Hannið töflur fyrir gagnasafnið og sýnið CREATE TABLE skipanirnar fyrir þær. Munið að tilgreina alla aðallykla og ytri lykla í skilgreiningunum.

   Svar:

   CREATE TABLE books
   (
       isbn CHAR(13) PRIMARY KEY,
       title VARCHAR(64) NOT NULL,
       price DECIMAL NOT NULL,
       publisher VARCHAR(64) NOT NULL,
       pub_date DATE NOT NULL,
       edition INTEGER NOT NULL,
       description TEXT NOT NULL
   );
   
   CREATE TABLE authors
   (
       id SERIAL PRIMARY KEY,
       name VARCHAR(64) NOT NULL
       -- etc.
   );
   
   CREATE TABLE book_author
   (
       isbn CHAR(13) REFERENCES books (isbn),
       author_id INTEGER NOT NULL REFERENCES authors (id),
       PRIMARY KEY (isbn, author_id)
   );
   
   CREATE TABLE users
   (
       id SERIAL PRIMARY KEY,
       username VARCHAR(32) NOT NULL,
       password CHAR(32) NOT NULL,
       email VARCHAR(64) NOT NULL
   );
   
   CREATE TABLE book_review
   (
       id SERIAL PRIMARY KEY,
       isbn CHAR(13) REFERENCES books (isbn),
       user_id INTEGER REFERENCES users (id),
       stars INTEGER NOT NULL,
       review TEXT NOT NULL
   );
   
   CREATE TABLE cart_items
   (
       id SERIAL PRIMARY KEY,
       user_id INTEGER REFERENCES users (id),
       isbn CHAR(13) REFERENCES books (isbn)
   );
   
   CREATE TABLE order
   (
       id SERIAL PRIMARY KEY,
       user_id INTEGER REFERENCES users (id),
       created DATE NOT NULL,
       sent DATE
   );
   
   CREATE TABLE order_items
   (
       id SERIAL PRIMARY KEY,
       order_id INTEGER REFERENCES order (id),
       isbn CHAR(13) REFERENCES books (isbn),
       qty INTEGER NOT NULL,
       price DECIMAL NOT NULL
   );
   

2. [Prófdæmi 2008]

   Gefnar eru töflurnar:

   Emp( eid, ename, salary, works_for_did ) 
   Project( pid, descr, budget, hosted_by_did ) 
   Takes_part( eid, pid, hours_per_month ) 
   Dept( did, dname, manager ) 
   

   Töflurnar geyma upplýsingar um starfsmenn (Emp), verkefni (Project) og deildir (Dept) í fyrirtæki nokkru.

   Það er skráð hvaða starfsmenn vinna í hvaða verkefni og hversu marga tíma á mánuði (Takes_part).

   Einnig er skráð í hvaða deild hver starfsmaður er (works_for_did sviðið í töflunni Emp) og hvaða hvaða deild hvert verkefni tilheyrir (hosted_by_did sviðið í töflunni Project).

   Þið eigið að búa til SQL skipanir til að svara eftirfarandi fyrirspurnum á þetta gagnasafn:

   1. Sýnið það verkefni sem hefur mesta fjármagnið (budget) af þeim verkefnum sem tilheyra "Sales" deildinni.

      Svar:

      SELECT P.pid, P.descr
      FROM Project P, Dept D
      WHERE P.hosted_by_did=D.Did
        AND D.dname='Sales'
        AND P.budget = (
          -- Skoðum öll verkefni í Sales deildinni og finnum hæsta budget
          SELECT MAX(P.budget)
          FROM Project P, Dept D
          WHERE P.hosted_by_did=D.did
            AND D.dname='Sales'
        )
      

   2. Sýnið þau verkefni sem hafa enga starfsmenn skráða á sig.

      Svar:

      Dæmi um lausn:

      SELECT P.pid, P.descr
      FROM Project P
      WHERE NOT EXISTS (
          -- Listi yfir starfsmenn sem hafa tekið þátt í viðkomandi verkefni
          SELECT T.eid
          FROM Takes_Part T
          WHERE T.pid=P.pid
        )
      

      Dæmi um aðra lausn:

      SELECT P.pid, P.descr
      FROM Project P LEFT JOIN Takes_Part T
        ON P.pid=T.pid
      WHERE T.eid IS NULL
      

      Dæmi um enn aðra lausn:

      SELECT P.pid, P.descr
      FROM Project P
      WHERE p.pid NOT IN (
          SELECT pid
          FROM Takes_Part
        )
      

   3. Sýnið þá starfsmenn sem aðeins vinna við verkefni sem tilheyra deildinni sem þeir sjálfir eru í.

      Svar:

      Dæmi um lausn:

      (
      -- Allir sem vinna í einhverju verkefni í sinni eigin deild
      SELECT E.eid, E.name
      FROM Emp E, Takes_Part T, Project P
      WHERE T.eid=E.eid
        AND T.pid=P.pid
        AND E.works_for_did=P.hosted_by_did
      )
      EXCEPT
      (
      -- Allir sem vinna í einhverju verkefni sem er ekki í þeirra eigin deild
      SELECT E.eid, E.name
      FROM Emp E, Takes_Part T, Project P
      WHERE T.eid=E.eid
        AND T.pid=P.pid
        AND E.works_for_did <> P.hosted_by_did
      )
      

      Dæmi um aðra lausn:

      SELECT E.eid, E.name
      FROM Emp E
      WHERE E.works_for_did = ALL (
          -- Finnum allar mismunandi deildir sem viðkomandi starfsmaður hefur unnið verkefni fyrir
          SELECT DISTINCT P.hosted_by_did
          FROM Project P, Takes_Part T
          WHERE T.pid=P.pid
            AND T.eid=E.eid
        )
      

   4. Sýnið öll þau verkefni sem starfsmaðurinn "John" vinnur við, í röð eftir umfangi, þ.e. heildarmagni tíma sem settir eru í verkefnið (ekki aðeins tíma "John"). Sýnið þó aðeins þau verkefni þar sem umfangið er meira en 100 tímar.

      Svar:

      Dæmi um lausn:

      SELECT P.pid, P.descr, SUM(T.hours_per_month) as tot_hours
      FROM Project P, Takes_Part T
      WHERE T.pid=P.pid
        AND T.pid IN (
          SELECT T.pid
          FROM Takes_Part T, Emp E
          WHERE T.eid=E.eid
            AND E.ename='John'
        )
      GROUP BY P.pid, P.descr
      HAVING SUM(T.hours_per_month) > 100
      ORDER BY SUM(T.hours_per_month) DESC
      

      Dæmi um aðra lausn:

      SELECT P.pid, P.descr, H.tot_hours
      FROM Project P, Takes_Part T, Emp E, (
        SELECT T.pid, SUM(T.hours_per_month) AS tot_hours
        FROM Takes_Part T
        GROUP BY T.pid
        HAVING SUM(T.hours_per_month) > 100) AS H
      WHERE P.pid=T.pid
        AND T.eid=E.eid
        AND P.pid=H.pid
        AND E.ename='John'
      ORDER BY H.tot_hours DESC
      

3. [Prófdæmi 2008]

   Lát R(A,B,C,D,E) vera vensl með fallákveðunum AB → C, AC → B, AD → E, B → D, BC → A.

   1. Finnið alla lykla venslanna R.

      Svar:

      {AB}+ = ABCDEF svo AB er lykill.

      {AC}+ = ABCDEF svo AC er líka lykill.

      {BC}+ = ABCDEF svo BC er einnig lykill.

   2. Ef venslin R eru ekki á BCNF bendið þá á hvers vegna ekki og brjótið venslin upp þannig að þau uppfylli BCNF.

      Svar:

      Nei, AD → E brýtur gegn BCNF (AD er ekki yfirlykill)

      Brjótum upp þar til við höfum BCNF.

      

   3. Ef venslin R væru brotin upp í venslin R1(A, B, C) og R2(A, B, D, E) væri það uppbrot þá taplaust (e. lossless)? Útskýrið.

      Svar:

      Finnum sameiginlega dálka. R1 ∩ R2 = AB.

      Athugum hvort AB ákvarði annaðhvort ABC eða ABDE.

      AB getur ákvarðað ABC (og reyndar líka ABDE, en eitt nægir). Uppbrotið er því taplaust.

4. Gerum ráð fyrir eftirfarandi töflum:

   A(a,b,x)
   B(b,c,y)
   C(c,d,z)
   D(d,q)
   

   og eftirfarandi fyrirspurn:

   SELECT x,y,z,q
   FROM A,B,C,D
   WHERE A.b=B.b
     AND B.c=C.c
     AND C.d=D.d
     AND A.x < 500
     AND B.y = 100
     AND C.z > 10
   

   Hér fyrir neðan er lélegt segðatré fyrir framkvæmd á fyrirspurninni:

   

   Komið með tillögur að betra tré og færið rök fyrir því af hverju það er betra.

   Svar:

   

   Rökstuðningur:

   Segðatréið er betra því það lækkar fjölda raða sem þarf að senda upp tréið (minnkar stærðina á svokölluðum milliniðurstöðum, intermediate result sets). Tenging er dýr aðgerð og með því að ýta valinu niður (selection push-down) þá fækkum við röðunum sem þarf að tengja. Einnig opnum við fyrir þann möguleika að nota flýtivísa sem gætu verið til staðar til að finna raðir sem uppfylla selection skilyrðin.

   Annað sem er betra við þetta tré er right-deep röð á tengingum. Í slæma trénu þá þarf að reikna niðurstöðuna úr tveimur tengingum og síðan tengja þær milliniðurstöður saman (oft búnar til temporary töflur á bakvið tjöldin til að geyma slíkar milliniðurstöður úr tengingum sem þarf síðan að tengja aftur). Ef milliniðurstöðurnar eru of stórar til að geyma í minni þá þarf að skrifa þær út á disk, sem er mjög dýr aðgerð.

   Í okkar tilfelli þá eru tengingarnar settar upp í nokkurskonar færiband (pipeline) sem hentar mjög vel fyrir útreikninga í mörgum reikniritum fyrir tengingu þar sem unnið er með eina röð úr öðrum venslunum en allar raðir í hinum venslunum (eða mögulega hægt að fletta upp öllum viðeigandi röðum með flýtivísi).

5. Gerum ráð fyrir MVCC kerfi eins og í PostgreSQL.

   Eftirfarandi hreyfingar eru ennþá opnar (ókláraðar): 60, 80.

   Það var hætt við eftirfarandi hreyfingar (aborted): 70, 90

   Allar aðrar hreyfingar voru kláraðar með commit.

   Hreyfing númer 100 les eftirfarandi töflu.

   Svarið eftirfarandi spurningum:

   1. Hvaða raðir eru sýnilegar ef hreyfingin sem les gögnin er með einangrunarstig READ COMMITTED?

      Svar:

      1, 4, 5, 6, 8

   2. Hvaða raðir eru sýnilegar ef hreyfingin sem les gögnin er með einangrunarstig SERIALIZABLE?

      Svar:

      1, 4, 6, 8, 9

   Svar á töfluformi:

   ID	xmin	xmax	Sýnileg í READ COMMITTED	Sýnileg í SERIALIZABLE
   1	50		Já	Já
   2	60		Nei	Nei
   3	70		Nei	Nei
   4	75		Já	Já
   5	150		Já	Nei
   6	50	70	Já	Já
   7	50	77	Nei	Nei
   8	50	80	Já	Já
   9	50	140	Nei	Já
   10	130	180	Nei	Nei