Loop Restricted Patterns and First-order Rewritable Existential Rules in Query Answering

Speaker:        Prof. Yan Zhang
                Western Sydney University
                Australia

Title:          "Loop Restricted Patterns and First-order Rewritable
                 Existential Rules in Query Answering"

Date:           Friday, 1 February 2019

Time:           11:00am - 12 noon

Venue:          Room 3520 (CSE Conference Room, via lift 25/26), HKUST

Abstract:

In ontology-based data access (OBDA), the classical database is enhanced
with an ontology in the form of logical assertions generating new
intensional knowledge. A powerful form of such logical assertions is the
tuple-generating dependencies (TGDs), also called existential rules,
where Horn rules are extended by allowing existential quantifiers to
appear in the rule heads.

In this paper we introduce a new language called loop restricted (LR) TGDs
(existential rules), which are TGDs with certain restrictions on the loops
embedded in the underlying rule set. We study the complexity of this new
language. We show that the conjunctive query answering (CQA) under the LR
TGDs is decidable. In particular,  we prove that this language satisfies
the well-known bounded derivation-depth property (BDDP), which also
implies that the CQA is first-order rewritable, and its data complexity is
in AC0. We further show that the class of LR TGDs properly contains most
of currently known first-order rewritable TGD classes, from which we argue
that loop restricted pattern is a useful notion to characterize the
feature of first-order rewritability of TGDs in ontological query
answering.


***********************
Biography:

Yan Zhang is a professor of Western Sydney University, Australia, where he
leads the Artificial Intelligence Research Group (AIRG). Yan's research
interests include knowledge representation and reasoning, model checking
and update, and information security. Over the years, he has made a number
of original contributions in answer set programming, and knowledge and
model update. In recent years he has been focusing his study on ontology
based reasoning and query answering under complex domains, and applying
his research discoveries in Blockchain technology.