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 quasi-classical logic. Compared to the four-valued description logic, quasi-classical 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 quasi-classical description logic is closer to that of classical logic. Quasi-classical description logic combines three inclusions (i.e., material inclusion, internal inclusion and strong inclusion) of four-valued description logic so that quasi-classical description logic satisfies the intuitive equivalence. Moreover, we develop a terminable, sound and complete tableau algorithm for quasi-classical 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 first-order 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 so-called 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 meta-analysis, 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 non-monotone derivations. We present our results about this conjecture in the context of Dedalus, a Datalog-variant 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 non-causal 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 delta-matroids. Using combinatorial properties
of multimatroids rather than graph-theoretical 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 delta-matroids that correspond to new interrelationships and results for the corresponding graph polynomials. As a tool we prove the equivalence
of tight 3-matroids and delta-matroids closed under the operations
of twist and loop complementation, called vf-safe delta-matroids.
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 non-primitive. These results are shown to be insensitive to the choice of semantics for filter conditions (three-valued or two-valued). It is also shown that these two semantics can simulate each other.
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 context-free grammars. With the Conjunctive Context-Free Path Queries (CCFPQ) we introduce such a language based on the well-known 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 context-free grammars, as used in CCFPQ. Thirdly, we...
GRIMSON, Rafael; KUIJPERS, Bart
We consider the Sigma_0^1-fragment of second-order logic over the vocabulary <+,x,0,1, <, S_1,..., S_k>, interpreted over the reals, where the predicate symbols S_i are interpreted as semi-algebraic sets. We show that, in this context, satisability of formulas is decidable for the first-order 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
Location-Based 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 equality-generating constraints and functional constraints as an initial step towards dependency-like integrity constraints for RDF data . 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 symmetry-preserving chase algorithm. This symmetry-preserving 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 data-intensive 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...
The spectrum of a first-order logic sentence is the set of natural numbers that are cardinalities of its finite models. In this note we study the hierarchy of first-order 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 first-order spectra are closed under complement, it is sufficient to consider sentences using only three variables and binary relations.
The spectrum of a first-order 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 first-order 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 two-variable 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 coordination-freeness of computations, and monotonicity of the queries expressed by such computations. Indeed, we propose a formal definition of coordination-freeness and confirm that the class of monotone queries is captured by coordination-free transducer networks. Coordination-freeness 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 coordination-free 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 so-called homogeneous input and output types, the TeX type system is expressively complete: every untyped but homogeneously well-defined TeX expression can be equivalently expressed by a well-typed 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 complex-object dataflow database in which multiple dataflow specifications can be stored, together with multiple executions of these dataflows, including the complex-object data that are involved, and annotations. We focus on dataflow applications frequently encountered in the scientific community, involving the manipulation of data with a complex-object 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 non-deterministic behavior. Dataflow specifications are expressed in a high-level 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 if-then-else control flow in programs is investigated as well. Different ways...