1,721,012 research outputs found
A String-based Model for Infinite Granularities (Extended Abstract)
No full text) Jef Wijsen Universit'e de Mons-Hainaut [email protected] Abstract In the last few years, the concept of time granularity has been defined by several researchers, and a glossary of time granularity concepts has been published. These definitions often view a time granularity as a (mostly infinite) sequence of time granules. Although this view is conceptually clean, it is extremely inefficient or even practically impossible to represent a time granularity in this manner. In this paper, we present a practical formalism for the finite representation of infinite granularities. The formalism is string-based, allows symbolic reasoning, and can be extended to multiple dimensions to accommodate, for example, space. Introduction In the last few years, formalisms to represent and to reason about temporal and spatial granularity have been developed in several areas of computer science. Although several researchers have used different definitions of time granularity, they comm..
Mining the Data Cube for Improving its Scheme (Extended Abstract)
No full text) Stijn Dekeyser Bart Kuijpers Jan Paredaens Universiteit Antwerpen (UIA) Jef Wijsen y Vrije Universiteit Brussel (VUB) z Abstract The integration of data mining, data warehousing, and OLAP is an important research direction--- Han [4] uses the term OLAP mining in this respect. Data warehouses facilitate data mining, and conversely, the desire to mine knowledge is an incentive to maintain large, integrated data warehouses. The data structures of data warehouses are typically "flat" multidimensional data cubes. In this paper, we present the notion of nested data cube, which we believe is a natural paradigm for perceiving large data cubes. Flat data cubes can be nested in numerous ways. Three measures for characterizing the complexity/simplicity of a particular nesting are presented. An interesting data mining problem then is: Given threshold values for each measure, find a nesting that satisfies each threshold. The computational complexity and the applicability of this problem a..
Front Matter, Table of Contents, Preface, Organization, List of Authors
No full textFront Matter, Table of Contents, Preface, Organization, List of Author
Consistent Query Answering for Primary Keys in Logspace
Full text linkWe study the complexity of consistent query answering on databases that may violate primary key constraints. A repair of such a database is any consistent database that can be obtained by deleting a minimal set of tuples. For every Boolean query q, CERTAINTY(q) is the problem that takes a database as input and asks whether q evaluates to true on every repair. In [Koutris and Wijsen, ACM TODS, 2017], the authors show that for every self-join-free Boolean conjunctive query q, the problem CERTAINTY(q) is either in P or coNP-complete, and it is decidable which of the two cases applies. In this paper, we sharpen this result by showing that for every self-join-free Boolean conjunctive query q, the problem CERTAINTY(q) is either expressible in symmetric stratified Datalog (with some aggregation operator) or coNP-complete. Since symmetric stratified Datalog is in L, we thus obtain a complexity-theoretic dichotomy between L and coNP-complete. Another new finding of practical importance is that CERTAINTY(q) is on the logspace side of the dichotomy for queries q where all join conditions express foreign-to-primary key matches, which is undoubtedly the most common type of join condition
A Streamlined Model of Conditional Simple Temporal Networks - Semantics and Equivalence Results
Full text linkA Conditional Simple Temporal Network (CSTN) augments a Simple Temporal Network to include a new kind of time-points, called observation time-points. The execution of an observation time-point generates information in real time, specifically, the truth value of a propositional letter. In addition, time-points and temporal constraints may be labeled by conjunctions of (positive or negative) propositional letters. A CSTN is called dynamically consistent (DC) if there exists a dynamic strategy for executing its time-points such that no matter how the observations turn out during execution, the time-points whose labels are consistent with those observations have all been executed, and the constraints whose labels are consistent with those observations have all been satisfied. The strategy is dynamic in that its execution decisions may react to observations.
The original formulation of CSTNs included propositional labels only on time-points, but the DC-checking algorithm was impractical because it was based on a conversion of the semantic constraints into an exponentially-sized Disjunctive Temporal Network. Later work added propositional labels to temporal constraints, and yielded a sound-and-complete propagation-based DC-checking algorithm, empirically demonstrated to be practical across a variety of CSTNs.
This paper introduces a streamlined version of a CSTN in which propositional labels may appear on constraints, but not on time-points. This change simplifies the definition of the DC property, as well as the propagation rules for the DC-checking algorithm. It also simplifies the proofs of the soundness and completeness of those rules.
This paper provides two translations from traditional CSTNs to streamlined CSTNs. Each translation preserves the DC property and, for any DC network, ensures that any dynamic execution strategy for that network can be extended to a strategy for its streamlined counterpart.
Finally, this paper presents an empirical comparison of two versions of the DC-checking algorithm: the original version and a simplified version for streamlined CSTNs. The comparison is based on CSTN benchmarks from earlier work. For small-sized CSTNs, the original version shows the best performance, but the performance difference between the two versions decreases as the number of time-points in the CSTN increases. We conclude that the simplified algorithm is a practical alternative for checking the dynamic consistency of CSTNs
Project-Join-Repair: An Approach to Consistent Query Answering Under Functional Dependencies
No full text
- …
