Non-Standard Databases (CS 3202)

Lecturer: Prof. Dr. Ralf Möller

Assignment Organization: Marc Stelzner

Tutors: Raphael Allner, Lina Schad

Content:

  1. Introduction
  2. Semistructured databases (XML, algorithms for implmeneting XPath and XQuery)
  3. Text indexing, similarity retrieval (k-nearest-neigbor queries, top-k queries)
  4. Spatial, and multimodal databases (multidimensional index structures)
  5. Impact of modern hardware on databases, In-memory databases
  6. Temporal Databases
  7. Data streams (window concept, approximation
  8. Probabilistic databases
  9. First-n and Top-k queries

Credits: 2 hours/week class, 1 hour/week lab class and meeting with tutor, in total 4 ETCS

Time and Location:

  • Class: Mondays 2:15-4:00 pm, Lecture Hall V1
  • Tutor meeting 1: Fridays 8:15-9:00 am, IFIS Room 2035
  • Tutor meeting 2: Fridays 9:15-10:00 am, IFIS Room 2035

Start lecture: 10/20/2014

Start tutor meeting: 10/27/2014

Prerequisites:

  • Algorithms and Data Structures
  • Linear Algebra and Discrete Structures 1
  • Databases
  • Theoretical Computer Science (context-free grammars)
  • Stochastics or Biostatistics

Advantageous:

  • Introduction to Logic

Qualification Goals / Competences:

Knowledge

Students can name the main features of standard databases and, in addition, can explain which non-standard database models emerge if features are dropped. They can describe the main ideas behind non-standard databases presented in the course by explaining the main features of respective query languages (syntax and semantics) as well as the most important implementation techniques used for their practical realization.

Skills

Students can apply query languages for non-standard data models introduced in the course to retrieve desired structures from sample datasets in order to satisfy information needs specified textually in natural language. Students are able to represent data in the relational data model using encoding techniques presented in the course such that they can demonstrate how new formalisms relate to or can be implemented in SQL (in particular, SQL-99). In case an SQL transformation cannot be found, students can explain and apply dedicated algorithms for query answering. Students can demonstrate how index structures help answering queries fast by showing how index structures are built, updated, and exploited for query answering. The participants of the course can derive query answers by evaluating queries step by step and by deriving optimized query execution plans.

Social skills

Students work in teams to handle assignments, and they are encouraged to present their solution to other students in small presentations (in lab classes). In addition, self-dependence is fostered by giving pointers to query evaluation engines for various formalism presented in the lecture such that students get familiar with data models and query languages by self-controlled work.

Bibliography:

  • A.U. Tansel, J. Clifford, S. Gadia, S. Jojodia, A. Segev, R. Snodgrass, Temporal Databases: Theory, Design, and Implementation, Benjamin Cummings Publishing Company, 1993
  • J. Chomicki, G. Saake (Eds.), Logics for Databases and Information Systems, Springer, 1998
  • S. Abiteboul, P. Buneman, D. Suciu, Data on the Web - From Relations to Semistructured Data and XML, Morgan Kaufmann, 1999
  • P. Rigaux, M. Scholl, A. Voisard, Spatial Databases With Applications to GIS, Morgan Kaufmann, 2001
  • P. Revesz, Introduction to Constraint Databases, Springer, 2002
  • S. Chakravarthy, Q. Jiang, Stream Data Processing A Quality of Service Perspective, Springer, 2009
  • P. Revesz, Introduction to Databases- From Biological to Spatio-Temporal, Springer 2010
  • D. Suciu, D. Olteanu, Chr. Re, Chr. Koch, Probabilistic Databases, Morgan & Claypool, 2011
  • S. Ceri, A. Bozzon, M. Brambilla, E. Della Valle, P. Fraternali, S. Quarteroni, Web Information Retrieval, Springer, 2013