TUWIEN f-hybrid Knowledge Bases

From ONTORULE Show Case

Overview

f-hybrid knowledge bases is a tightly-coupled formalism which combines SHOQ ontologies with Forest Logic Programs (FoLPs). The integration of the two formalisms is achieved via a translation from SHOQ ontologies to FoLPs which preserves concept/unary predicates satisfiability.

FoLPs is a decidable fragment of the rule-based formalism Open Answer Programming (OASP), which at its turn is an extension of (unsafe) Answer Set Programming (ASP) with open domains. The syntax of OASP is identical to the ASP syntax, but the semantics is different: an open answer set is a "parametrized model", where the parameter is the domain of interpretation. More concretely, an open answer set of an OASP program P is a tuple (U, M), where U is a superset of the set of constants in the program, and M is a regular answer set of the program P grounded with U. In the general case OASP is undecidable. FoLPs achieve decidability by restricting the shape of rules which can appear in a program: rules have a so-called "tree" shape which translates in the fact that the fragment has the forest model property.

Example

The following program is a FoLP which says that somebody is a special member of an organization if it is supported by at least two regular members and that somebody is a regular member if it is involved in some project.

The program has a forest-shaped open answer set as in the figure below, where nodes in the forest are elements of the universe, and labels of nodes/arcs indicate which atoms are part of the model. For example: smember(x) is part of the model as "smember" is in the label of node x and supportedBy(x,y) is part of the model as "supportedBy" is in the label of arc (x, y).

Technical Work

During the course of the project we developed reasoning algorithms for FoLPs. As reasoning with f-hybrid KBs can be reduced to reasoning with FoLPs, these algorithms can also be employed for reasoning with f-hybrid KBs.

Deliverable D3.2 describes a non-optimal algorithm for reasoning with FoLPs which runs in the worst case in double exponential time. Being the first algorithm for reasoning with the fragment, it also established the decidability result.

Deliverable D3.3 describes an optimization for reasoning with FoLPs based on a knowledge compilation technique: the set of all possible building blocks of a model called Unit Completion Structures (UCSs) is precomputed and a notion of redundant UCSs is defined. The new algorithm uses only the set of nonredundant UCSs. While it is expected that this algorithm has better running times than the original one, the worst case complexity does not decrease.

Deliverable D3.4 introduces an optimal algorithm for reasoning with the fragment. The algorithm uses new termination conditions, in particular, a new redundancy rule and a caching rule. The worst case running time descreased one exponential level and it is now exponential. As reasoning with FoLPs was known to be an EXPTIME-hard problem, it follows that it is actually EXPTIME-complete.