Theory of Data and Knowledge Bases

Aims and Prerequisites

The aim of this series of lectures is to provide an understanding of the logical foundations of database query languages and knowledge representation formalisms, of their expressive power, and the complexity query-answering and reasoning with such languages/formalisms. No previous knowledge on databases/AI is required. The course will be self-contained, but basic knowledge on automata theory (e.g., finite state automata), databases (e.g., the relational data model, relational algebra, SQL), and complexity theory (e.g., NP-completeness) does not harm.

Outcomes

By the end of this lecture series you should have a good understanding of the fundamentals of query languages, understand the trade-off between complexity and expressive power of query languages, and understand some basic formalisms of non-monotonic reasoning. You should be in the position of analyzing a query language and expressing knowledge in suitable logical formalisms.