This extended abstract summarizes our recent study [4] of existential rules with closed predicates and active-domain semantics.
The vast majority of work on ontology-mediated query answering (OMQA) adopts the open world assumption, whereby facts that are not present in the data instance are treated as unknown. Formally, each knowledge base (KB) (R; I), consisting of an ontology R and data instance I, give rise to a set of models, de ned as the rst-order structures that make true all facts in I and satis es all rules (or axioms) in R. When querying a KB, we are interested in the certain answers that hold for every model of the KB. By contrast, relational databases make the closed-world assumption, where each instance I is interpreted as the nite structure whose domain is the active domain of I (i.e., the constants explicitly mentioned in I) and which makes true precisely the facts in I.
In practice, it seems natural to assume that applications may involve some
predicates whose contents are fully known and others for which we have only
partial information. This motivates the consideration of mixed-world semantics,
where the set of predicates is partitioned into closed and open predicates, and
models are required to coincide with the instance on the closed predicates.
Mixedworld OMQA was rst explored for description logic (DL) ontologies [10{12] and
has only recently been studied for existential rules [
The research summarized here combines elements of these di erent lines of research by exploring OMQA with existential rules under a hybrid mixed-world active-domain semantics, in which we can use both closed and open predicates, and the semantics is based upon active-domain models whose domains are equal to the active domain of the instance. Such a semantics is appropriate for scenarios in which all relevant constants are made available in the instance. A possible use case, which served as a motivation for our work, is in analyzing the trajectories of people circulating in a geographically restricted area (e.g., industrial facility, closed medical facility) that is equipped with captors and secure entry and exit (so that the set of people in the area is known at each timepoint).
Meghyn Bienvenu and Pierre Bourhis
We have analyzed the data complexity of three central reasoning tasks in this
setting which are to determine whether a mixed-world knowledge base (MWKB)
is satis able, and whether a Boolean conjunctive query (BCQ) is certain or
possible w.r.t. a MWKB (the latter can be equivalently viewed as determining whether
a BCQ is not certainly false). We show that all three tasks are intractable
(NPor coNP-complete in data complexity) for MWKBs based upon arbitrary
existential rules. This is unsurprising in light of previous negative results obtained
for querying lightweight DL ontologies with closed predicates [
Motivated by these encouraging results, we investigate the linear fragment in more detail. It is a well-known result in descriptive complexity that semipositive Datalog (i.e., Datalog rules that may use negated extensional atoms in their bodies) captures all PTIME queries over ordered instances with min and max, i.e., instances I with a binary predicate Succ providing a successor relation among all constants in adom(I), and unary predicates M in and M ax containing the smallest and largest constants. We study the expressive power of the linear fragment and prove our most technically challenging result, namely, that atomic queries coupled with mixed-world linear existential rules, extended with either closed negated atoms or disjunctive ruleheads and interpreted under either certain or possible active-domain semantics, can express all PTIME queries over ordered instances (we do not require min and max to be given as input, as we can compute them from the Succ relation).
While the (extended) linear fragment has desirable computational properties, it cannot express some useful constructs, such as functionality. To broaden its applicability, we introduce a general method of approximating unrestricted existential rules by means of linear rules, which roughly works as follows. Given an arbitrary ruleset, we can rst compute the certain and possible facts using only its linear rules, which yields a subset of the `true' certain facts and a superset of the possible ones. We store these facts in new closed predicates linked by rules to the original open predicates, create new linear rules from the non-linear rules by replacing all open atoms but one with one with a closed atom (using the new closed predicates), then recompute the certain and possible facts. Iterating this process until xpoint allows us to obtain more re ned approximations of the certain and possible facts of the original ruleset.
We envision several continuations to this work, including: studying the combined complexity and the impact of using a xed but succinctly represented domain, further exploring the expressive power of di erent fragments, and developing and implementing e cient PTIME algorithms for the linear fragment (avoiding the construction of full maximal models).