Antoine Amarilli (Télécom Paris) will give a talk on October 20th, 2 pm, at Salle Thomas Flowers, Turing Building.
Abstract
The query answering problem, also called entailment or certain answer problem, is a fundamental reasoning problem in knowledge representation and databases. It asks whether a conjunctive query is always certain given incomplete data and logical constraints, i.e., whether all completions of the data that satisfy the constraints must also satisfy the query; it amounts to the negation of the satisfiability problem for the data, the constraints, and the negation of the query.
While this problem is undecidable for general TGDs or FO constraints, existing work has studied logical fragments for which it is decidable and has lower complexity, in particular the guarded paradigm, i.e., (frontier-)guarded TGDs and the guarded (negation) fragment of FO, based on restricting the shape of rules and of quantification. Yet, the guardedness paradigm cannot express many constraints that are important in practice to reason about data: transitivity (e.g., reachability), number restrictions (e.g., functional dependencies), and order relations (e.g., on numbers).
This talk will review our work (presented at IJCAI’15 and IJCAI’16) about extending guarded rules and logics to express such constraints, and its effect on the decidability and complexity of QA.
