Foundations of Data and Knowledge Bases

Nowadays we need to deal with data that is very large, heterogeneous, distributed in different sources, and incomplete. At the same time, we have very large amounts of knowledge about the application domain of the data in the form of ontologies that can be used to provide end users with flexible and integrated access to data. This gave rise to knowledge-enriched databases, which lie at the intersection of traditional databases and symbolic Artificial Intelligence (in particular, knowledge representation and reasoning). The purpose of the course is to introduce students to the principles of knowledge-enriched databases and demonstrate how logic can be used for reasoning over data, as well as the implications of such studies for real-life applications such as reasoning over knowledge graphs, ontology-based data integration, and many more.
Course Description:
Towards the main goal of the course, it is vital to first cover the principles of relational databases, without taking ontologies into account, on top of which the principles of knowledge-enriched databases are built. In particular, the course will cover the following topics:
· Relational model: data model, relational algebra, relational calculus (first-order queries), first-order query evaluation, static analysis of first-order queries.
· Conjunctive queries (CQs): syntax and semantics (via homomorphisms), CQ evaluation, static analysis of CQs (satisfiability, containment and the Homomorphism Theorem), minimization of CQs.
· Fast CQ evaluation: acyclic CQs, evaluating acyclic CQs (Yannakakis' algorithm), semantically acyclic CQs and their evaluation, size bounds for joins (AGM bound), worst-case optimal join algorithms.
· Adding recursion - Datalog: inexpressibility of recursive queries, syntax and semantics of Datalog, Datalog query evaluation, static analysis of Datalog queries.
· Knowledge-enriched databases: rule-based ontologies (syntax and semantics), combining relational databases with rule-based ontologies, ontological query answering (OQA), universal models, reasoning over knowledge graphs, ontology-based data integration.
· Ontological query answering: forward-chaining (the chase procedure), backward-chaining (resolution-based query rewriting), linear rule-based ontologies.
· Advanced topics (time permitting): expressive rule-based ontology languages, chase termination, static analysis of ontological queries