Titelaufnahme

Titel
Efficient problem solving based on datalog transformations / von Christoph Singewald
VerfasserSingewald, Christoph
Begutachter / BegutachterinPichler, Reinhard ; Jakl, Michael
Erschienen2008
Umfang81 Bl. : graph. Darst.
HochschulschriftWien, Techn. Univ., Dipl.-Arb., 2008
Anmerkung
Zsfassung in dt. Sprache
SpracheEnglisch
DokumenttypDiplomarbeit
Schlagwörter (DE)Datalog / Transformation / SAT / effizient / problem / lösen / monadic / dlv
Schlagwörter (EN)datalog / transformation / sat / efficient / problem / solving / monadic / dlv
URNurn:nbn:at:at-ubtuw:1-25540 Persistent Identifier (URN)
Zugriffsbeschränkung
 Das Werk ist frei verfügbar
Dateien
Efficient problem solving based on datalog transformations [0.64 mb]
Links
Nachweis
Klassifikation
Zusammenfassung (Deutsch)

Viele interessante algorithmische Probleme in der Computerwissenschaft können im Allgmeinen nur mit hohem Aufwand auf einer Rechenmaschine gelöst werden.

In diesem Zusammenhang sind in den letzten Jahren parametrisierbare Probleme immer wichtiger geworden. Es konnte gezeigt werden, dass viele harte Probleme effizient lösbar werden, wenn ein Parameter durch eine Konstante begrenzt ist. Besitzt ein Problem diese Eigenschaft, bezeichnet man es als fixedparameter- lösbar (engl. fixed-parameter tractable). Bei Problemen aus dem Bereich der Graphentheorie ist die Baumweite (engl. treewidth) ein solcher Parameter.

Aufgrund des Courcelle'schen Theorems wissen wir, dass sämtliche Grapheigenschaften, die sich mittels Monadic Second Order Logic (MSO) ausdr ücken lassen, auf Graphen mit beschränkter Baumweite effizient entscheidbar sind. Gottlob et al. haben vor kurzem Monadisches Datalog (jedes Prädikat ist einstellig) über Strukturen mit beschränkter Baumweite als Alternative zu (MSO) vorgeschlagen. Dieser Ansatz sieht theoretisch vielversprechend aus.

Eine praktische Evaluierung war aber bislang ausständig. Im Rahmen dieser Diplomarbeit wurde der Prozess zur allgemeinen Verarbeitung - vom zugrunde liegenden Problem unabhängig - dieser Datalogregeln implementiert. Am Beispiel des Programms SAT wurde die automatische Transformation von Monadischem Datalog in "normales" Datalog für die verwendeten Datalog Interpreter (DLV, DLV Complex und DLV Complex mit externem Prädikat) durchgeführt und die Applikation mit unterschiedlichen Parametern ausführlich getestet. Als Ergebnis konnte gezeigt werden, dass dieser Ansatz ein großes Potential hat und mit Hilfe von allgemeinen Datalog Interpretern realisiert werden kann. Zudem hat sich herausgestellt, dass dieses Thema noch viel Potential zur Verbesserung bietet.

Zusammenfassung (Englisch)

Many interesting algorithmic problems in computer science are well known to be intractable and solvable only with high computational effort. In the recent years parameterized complexity as a new paradigm came up and is getting more and more important. It has turned out that many hard (intractable) problems become tractable if some problem parameter is fixed or bounded by a fixed constant.

Problems having such a property are called fixed-parameter tractable (FPT). In case of graph problems the treewidth of a graph is such a constant parameter. By Courcelle's Theorem, we know that all graph properties expressible in Monadic Second Order Logic (MSO) can be efficiently decided on graphs with bounded treewidth. Gottlob et al. have recently proposed monadic datalog (i.e., all intensional predicates are unary) over structures with bounded treewidth as an alternative to Monadic Second Order Logic (MSO). This approach looks theoretically very promising. However, a practical evaluation has been missing so far.

In this thesis we implement an evaluation process for datalog rules abstracted from the underlying problem. Using the example of the program SAT we implemented the automatic transformation from monadic datalog to "normal" datalog for the used datalog engine (DLV, DLV Complex and DLV Complex with external predicate) and tested our application with various parameters. As a result we could show that this approach is feasible, has (a lot of) potential and can be implemented using a generic datalog system. Further more we discovered that there is room for further improvements.