Constructive Reasoning for Semantic Wikis

One of the main design goals of social software, such as wikis, is
to support and facilitate interaction and collaboration. This
dissertation explores challenges that arise from extending social
software with advanced facilities such as reasoning and semantic
annotations and presents tools in form of a conceptual model,
structured tags, a rule language, and a set of novel forward
chaining and reason maintenance methods for processing such rules
that help to overcome the challenges. Wikis and semantic wikis were
usually developed in an ad-hoc manner, without much thought about
the underlying concepts. A conceptual model suitable for a semantic
wiki that takes advanced features such as annotations and reasoning
into account is proposed. Moreover, so called structured tags are
proposed as a semi-formal knowledge representation step between
informal and formal annotations. The focus of rule languages for
the Semantic Web has been predominantly on expert users and on the
interplay of rule languages and ontologies. KWRL, the KiWi Rule
Language, is proposed as a rule language for a semantic wiki that
is easily understandable for users as it is aware of the conceptual
model of a wiki and as it is inconsistency-tolerant, and that can
be efficiently evaluated as it builds upon Datalog concepts. The
requirement for fast response times of interactive software
translates in our work to bottom-up evaluation (materialization) of
rules (views) ahead of time – that is when rules or data change,
not when they are queried. Materialized views have to be updated
when data or rules change. While incremental view maintenance was
intensively studied in the past and literature on the subject is
abundant, the existing methods have surprisingly many disadvantages
– they do not provide all information desirable for explanation of
derived information, they require evaluation of possibly
substantially larger Datalog programs with negation, they recompute
the whole extension of a predicate even if only a small part of it
is affected by a change, they require adaptation for handling
general rule changes. A particular contribution of this
dissertation consists in a set of forward chaining and reason
maintenance methods with a simple declarative description that are
efficient and derive and maintain information necessary for reason
maintenance and explanation. The reasoning methods and most of the
reason maintenance methods are described in terms of a set of
extended immediate consequence operators the properties of which
are proven in the classical logical programming framework. In
contrast to existing methods, the reason maintenance methods in
this dissertation work by evaluating the original Datalog program –
they do not introduce negation if it is not present in the input
program – and only the affected part of a predicate’s extension is
recomputed. Moreover, our methods directly handle changes in both
data and rules; a rule change does not need to be handled as a
special case. A framework of support graphs, a data structure
inspired by justification graphs of classical reason maintenance,
is proposed. Support graphs enable a unified description and a
formal comparison of the various reasoning and reason maintenance
methods and define a notion of a derivation such that the number of
derivations of an atom is always finite even in the recursive
Datalog case. A practical approach to implementing reasoning,
reason maintenance, and explanation in the KiWi semantic platform
is also investigated. It is shown how an implementation may benefit
from using a graph database instead of or along with a relational
database.