Logic and XML

Thomas Schwentick, Philipps-Universität Marburg, Germany

The advent of XML processing languages raises the question whether there are good logical foundations for XML querying tasks as they are established for the theory of relational databases. The talk gives a couple of examples of the application of logics to the theory of XML query languages and concludes with some recent results on two-variable logics with data comparisons.

---

Database repairing by means of updates

Jef Wijsen, Université de Mons-Hainaut, Belgium

Repairing a database means bringing the database in accordance with a given set of integrity constraints by applying some minimal change. In general, this results in multiple possible repairs, and hence multiple possible answers to a given query. The consistent answer to a query consists of the tuples that are in all possible query answers.

Earlier approaches have confined the repair work to deletions and insertions of entire tuples. We propose a theoretical framework that also covers updates as a repair primitive. Update-based repairing is interesting because it allows rectifying an error within a tuple without deleting the tuple, thereby preserving its consistent components. Another novel idea is the construct of nucleus: a single database that yields consistent answers to a class of queries, without the need for query rewriting.

Consistent query answering and constructing nuclei is generally intractable under update-based repairing. Nevertheless, we also distinguish some tractable cases of practical interest.

---

The role of deontic logic in Multi-Agent Systems

Frank Dignum, Universiteit Utrecht, The Netherlands

Deontic logic has a long philosophical tradition. It has been used to formally specify norms and laws and reason about different aspects of norms in our society. Since the beginning of the 90's deontic logic has also been used in computer science in order to reason about incorrect behaviour of programs and about normative aspects of programs that are not under the direct control of the designer and/or user. With the advent of MAS research the normative aspects of computer systems has become more and more important. I will show what the role of deontic logic is in this research both for the theory as well as for practice.

---

Deciding static properties of XPath expressions

Jan Hidders, Universiteit Antwerpen, Belgium

In the first part of this talk we discuss the problem of finding a sound and complete rule set for determining whether sorting and duplicate removal operations in the query plan of XPath expressions are unnecessary. Additionally we define a deterministic infinite automaton that illustrates how these rules can be translated into an efficient algorithm. This work is an important first step in the understanding and tackling of XPath/XQuery optimization problems that are related to ordering and duplicate removal.

In the second part of this talk we investigate the complexity of deciding the satisfiability of XPath 2.0 expressions, i.e., whether there is an XML document for which their result is nonempty. Several fragments that allow certain types of expressions are classified as either in PTIME or NP-hard to see which type of expression make this a hard problem. Finally, we establish a link between XPath expressions and partial tree descriptions which are studied in computational linguistics.

---

Logic Programs with Annotated Disjunctions

Joost Vennekens, K.U. Leuven, Belgium

The domain of probabilistic logic programming deals with the problem of integrating probability theory and logic programming. In this talk, we take a look at this problem from a knowledge representation point of view, i.e., we consider the questions of what kind of knowledge one would like to represent in such a formalism and how such knowledge can be given a natural representation.

Concretely, our discussion will focus on the probabilistisc logic programming formalism of ``Logic Programs with Annotated Disjunctions''. After defining its syntax and semantics, we discuss several interesting properties of this language, which clarify its use as a knowledge representation formalism. We discuss which kinds of problems this language seems most suitable for and briefly present some thoughts on how a langauge such as this could fit into a larger knowledge representation system.

---

Probabilistic Logic Learning

Luc De Raedt, Albert-Ludwigs-Universität Freiburg, Germany

Probabilistic inductive logic programming (sometimes also called statistical relational learning) addresses one of the central questions of artificial intelligence: the integration of Probabilistic reasoning with first order Logic representations and machine Learning.

In this talk, I shall start from an inductive logic programming perspective and sketch how it can be extended with probabilistic methods. More specifically, I shall outline three settings for inductive logic programming: learning from entailment, learning from interpretations and learning from proofs or traces and show how they can be used to learn different types of probabilistic representations.

The learning from entailment setting is natural when learning stochastic context free grammars and their upgrade, stochastic logic programs, the learning from interpretations settings is the method of choice when learning bayesian networks or bayesian logic programs, and learning from proofs or traces correspond to learning (hidden) markov models and their first order upgrades. The resulting settings will also be illustrated using various real-life examples from the field of bio-informatics.

This is joint work with Kristian Kersting and part of the EU project APRIL II (Application of Probabilistic Inductive Logic Programming II). The talk will be based on
De Raedt, L., Kersting, K., Probabilistic Logic Learning, SIGKDD Explorations, Vol. 5(1), 2003.
De Raedt, L., Kersting, K. Probabilistic Inductive Logic Programming, In Proceedings ALT 2004, LNCS 3244, 2004.

---

Complexity of the Two-Variable Fragment with Counting Quantifiers

Ian Pratt-Hartmann, Manchester University, United Kingdom

Let C2 denote the fragment of first-order logic (without function-symbols) in which formulas may contain at most two variables, but with the usual counting quantifiers allowed. The satisfiability problem for C2 was shown to be decidable in 1997 by Graedel, Otto and Rosen and, independently, by Pacholski, Szwast and Tendera, with the latter providing an upper complexity bound of 2-NEXPTIME (improving to NEXPTIME if counting quantifiers are encoded non-succinctly). This talk reports on a recently obtained result which states that the satisfiability and finite satisfiability problems for C2 are in fact both in NEXPTIME, even when counting quantifiers are encoded succinctly.

---

Type Inference for Unique Pattern Matching

Stijn Vansummeren, Limburgs Universitair Centrum, Belgium

Regular expression patterns provide a natural, declarative way to express constraints on semi-structured data and to extract relevant information from it. Indeed, it is a core feature of the programming language Perl, surfaces in various UNIX tools such as sed and awk, and has recently been proposed in the context of the XML programming language XDuce. Since regular expressions can be ambiguous in general, different disambiguation policies have been proposed to get a unique matching strategy. We formally define the matching semantics under both (1) the POSIX, and (2) the first and longest match disambiguation strategies. We show that the generally accepted method of defining the longest match in terms of the first match and recursion does not conform to the natural notion of longest match. We continue by solving the type inference problem for both disambiguation strategies, which consists of calculating the set of all subparts of input values a subexpression can match under the given policy.