Non-Standard Databases (CS 3202)

Lecturer: Prof. Dr. Ralf Möller

Assignment Organization: Dennis Heinrich



  1. Introduction
  2. Semistructured databases (XML, algorithms for implmeneting XPath and XQuery)
  3. Text indexing
  4. Multidimensional index structures
  5. First-n, Top-k, and Skyline-Queries
  6. Probabilistic databases
  7. Temporal Databases
  8. Data streams (window concept, incremental data processing)
  9. Approximation techniques for data stream processing
  10. From NoSQL to NewSQL databases
  11. Graph databases, approximation techniques for answering graph queries (not in WS16/17)
  12. Spatio-temporal index data structures (not in WS16/17)
  13. Provenance, anonymization, compression techniques (not in WS16/17)

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/17/2016

Start tutor meeting: 10/28/2016


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


  • Introduction to Logic

Qualification Goals / Competences:


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.


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.


  • 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
  • C. J. Date, H. Darwen, N.A. Lorentzos, Time and Relational Theory: Temporal Databases in the Relational Model and SQL, Morgan Kaufmann, 2014 
  • 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