This course aims at giving interested students who have an appropriate background deep insights into special research topics in database theory and artificial intelligence (AI). In particular, students are expected to acquire expertise in the decomposition theory for database queries and constraint satisfaction problems. They should get acquainted with state-of-the art results and with the latest papers on this topic and on some other selected topics in the area of database theory and AI. For students intending to enrol in a doctoral program, this course may therefore also be of use as an introduction into scientific work, and as a possible stimulus towards the selection of a research topic for doctoral studies.

• Conjunctive queries, the constraint satisfaction problem (CSP) and the homomorphism problem.
• NP-hard and tractable classes of queries
• Degrees of query acyclicity and characterizations of alpha-acyclicity
• Complexity of evaluating alpha-acyclic queries and CSP instances
• Tree decomposition of graphs and queries; critique of tree decompositions
• Generalized hypertree decompositions and hypertree decompositions
• Fractional covers and fractional hypertree decompositions
• Submodular decompositions
• Complexity results for various types of decompositions
• Minimal and trobust constraint satisfaction poblems
• Datalog and its extensions; elements of Datalog+/-
• Complexity and expressive power of various query languages

Held in summer semester subsequent to and building on the "Datenbanktheorie" lecture by Prof. Reinhard Pichler.

The lecture slides are now available and can be downloaded under the following link:

https://www.dropbox.com/sh/zxo2rxongym2wya/AAC6SmsZwOkHFP4H0vCfrLFwa?dl=0

Excercises and written exam.

The lecture slides will be made available to the students.

The lecture slides can be downloaded under the following link:

https://www.dropbox.com/sh/zxo2rxongym2wya/AAC6SmsZwOkHFP4H0vCfrLFwa?dl=0

Books: Relevant chapters will be indicated during the course

• David Maier: The Theory of Relational Databases, 1983, online version available at: http://web.cecs.pdx.edu/~maier/TheoryBook/TRD.html

• Ceri, Gottlob, Tanca: Logic Programming and Databases, Springer, 1990.

Papers (tentative list) - electronic versions will be made available:

• Ronald Fagin: Degrees of Acyclicity for Hypergraphs and Relational Database Schemes. J. ACM 30(3): 514-550 (1983)
• Georg Gottlob, Nicola Leone, Francesco Scarcello: The complexity of acyclic conjunctive queries. J. ACM 48(3): 431-498 (2001)
• Georg Gottlob, Gianluigi Greco, Nicola Leone, Francesco Scarcello: Hypertree Decompositions: Questions and Answers. PODS 2016: 57-74
• Georg Gottlob, Nicola Leone, Francesco Scarcello: Hypertree Decompositions and Tractable Queries. J. Comput. Syst. Sci. 64(3): 579-627 (2002)
• Georg Gottlob, Nicola Leone, Francesco Scarcello: A comparison of structural CSP decomposition methods. Artif. Intell. 124(2): 243-282 (2000)
• Albert Atserias, Martin Grohe, Dániel Marx: Size Bounds and Query Plans for Relational Joins. SIAM J. Comput. 42(4): 1737-1767 (2013)
• Martin Grohe, Dániel Marx: Constraint Solving via Fractional Edge Covers. ACM Trans. Algorithms 11(1): 4:1-4:20 (2014)
• Dániel Marx: Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries. J. ACM 60(6): 42 (2013)
• Andrea Calì, Georg Gottlob, Thomas Lukasiewicz: A general Datalog-based framework for tractable query answering over ontologies. J. Web Sem. 14: 57-83 (2012)
• Andrea Calì, Georg Gottlob, Michael Kifer: Taming the Infinite Chase: Query Answering under Expressive Relational Constraints. J. Artif. Intell. Res. (JAIR) 48: 115-174 (2013)
• Andrea Calì, Georg Gottlob, Andreas Pieris: Towards more expressive ontology languages: The query answering problem. Artif. Intell. 193: 87-128 (2012)
• Georg Gottlob: On minimal constraint networks. Artif. Intell. 191-192: 42-60 (2012) 
• Samson Abramsky, Georg Gottlob, Phokion G. Kolaitis: Robust Constraint Satisfaction and Local Hidden Variables in Quantum Mechanics. IJCAI 2013: 440-446