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.