Constructive Reasoning for Semantic Wikis [Elektronische Ressource] / Jakub Kotowski. Betreuer: Francois Bry

Jakub Kotowski

Sujets

• Informatik

Informations

• Publié par: ludwig-maximilians-universitat_munchen
• Publié le: 01 janvier 2011
• Nombre de lectures: 92
• Langue: English
• Poids de l'ouvrage: 5 Mo

Extrait

C O N S T R U C T I V E R E A S O N I N G F O R S E M A N T I C W I K I S
jakub kotowski
Dissertation an der Fakultät für Mathematik, Informatik und Statistik der
Ludwig-Maximilians-Universität, München
Oktober 2011C O N S T R U C T I V E R E A S O N I N G F O R S E M A N T I C W I K I S
jakub kotowski
Dissertation an der Fakultät für Mathematik, Informatik und Statistik der
Ludwig-Maximilians-Universität, München
Oktober 2011
Erster Berichterstatter: Prof. Dr. François Bry
Ludwig-Maximilians-Universität München
Zweiter Prof. Dr. Peter Dolog
Aalborg University
Datum der Disputation: 18. Oktober 2011A B S T R A C T
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 mainte-
nance 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 con-
ceptual model suitable for a semantic wiki that takes advanced features
such as annotations and reasoning into account is proposed. More-
over, so called structured tags are proposed as a semi-formal knowl-
edge representation step between informal and formal annotations.
The focus of rule languages for the Semantic Web has been pre-
dominantly 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 inten-
sively 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 exten-
sion 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 declar-
ative description that are efficient and derive and maintain informa-
tion necessary for reason maintenance and explanation. The reason-
ing methods and most of the reason maintenance methods are de-
scribed 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
vmethods in this dissertation work by evaluating the original Datalog
program – they do not introduce negation if it is not present in the in-
put 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 justifi-
cation 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 no-
tion 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.
Z U S A M M E N FA S S U N G
Ein vorrangiges Designziel von sozialer Software, wie zum Beispiel
Wikis, ist es, die Interaktion und Zusammenarbeit zu unterstützen
und zu erleichtern. Diese Dissertation untersucht Herausforderun-
gen, die beim Anreichern von sozialer Software mit fortgeschritte-
nen Funktionen, wie dem Schließen und semantischen Annotationen,
entstehen, und stellt Hilfsmittel in Form eines konzeptuellen Modells,
strukturierten Tags, einer Regelsprache und einer Menge von neuarti-
gen Methoden zum Vorwärtsschließen und zur Begründungsverwal-
tung zur Verarbeitung solcher Regeln zur Verfügung, um diese Her-
ausforderungen zu meistern.
Wikis und semantische Wikis wurden üblicherweise nach einem
Ad-Hoc-Ansatz entwickelt, ohne sich über die darunterliegenden Kon-
zepte Gedanken zu machen. Es wird ein für semantische Wikis geei-
gnetes konzeptuelles Modell vorgeschlagen, welches fortgeschrittene
Funktionen wie Annotationen und Schließen berücksichtigt. Darüber-
hinaus werden sog. strukturierte Tags als semi-formales Bindeglied
zwischen informalen und formalen Annotationen vorgeschlagen. Re-
gelsprachen des Semantic Web waren bisher hauptsächlich auf die
Benutzung durch Experten und das Zusammenspiel mit Ontologien
ausgerichtet. KWRL, die KiWi Rule Language, ist ein Vorschlag einer
für den Benutzer leicht verständlichen Regelsprache für ein semantis-
ches Wiki, da sie das konzeptuelle Modell eines Wikis berücksichtigt
und Inkonsistenzen toleriert. Da sie auf Konzepten von Datalog auf-
baut, ist sie zudem effizient auswertbar.
viDer Anforderung an schnelle Antwortzeiten von interaktiver Soft-
ware wird in unserer Arbeit durch eine vorzeitige Bottom-Up-Aus-
wertung (Materialisierung) von Regeln (Sichten) entsprochen – d.h.
wenn sich Regeln oder Daten ändern, und nicht erst wenn sie ange-
fragt werden. Materialisierte Sichten müssen aktualisiert werden, so-
bald sich Daten oder Regeln ändern. Während "Incremental View
Maintenance" intensiv in der Vergangenheit studiert wurde und es
reichlich Literatur dazu gibt, haben die existierenden Methoden über-
raschenderweise viele Nachteile – sie liefern nicht all die Information,
die für die Erklärung der hergeleiteten Informationen wünschenswert
wäre, sie erfordern die Auswertung von unter Umständen erheblich
größeren Datalog Programmen mit Negation, sie berechnen die voll-
ständige Erweiterung eines Prädikats selbst wenn nur ein kleiner Teil
davon von einer änderung betroffen ist, und sie müssen angepasst
werden, um allgemeine Regeländerungen verarbeiten zu können.
Ein Beitrag dieser Dissertation besteht in einer Menge von Meth-
oden zum Vorwärtsschließen und zur Begründungsverwaltung mit
einer einfachen deklarativen Beschreibung, welche effizient sind und
die zur Begründungsverwaltung und Erklärung notwendigen Infor-
mationen ableiten und bereithalten. Die Methoden zum Schließen
und die meisten der Methoden zur Begründungsverwaltung werden
in Form einer Menge von erweiterten, unmittelbaren Folgerungsop-
eratoren beschrieben, deren Eigenschaften im Rahmen der klassis-
chen Logikprogrammierung bewiesen werden. Im Gegensatz zu den
bereits existierenden Methoden der Begründungsverwaltung, funk-
tionieren die Methoden dieser Dissertation durch Auswertung des
ursprünglichen Datalog Programmes – es wird keine Negation einge-
führt, wenn diese nicht schon im Eingabeprogramm vorhanden war –
und nur der von einer Prädikatserweiterung betroffene Teil wird neu
berechnet. Darüberhinaus werden änderungen in Daten sowohl als
auch Regeln direkt durch unser Verfahren behandelt; eine Regelän-
derung stellt also keinen Spezialfall dar.
Weiterhin wird das Konzept von Support Graphen vorgeschlagen,
einer von den Rechtfertigungsgraphen der klassischen Begründungs-
verwaltung inspirierten Datenstruktur. Diese ermöglichen eine ein-
heitliche Beschreibung und formale Gegenüberstellung der verschiede-
nen Methoden zum Schließen und zur Begründungsverwaltung und
definieren einen Begriff einer Herleitung, derart dass die Anzahl der
Herleitungen eines Atoms immer endlich ist, selbst im Falle von rekur-
sivem Datalog.
Auch wird in der semantischen Plattform von KiWi ein praktis-
cher Ansatz zur Implementierung des Schließens, der Begründungs-
verwaltung und Erklärung untersucht. Es wird gezeigt, wie eine Im-
plementierung von einer Graphdatenbank anstelle oder in Ergänzung
zu einer relationen Datenbank profitieren kann.
viiP U B L I C AT I O N S
Some ideas and figures have appeared previously in the following publica-
tions:
Jakub Kotowski, François Bry, and Norbert Eisinger. A Potpourri of Reason
Maintenance Methods.