Recursos de colección

Document Server@UHasselt (58.026 recursos)

Repository of the University of Hasselt containing publications in the fields of statistics, computer science, information strategies and material from the Institute for behavioural sciences.

Databases and Theoretical Computer Science

Mostrando recursos 1 - 20 de 111

  1. Declarative Networking: Recent Theoretical Work on Coordination, Correctness, and Declarative Semantics

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

  2. Quasi-classical description logic

    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...

  3. On the power of SPARQL in expressing navigational queries

    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...

  4. On the completeness of the semigraphoid axioms for deriving arbitrary from saturated conditional independence statements

    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...

  5. Surgical Safety Checklists : an Update

    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...

  6. Positive Dedalus programs tolerate non-causality

    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...

  7. Interlace polynomials for multimatroids and delta-matroids

    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...

  8. On the primitivity of operators in SPARQL

    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.

  9. Conjunctive Context-Free Path Queries

    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 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...

  10. Some fragments of second-order logic over the reals for which satisfiability and equivalence are (un)decidable

    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.

  11. Privacy through Uncertainty in Location-Based Services

    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.

  12. On the intrinsic complexity of elimination problems in effective algebraic geometry

    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.

  13. Implication and Axiomatization of Functional Constraints on Patterns with an Application to the RDF Data 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 [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 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...

  14. An Approach towards the Study of Symmetric Queries

    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...

  15. A note on the variable hierarchy of first-order spectra

    TAN, Tony
    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.

  16. Regular graphs and the spectra of two-variable logic with counting

    TAN, Tony
    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...

  17. Relational Transducers for Declarative Networking

    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.

  18. Well-defined NRC queries can be typed

    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.

  19. Querying an integrated complex-object dataflow database

    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...

  20. On the expressive power of update primitives

    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...

Aviso de cookies: Usamos cookies propias y de terceros para mejorar nuestros servicios, para análisis estadístico y para mostrarle publicidad. Si continua navegando consideramos que acepta su uso en los términos establecidos en la Política de cookies.