2014. őszi félév: Az adatbázisrendszerek elméleti alapjai 

 

(Utolsó módosítás: 2014. november 25.)

 

A kurzushoz tartozó levelezéshez, anyagok küldésére kizárólag a 2014abea@gmail.com címet használjátok!

 

Hirdetés:

 

Tematika:

Szemelvények az adatbázis-kezelés elméletéből.

Hasonló kurzusok:

http://www.cs.washington.edu/education/courses/544/

http://www.dbai.tuwien.ac.at/staff/pichler/dbt/index.html

 

Vizsga:

 

Folyamatos számonkérés lesz, témakörönként egy rövid teszt és egy kiscsoportos kutatási feladat (cikk olvasás, feladatkitűzés, algoritmusimplementálás, rövid cikkírás és prezentáció) a félév második felében.

 

Vizsgakérdések (1-9):

 

1. Relációs algebra és SQL

algebra.ppt

 

2. Relációs kalkulusok (DRC, TRC, tartományfüggetlenség, biztonságosság, ekvivalens lekérdező nyelvek (bizonyítással)

kalkulusok.ppt WINRDBI WINRDBI slides

 

3. Konjunktív lekérdezések, Datalog programok, lekérdezések tartalmazása, nézetek minimalizálása, lekérdezési problémák bonyolultsága

lecture05-06.ppt  ( lecture05-06hun.ppt) és rekurziv sql datalog.ppt DATALOG rendszer (DES)

 

4. Fuzzy halmazok, fuzzy logika, műveletek kiterjesztése, fuzzy adatbázisok, fuzzy relációs algebra, alkalmazási területek:

Beolvas_s14-11-25_1429_.pdf de_3344.pdf Achs_1995_ActaCybernetica.pdf 223.pdf p19930006.pdf

fuzzy1.pdf (1-33 oldal), fuzzyism.pdf (1-5 oldal), Bosc 2006.ppt (1-19 oldal)   sem1.ppt (1-14 oldal)

 

5. A 3-értékű (igaz, hamis, ismeretlen) logika szakértői rendszerekben, rákövetkezési operátor 2- és 3-értékű esetben, stabil modell, megalapozott modell:

wellfoundedmodel.pdf (1-7 oldal) (a részletek ebben találhatók: Well-founded szemantika.zip ), wellfounded.pdf (1-16 oldal) cs345-2.pptx

 

6. Osztott adatbázisok: Bevezetés, architektúrák, darabolás (fragmentálás), sokszorosítás (replikálás), 2PC (2 fázisú commit protokoll), Globális és lokális zárkezelés.

week1_lecture1.ppt week1_lecture2.ppt week2_lecture1.ppt week2_lecture2.ppt week3_lecture1.ppt week3_lecture2.ppt

ppea24.pdf (Katona Gyula előadásjegyzete alapján)

(Az előadások a következő könyvből tartalmaznak szemelvényeket: M. Tamer Ozsu, Patrick Valduriez: Principles of Distributed Database Systems, 2/E, 1999) A diák forrása: http://www.cs.purdue.edu/homes/bb/cs542-06Spr/

 

7. Osztott adatbázisok lekérdezése, félig-összekapcsolások szerepe, félig-összekapcsolásos program, teljes redukáló, aciklikus hipergráf, jóldefiniáltság, GYO-redukció

 

8. Teljes redukáló konstruálása aciklikus hipergráf esetén, (R1 join R2 join  ..  join Rn) vetítése Ri-re, az összekapcsolások méretének becslése

 

9.  Teljes redukáló kiszámítási költsége, (R1 join R2 join  ..  join Rn) vetítése adott attribútumhalmazra és a kiszámítás költsége

A 7-9 tételekhez az előadás kézirata: Osztott.pdf (1-29 oldal) (a részletek ebben találhatók, a beolvasott oldalak külön eps fájlok: Optimization.zip , a pdf-be konvertáláshoz http://www.online-convert.com/ is használható.)

 

A bécsi kurzus anyaga:

dbt00.pdf dbt01.pdf dbt02.pdf dbt03.pdf dbt04.pdf dbt05.pdf dbt06.pdf dbt07.pdf

 

Sidló Csaba összefoglalása a 2011 VLDB konferencián tapasztalt trendekről: vldb-2011-09-29.pdf

Szeminárium: Szeminarium.doc

 

Bonyolutságelméleti kurzusanyag: calc-chap1.pdf calc-chap2.pdf calc-chap3.pdf calc-chap4.pdf calc-chap5.pdf calc-chap6.pdf calc-chap7.pdf calc-chap8.pdf

 

A vizsgajegy a 2 részből adódik össze.

 

A 9 tételhez segítség.

Korábbi években hallgatók által kidolgozott tételek (nincs ellenőrizve!)

1.      Maczika Száva, Balog Péter: RelAlgebra.docx Prezentáció:

2.      Csubák Dániel, Varga Péter, Vörös Péter: 2_drc_trc.doc Prezentáció: 2_drc_trc.pptx

3.      Barabás Gábor, Nagy Dávid, Nemes Tamás: 3_konj_datalog.doc Prezentáció: 3_konj_datalog.pptx

4.      Bodnár István, Fodor Krisztián, Gyimesi Gábor: FuzzyJegyzet.doc Prezentáció: Fuzzy.ppt

5.      Balázs Barnabás Lóránt, Iván Gergő, Szalona Szandra: 3-erteku logika.doc Prezentáció: 3-erteku logika.pptx

6.      Torma Balázs, Müller Dávid, Tornóczky Zoltán: TormaBalazs_MullerDavid.doc  Prezentáció: TornoczkyZoltan.ppt

7.      Szücs Ádám, Verő Anita, Morvai Mihály: adatbrendszerek_tetel7_teljes.docx Prezentáció: osztott_adatb lekerd.pptx

8.      Ez a tétel még kidolgozásra vár, akinek van kedve és megcsinálja, küldje el a fenti emailcímre.  Prezentáció:

9.      Fokin Miklós, Hodosy Gábor, Tóth Tamás: Jegyzet_9.doc Prezentáció: 9. eloadas.ppt

 

Kutatási feladat (kiscsoportban) Egy implementálható algoritmust, módszert is tartalmazó cikk választása a 2014-as (VLDB, ADBIS, PODS, ICDT, EDBT, DEXA) konferenciákról vagy az ACM TDS folyóiratból

 3 fős csoportonként

                                                              i.      Egy fő implementálja az algoritmust vagy annak egy részét és bemutatja a programot    

                                                            ii.      Egy fő összefoglaló minimum 10 oldalas magyar nyelvű tanulmányt készít, a prezentáció előtt elküldi a fenti emailcímre.

                                                          iii.      Egy fő az összefoglaló alapján egy prezentációt készít, elküldi a fenti emailcímre és előadja.

 

 

Adatbázisokkal foglalkozó legrangosabb

évente megrendezett konferenciák 2014-ban:

folyóiratok:

 

A konferenciákon elhangzott cikkek keresése egyetemi IP címről:

ACM

Google tudós

ScienceDirect

vagy a szerző oldaláról is gyakran letölthető.

 

 

KUTATÁSI FELADAT:

1.      Rövid összefoglalás (absztrakt: kb. 10 mondat)

2.      Bevezetés (a vizsgált problémák közérthető megfogalmazása: kb. 2-3 oldal)

3.      Kapcsolódó munkák (a hivatkozásban milyen eredményeket értek el eddig: kb.0,5-1 oldal)

4.      Alapfogalmak (definíciók, tulajdonságok, módszerek, példák: kb. 4-5 oldal)

5.      Eredmények (megoldások, állítások, példák, futási eredmények: kb. 4-5 oldal)

6.      További kutatás terv (a cikkek alapján mit lehetne még vizsgálni, saját ötletek a folytatásra: 0.5-1 oldal, olyan formában, ahogy a szakdolgozat témabejelentőjében kell megadni)

7.      Irodalomjegyzék (0.5-1 oldal)

                                                              i.      szerző_hun.doc vagy

                                                            ii.      szerző_hun.pdf

 

ALGORITMUS:

Az algoritmus implementálása bármilyen nyelven történhet, a hatékonyabb, olvashatóbb, szebb felületű kódért több pont jár.

 

PREZENTÁCIÓ:

Powerpoint (Pdf, Prezi, stb) bemutatót kell készíteni és előadni 20 percben

A prezentáció neve szerző.ppt legyen, ahol szerző a cikk egyik szerzője és a 2014abea@gmail.com címre küldjétek el

 

A prezentációk dátuma, beosztás a félév második felében lesz.

 

Egy kiindulási beosztást én fogok megadni, de dátumot egymás között cserélhettek, ha változás van, írjátok meg nekem:

 

Prezentáció alkalmak (egy nap több csoport is sorra kerül).

 

 

2014. november 11.

- Kis Dávid, Pótári Gábor, Harazin Orsolya: From "Think Like a Vertex" to "Think Like a Graph"

-

-

 

2014. november 18.

-

-

-

 

2014. november 25.

- Herédi Zsolt, Oláh Péter, Tóth Tamás: Advanced Join Strategies for Large-Scale Distributed Computation

- Hegedűs Ferenc, Tokodi Gergely, Vass Nándor: Top-K Structural Diversity Search in Large Networks

- Kis Zoltán, Parragi Zsolt, Szabó Ádám: Distributed Graph Simulation: Impossibility and Possibility

 

2014. december 2.

- Árva Balázs, Hosszejni Darjus, Horváth Gábor: Simple, Fast, and Scalable Reachability Oracle

- Epresi Balázs, Hamar Dávid és Nádasi Zoltán: Towards Social Data Platform:Automatic Topic focused Monitor for Twitter Stream

- Hack János, Kuthi Balázs, ??? : A Partition-Based Approach to Structure Similarity Search

 

2014. december 9.

- Wei Cheng, Erőss Attila, Katona György: Fast Foreign-Key Detection in Microsoft SQL Server PowerPivot for Excel

- Menyhárt Ábrahám József, Péteri Miklós, Kováts László: An Effective Encoding Scheme for Spatial RDF Data : John Liagouris

- Peter Norbert, Gergely Szabolcs, ???: Continuous Quantile Query Processing in Wireless Sensor Networks

 

 

Minta a 2013-as prezentációkra.

 

2013. November 20.

Englert Péter, Tömösy Péter, Balassi Márton: A Data-adaptive and Dynamic Segmentation Index for Whole Matching on Time Series Tanulmány Prezentáció

Kresz Marcell, Balogh Bernadett, Cseh Tamás: Recommending XML Physical Designs for XML Databases Tanulmány Prezentáció

Botos Ádám, Beke Balázs, Balogh Szabolcs: Streaming Algorithms for kcore Decomposition Tanulmány Prezentáció

 

2013. November 27.

Pillinger János, Németh Bence, Bereczki Gábor: NeMa: Fast Graph Search with Label Similarity Tanulmány Prezentáció

Csóka Győző, Polgár Ákos, Zvara Zoltán: Computing n-Gram Statistics in MapReduce Tanulmány Prezentáció

Gyenes Csilla, Szabó Andrea, Sallai Levente: GPU-Accelerated Collocation Pattern Discovery Tanulmány Prezentáció

 

2013. December 4.

Haszpra Zsolt, Hrabovsky Marián, Kereszti Krisztián, Marczinus Dávid: Memory Efficient Minimum Substring Partitioning Tanulmány Prezentáció

Dananaj Pál, Ancsin Attila , Horváth Viktor: Query-Aware Compression of Join Results Tanulmány Prezentáció

Gergácz Dániel, Tomcsik Bence, Nagy Tamás: Spatio-Textual Similarity Joins Tanulmány Prezentáció

 

 

2013. December 11.

Kukovecz János, Szentkirályi Károly, Tverdota Dávid, Nyári István: Hybrid Storage Management for Database Systems Tanulmány Prezentáció

Hollenczer Péter, Kalmár Dániel, Németh Boldizsár: R++ -tree: an efficient spatial access method for highly redundant point data Tanulmány Prezentáció

Béleczki András; Nyilas Árpád, Zoltán Bodor: Direction-Preserving Trajectory Simplication Tanulmány Prezentáció

 

 

 

Minta, hogy 2012-ben milyen tanulmányok és prezentációk készültek:

 

  1. NOVEMBER 6. Fazakas Róbert, Maczika Száva, Rákos Rudolf: Trie-join: a trie-based method for efficient string similarity joins Trie-join.pdf MaczikaSzava_hun.pdf Trie-join.ppt Trie-join.pptx
  2. NOVEMBER 6. Pinczel Máté, Mihályi Zoltán: Highly Expressive Query Languages for Unordered Data Trees p46-abiteboul.pdf abiteboul_hun.pdf abiteboul_prez.pptx
  3. NOVEMBER 13. Bodnár István, Fodor Krisztián, Gyimesi Gábor: Effective Caching of Shortest Paths for Location-Based Services SIGMOD12_spcache.pdf Hatekony_gyorsitotar.pdf effective_shortest_paths_caching.ppsx
  4. NOVEMBER 13. Balog Péter, Sosterics Ádám, Pápai Dávid: KReach: Who is in Your Small World p1292_jamescheng_vldb2012.pdf cikk_adatb.pdf prezentacio.pptx
  5. NOVEMBER 20. Szücs Ádám, Verő Anita, Morvai Mihály: Relational Approach for Shortest Path Discovery over Large Graphs jun_gao.pdf jun_gao_hun.docx jung_gao.ppt
  6. NOVEMBER 20. Barabás Gábor, Nagy Dávid, Nemes Tamás: Supporting Top-K Item Exchange Recommendations in Large Online Communities a14-su.pdf Barabas_Nagy_Nemes_Top-k_Itemek_Kicserelese.pdf Top-k_dia.pdf
  7. NOVEMBER 27. Fokin Miklós, Hodosy Gábor, Tóth Tamás: Minuet: A Scalable Distributed Multiversion BTree ScalableDistributedMultiversionBTree.pdf BenjaminSovell_hun.pdf Benjamin_Sowell.ppt
  8. NOVEMBER 27. Torma Balázs, Müller Dávid, Tornóczky Zoltán: Muppet: MapReduceStyle Processing of Fast Data p1814_wanglam_vldb2012.pdf TormaBalazs_hun.pdf TornoczkyZoltan.pdf
  9. DECEMBER 4. Csubák Dániel, Varga Péter, Vörös Péter: The FilterPlacement Problem and its Application to Minimizing Information Multiplicity Erdos.pdf Erdos_HUN.pdf erdosprez.pdf
  10. DECEMBER 4. Balázs Barnabás Lóránt, Iván Gergő, Szalona Szandra: SimpleSQL: A Relational Layer for SimpleDB adbisCalilMello2012.pdf adbisCalilMello.pdf presentation.pdf