
AMELOOT, Tom
We discuss recent theoretical results on declarative networking, in particular regarding the topics of coordination, correctness, and declarative semantics.

ZHANG, Xiaowang; LIN, Zuoquan
In this paper, we present a paraconsistent description logic based on quasiclassical logic. Compared to the fourvalued description logic, quasiclassical description logic satisfies all of the three basic inference rules (i.e., modus ponens, modus tollens and disjunctive syllogism) so that the inference ability of quasiclassical description logic is closer to that of classical logic. Quasiclassical description logic combines three inclusions (i.e., material inclusion, internal inclusion and strong inclusion) of fourvalued description logic so that quasiclassical description logic satisfies the intuitive equivalence. Moreover, we develop a terminable, sound and complete tableau algorithm for quasiclassical description logic. As an important result, the...

ZHANG, Xiaowang; VAN DEN BUSSCHE, Jan
Navigational queries on graph databases return binary relations over the nodes of the graph. The calculus of relations, popularized by Tarski, serves as a natural benchmark for firstorder navigational querying. Recently, nested regular expressions (nre's) have been proposed to extend navigational querying to resource description framework graphs, i.e. ternary relations. This paper investigates the expressiveness of nre's and their relationship to basic SPARQL queries. An elegant proof is given to the effect that nre queries are already expressible as basic SPARQL queries. This result takes exception of nre's involving Kleene star (transitive closure), but on the other hand it holds...

GYSSENS, Marc; Niepert, Mathias; Van Gucht, Dirk
Conditional independence (CI) statements occur in several areas of computer science and artificial intelligence, e.g., as embedded multivalued dependencies in database theory, disjunctive association rules in data mining, and probabilistic CI statements in probability theory. Although, syntactically, such constraints can always be represented in the form I(A, B vertical bar C), with A, B, and C subsets of some universe S, their semantics is very dependent on their interpretation, and, therefore, inference rules valid under one interpretation need not be valid under another. However, all aforementioned interpretations obey the socalled semigraphoid axioms. In this paper, we consider the restricted case...

Bergs, Jochen; Hellings, Johan; CLEEMPUT, Irina; SIMONS, Pascale; ZUREL, Ozhan; VERTRIEST, Sonja; VANDIJCK, Dominique
Surgical safety checklists aim to improve patient safety by prompting the attention of the surgical team towards critical steps during the operation. The checklist's items are aimed to improve compliance with proven interventions, and to facilitate multidisciplinary communication and teamwork. Based on the current literature, corroborated by systematic reviews and metaanalysis, surgical safety checklists have a positive impact on communication and reduce postoperative complications including mortality. However, despite their effectiveness, the implementation of these checklists is not straightforward. Several determinants leading to behaviour were checklists are checked but not properly executed have been highlighted. As surgical safety checklists are in...

AMELOOT, Tom; VAN DEN BUSSCHE, Jan
Declarative networking is a recent approach to programming distributed applications with languages inspired by Datalog. A recent conjecture posits that the delivery of messages should respect causality if and only if they are used in nonmonotone derivations. We present our results about this conjecture in the context of Dedalus, a Datalogvariant for distributed programming. We show that both directions of the conjecture fail under a strong semantical interpretation. But on a more syntactical level, we show that positive Dedalus programs can tolerate noncausal messages, in the sense that they compute the correct answer even when messages can be sent into...

BRIJDER, Robert; Hoogeboom, Hendrik Jan
We provide a unified framework in which the interlace polynomial
and several related graph polynomials are defined more generally
for multimatroids and deltamatroids. Using combinatorial properties
of multimatroids rather than graphtheoretical arguments, we find that various known results about these polynomials, including their recursive relations, are both more efficiently and more generally obtained. In addition, we obtain several interrelationships and results for polynomials on multimatroids and deltamatroids that correspond to new interrelationships and results for the corresponding graph polynomials. As a tool we prove the equivalence
of tight 3matroids and deltamatroids closed under the operations
of twist and loop complementation, called vfsafe deltamatroids.
This result is...

Zhang, Xiaowang; Van den Bussche, Jan
The paper studies the primitivity of the basic operators UNION, AND, OPTIONAL, FILTER, and SELECT, as they are used in the SPARQL query language. The question of whether one operator can be expressed in terms of the other operators is answered in detail. It turns out that only AND is nonprimitive. These results are shown to be insensitive to the choice of semantics for filter conditions (threevalued or twovalued). It is also shown that these two semantics can simulate each other.

HELLINGS, Jelle
In graph query languages, regular expressions are commonly used to specify the labeling of paths. A natural step in increasing the expressive power of these query languages is replacing regular expressions by contextfree grammars. With the Conjunctive ContextFree Path Queries (CCFPQ) we introduce such a language based on the wellknown Conjunctive Regular Path Queries (CRPQ).
First, we show that query evaluation of CCFPQ has polynomial time data complexity. Secondly, we look at the generalization of regular expressions, as used in CRPQ, to regular relations and show how similar generalizations can be applied to contextfree grammars, as used in CCFPQ. Thirdly, we...

GRIMSON, Rafael; KUIJPERS, Bart
We consider the Sigma_0^1fragment of secondorder logic over the vocabulary <+,x,0,1, <, S_1,..., S_k>, interpreted over the reals, where the predicate symbols S_i are interpreted as semialgebraic sets. We show that, in this context, satisability of formulas is decidable for the firstorder exists^* quantier fragment and undecidable for the exists^*forall and forall^* fragments. We
also show that for these three fragments the same (un)decidability results hold for containment and equivalence of formulas.

Merrill, Shawn; Basalp, Nilgun; Biskup, Joachim; Buchmann, Erik; Clifton, Chris; Kuijpers, Bart; Othman, Walied; Savas, Erkay
LocationBased Services (LBS) are becoming more prevalent. While there are many benefits, there are also real privacy risks. People are unwilling to give up the benefits  but can we reduce privacy risks without giving up on LBS entirely? This paper explores the possibility of introducing uncertainty into location information when using an LBS, so as to reduce privacy risk while maintaining good quality of service. This paper also explores the current uses of uncertainty information in a selection of mobile applications.

Heintz, Joos; Kuijpers, Bart; Rojas Paredes, Andr??s
The representation of polynomials by arithmetic circuits evaluating
them is an alternative data structure which allowed considerable progress in polynomial equation solving in the last fifteen years. We present a circuit based computation model which captures the core of all known symbolic elimination algorithms that avoid unnecessary branchings in effective algebraic geometry and show the intrinsically exponential complexity character of elimination in this complexity model.

Hellings, Jelle; Gyssens, Marc; Paredaens, Jan; Wu, Yuqing
Akhtar et al. introduced equalitygenerating constraints and functional constraints as an initial step towards dependencylike integrity constraints for RDF data [1]. Here, we focus on functional constraints. The usefulness of functional constraints is not limited to the RDF data model. Therefore, we study the functional constraints in the more general setting of relations with arbitrary arity. We show that a chase algorithm for functional constraints can be normalized to a more specialized symmetrypreserving chase algorithm. This symmetrypreserving chase algorithm is subsequently used to construct a sound and complete axiomatization for the functional constraints. This axiomatization is in particular applicable in...

Gyssens, Marc; Paredaens, Jan; Van Gucht, Dirk; Wijsen, Jef; Wu, Yuqing
Many dataintensive applications have to query a database that involves sequences of sets of objects. It is not uncommon that the order of the sets in such a sequence does not affect the result of the query. Such queries are called symmetric. In this paper, the authors wish to initiate research on symmetric queries. Thereto, a data model is proposed in which a binary relation between objects and set names encodes set membership. On this data model, two query languages are introduced, QuineCALC and SyCALC. They are correlated in a manner that is made precise with the symmetric Boolean functions...

TAN, Tony
The spectrum of a firstorder logic sentence is the set of natural numbers that are cardinalities of its finite models. In this note we study the hierarchy of firstorder spectra based on the number of variables. We show that it forms an infinite hierarchy. However, despite the fact that more variables can express more spectra, we also show that to show whether the firstorder spectra are closed under complement, it is sufficient to consider sentences using only three variables and binary relations.

TAN, Tony
The spectrum of a firstorder logic sentence is the set of natural numbers that are cardinalities of its finite models. In this paper we show that when restricted to using only two variables, but allowing counting quantifiers, the spectra of firstorder logic sentences are semilinear and hence, closed under complement. At the heart of our proof are semilinear characterisations for the existence of regular and biregular graphs, the class of graphs in which there are a priori bounds on the degrees of the vertices.
Our proof also provides a simple characterisation of models of twovariable logic with counting  that...

Ameloot, Tom J.; Neven, Frank; Van den Bussche, Jan
Motivated by a recent conjecture concerning the expressiveness of declarative networking, we propose a formal computation model for "eventually consistent" distributed querying, based on relational transducers. A tight link has been conjectured between coordinationfreeness of computations, and monotonicity of the queries expressed by such computations. Indeed, we propose a formal definition of coordinationfreeness and confirm that the class of monotone queries is captured by coordinationfree transducer networks. Coordinationfreeness is a semantic property, but the syntactic class of "oblivious" transducers we define also captures the same class of monotone queries. Transducer networks that are not coordinationfree are much more powerful.

VAN DEN BUSSCHE, Jan; VANSUMMEREN, Stijn
We study the expressive power of the static type system of the Nested Relational Calculus TeX and show that on socalled homogeneous input and output types, the TeX type system is expressively complete: every untyped but homogeneously welldefined TeX expression can be equivalently expressed by a welltyped expression. The TeX static type system hence does not limit the expressive power of the query writer.

KWASNIKOWSKA, Natalia; VAN DEN BUSSCHE, Jan
We consider an integrated complexobject dataflow database in which multiple dataflow specifications can be stored, together with multiple executions of these dataflows, including the complexobject data that are involved, and annotations. We focus on dataflow applications frequently encountered in the scientific community, involving the manipulation of data with a complexobject structure combined with service calls, which can be either internal or external. Internal services are dataflows acting as a subprogram of an other dataflow, whereas external services are modeled as functions with a possibly nondeterministic behavior. Dataflow specifications are expressed in a highlevel programming language based on the nested relational...

AMELOOT, Tom; VAN DEN BUSSCHE, Jan; Waller, Emmanuel
The SQL standard offers three primitive operations (insert, delete, and update which is here called modify) to update a relation based on a generic query. This paper compares the expressiveness of programs composed of these three operations, with the general notion of update that simply replaces the content of the relation by the result of a query. It turns out that replacing cannot be expressed in terms of insertions, deletions, and modifications, and neither can modifications be expressed in terms of insertions and deletions. The expressive power gained by ifthenelse control flow in programs is investigated as well. Different ways...