Interessierten Studierende mit entsprechenden Vorkenntnissen soll ein vertiefter Zugang zu speziellen Fragestellungen der Datenbanktheorie und der Artificial Intelligence (AI) geboten werden. Unter anderem sollen profunde Kenntnisse der Zerlegungstheorie für Datenbankabfragen und Constraint-Satisfaction-Probleme erworben werden. Studierende, die diese LVA besuchen, sollen Kenntnisse über den letzten Stand der Literatur zu diesem Thema und zu anderen ausgewählten Kapiteln der Datenbanktheorie und der AI erlangen. Diese LVA kann Studierenden daher auch zur Vorbereitung auf das Wissenschaftliche Arbeiten und als Anregung für Dissertationsthemen zugutekommen.

• 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

Wird in Sommersemestern im Anschluss an die LVA ¿Datenbanktheorie¿ abgehalten und ist mit dem Leiter dieser LVA (Prof. Reinhard Pichler) koordiniert.

Die LVA-Unterlagen sind unter folgendem Link zum downloaden:

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

Übungen und schriftliche Prüfung. 

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