Dagstuhl Publishing
http://www.dagstuhl.de
RSS feed announcing the latest publications published by Schloss Dagstuhlen-en2010-06-082010-06-08http://www.dagstuhl.de/rss.phpBeyond-Planar Graphs: Algorithmics and Combinatorics (Dagstuhl Seminar 16452)
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7038
This report summarizes Dagstuhl Seminar 16452 "Beyond-Planar Graphs: Algorithmics and Combinatorics'' and documents the talks and discussions.The seminar brought together 29 researchers in the areas of graph theory, combinatorics, computational geometry, and graph drawing. The common interest was in the exploration of structural properties and the development of algorithms for so-called beyond-planar graphs, i.e., non-planar graphs with topological constraints such as specific types of crossings, or with some forbidden crossing patterns. The seminar began with three introductory talks by experts in the different fields. Abstracts of these talks are collected in this report. Next we discussed and grouped together open research problems about beyond planar graphs, such as their combinatorial structures (e.g, thickness, crossing number, coloring), their topology (e.g., string graph representation), their geometric representations (e.g., straight-line drawing, visibility representation, contact representation), and applications (e.g., algorithms for real-world network visualization). Four working groups were formed and a report from each group is included here.Thu, 23 Mar 2017 09:49:48 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7038Structure and Hardness in P (Dagstuhl Seminar 16451)
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7037
This document contains description of the talks at the Dagstuhl seminar 16451 "Structure and Hardness in P". The main goal of the seminar was to bring together researchers from several disciplines and connect those who work on proving conditional lower bounds with those who or may benefit from it. This resulted in an extensive list of open problems which is also provided.Thu, 23 Mar 2017 09:49:24 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7037LIPIcs, Volume 68, ICDT'17, Complete Volume
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7068
LIPIcs, Volume 68, ICDT'17, Complete VolumeTue, 21 Mar 2017 14:17:14 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7068Front Matter, Table of Contents, Preface, Conference Organization, List of Authors
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7044
Front Matter, Table of Contents, Preface, Conference Organization, List of AuthorsTue, 14 Mar 2017 21:43:22 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7044Top-k Querying of Unknown Values under Order Constraints
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7045
Many practical scenarios make it necessary to evaluate top-k queries over data items with partially unknown values. This paper considers a setting where the values are taken from a numerical domain, and where some partial order constraints are given over known and unknown values: under these constraints, we assume that all possible worlds are equally likely.Our work is the first to propose a principled scheme to derive the value distributions and expected values of unknown items in this setting, with the goal of computing estimated top-k results by interpolating the unknown values from the known ones. We study the complexity of this general task, and show tight complexity bounds, proving that the problem is intractable, butcan be tractably approximated. We then consider the case of tree-shaped partial orders, where we show a constructive PTIME solution. We also compare our problem setting to other top-k definitions on uncertain data.Tue, 14 Mar 2017 21:43:22 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7045GYM: A Multiround Distributed Join Algorithm
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7046
Multiround algorithms are now commonly used in distributed data processing systems, yet the extent to which algorithms can benefit from running more rounds is not well understood. This paper answers this question for several rounds for the problem of computing the equijoin of n relations. Given any query Q with width w, intersection width iw, input size IN, output size OUT, and a cluster of machines with M=\Omega(IN \frac{1}{\epsilon}) memory available per machine, where \epsilon > 1 and w \ge 1 are constants, we show that:1. Q can be computed in O(n) rounds with O(n(INw + OUT)2/M) communication cost with high probability.Q can be computed in O(log(n)) rounds with O(n(INmax(w, 3iw) + OUT)2/M) communication cost with high probability.Intersection width is a new notion we introduce for queries and generalized hypertree decompositions (GHDs) of queries that captures how connected the adjacent components of the GHDs are. We achieve our first result by introducing a distributed and generalized version of Yannakakis's algorithm, called GYM. GYM takes as input any GHD of Q with width w and depth d, and computes Q in O(d + log(n)) rounds and O(n (INw + OUT)2/M) communication cost. We achieve our second result by showing how to construct GHDs of Q with width max(w, 3iw) and depth O(log(n)). We describe another technique to construct GHDs with longer widths and lower depths, demonstrating other tradeoffs one can make between communication and the number of rounds.Tue, 14 Mar 2017 21:43:22 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7046Entropy Bounds for Conjunctive Queries with Functional Dependencies
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7047
We study the problem of finding the worst-case size of the result Q(D) of a fixed conjunctive query Q applied to a database D satisfying given functional dependencies. We provide a characterization of this bound in terms of entropy vectors, and in terms of finite groups. In particular, we show that an upper bound provided by [Gottlob, Lee, Valiant and Valiant, J.ACM, 2012] is tight, and that a correspondence of [Chan and Yeung, ACM TOIT, 2002] is preserved in the presence of functional dependencies. However, tightness of a weaker upper bound provided by Gottlob et al., which would have immediate applications to evaluation of join queries ([Khamis, Ngo, and Suciu, PODS, 2016]) remains open. Our result shows that the problem of computing the worst-case size bound, in the general case, is closely related to difficult problems from information theory.Tue, 14 Mar 2017 21:43:22 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7047Detecting Ambiguity in Prioritized Database Repairing
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7048
In its traditional definition, a repair of an inconsistent database is a consistent database that differs from the inconsistent one in a "minimal way." Often, repairs are not equally legitimate, as it is desired to prefer one over another; for example, one fact is regarded more reliable than another, or a more recent fact should be preferred to an earlier one.Motivated by these considerations, researchers have introduced and investigated the framework of preferred repairs, in the context of denial constraints and subset repairs. There, a priority relation between facts is lifted towards a priority relation between consistent databases, and repairs are restricted to the ones that are optimal in the lifted sense.Three notions of lifting (and optimal repairs) have been proposed: Pareto, global, and completion.In this paper we investigate the complexity of deciding whether the priority relation suffices to clean the database unambiguously, or in other words, whether there is exactly one optimal repair. We show that the different lifting semantics entail highly different complexities. Under Pareto optimality, the problem is coNP-complete, in data complexity, for every set of functional dependencies (FDs), except for the tractable case of (equivalence to) one FD per relation. Under global optimality, one FD per relation is still tractable, but we establish Pi-2-p-completeness for a relation with two FDs. In contrast, under completion optimality the problem is solvable in polynomial time for every set of FDs. In fact, we present a polynomial-time algorithm for arbitrary conflict hypergraphs. We further show that under a general assumption of transitivity, this algorithm solves the problem even for global optimality. The algorithm is extremely simple, but its proof of correctness is quite intricate.Tue, 14 Mar 2017 21:43:22 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7048A Logic for Document Spanners
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7049
Document spanners are a formal framework for information extraction that was introduced by [Fagin, Kimelfeld, Reiss, and Vansummeren, J.ACM, 2015]. One of the central models in this framework are core spanners, which are based on regular expressions with variables that are then extended with an algebra. As shown by [Freydenberger and Holldack, ICDT, 2016], there is a connection between core spanners and EC^{reg}, the existential theory of concatenation with regular constraints. The present paper further develops this connection by defining SpLog, a fragment of EC^{reg} that has the same expressive power as core spanners. This equivalence extends beyond equivalence of expressive power, as we show the existence of polynomial time conversions between this fragment and core spanners. This even holds for variants of core spanners that are based on automata instead of regular expressions. Applications of this approach include an alternative way of defining relations for spanners, insights into the relative succinctness of various classes of spanner representations, and a pumping lemma for core spanners.Tue, 14 Mar 2017 21:43:22 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7049On the Automated Verification of Web Applications with Embedded SQL
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7050
A large number of web applications is based on a relational database together with a program, typically a script, that enables the user to interact with the database through embedded SQL queries and commands. In this paper, we introduce a method for formal automated verification of such systems which connects database theory to mainstream program analysis. We identify a fragment of SQL which captures the behavior of the queries in our case studies, is algorithmically decidable, and facilitates the construction of weakest preconditions. Thus, we can integrate the analysis of SQL queries into a program analysis tool chain. To this end, we implement a new decision procedure for the SQL fragment that we introduce. We demonstrate practical applicability of our results with three case studies, a web administrator, a simple firewall, and a conference management system.Tue, 14 Mar 2017 21:43:22 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7050Combined Tractability of Query Evaluation via Tree Automata and Cycluits
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7051
We investigate parameterizations of both database instances and queries that make query evaluation fixed-parameter tractable in combined complexity. We introduce a new Datalog fragment with stratified negation, intensional-clique-guarded Datalog (ICG-Datalog), with linear-time evaluation on structures of bounded treewidth for programs of bounded rule size. Such programs capture in particular conjunctive queries with simplicial decompositions of bounded width, guarded negation fragment queries of bounded CQ-rank, or two-way regular path queries. Our result is shown by compiling to alternating two-way automata, whose semantics is defined via cyclic provenance circuits (cycluits) that can be tractably evaluated. Last, we prove that probabilistic query evaluation remains intractable in combined complexity under this parameterization.Tue, 14 Mar 2017 21:43:22 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7051The Complexity of Reverse Engineering Problems for Conjunctive Queries
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7052
Reverse engineering problems for conjunctive queries (CQs), such as query by example (QBE) or definability, take a set of user examples and convert them into an explanatory CQ. Despite their importance, the complexity of these problems is prohibitively high (coNEXPTIME-complete). We isolate their two main sources of complexity and propose relaxations of them that reduce the complexity while having meaningful theoretical interpretations. The first relaxation is based on the idea of using existential pebble games for approximating homomorphism tests. We show that this characterizes QBE/definability for CQs up to treewidth k, while reducing the complexity to EXPTIME. As a side result, we obtain that the complexity of the QBE/definability problems for CQs of treewidth k is EXPTIME-complete for each k > 1. The second relaxation is based on the idea of "desynchronizing" direct products, which characterizes QBE/definability for unions of CQs and reduces the complexity to coNP. The combination of these two relaxations yields tractability for QBE and characterizes it in terms of unions of CQs of treewidth at most k. We also study the complexity of these problems for conjunctive regular path queries over graph databases, showing them to be no more difficult than for CQs.Tue, 14 Mar 2017 21:43:22 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7052Answering FO+MOD Queries Under Updates on Bounded Degree Databases
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7053
We investigate the query evaluation problem for fixed queries over fully dynamic databases, where tuples can be inserted or deleted. The task is to design a dynamic algorithm that immediately reports the new result of a fixed query after every database update.We consider queries in first-order logic (FO) and its extension with modulo-counting quantifiers (FO+MOD), and show that they can be efficiently evaluated under updates, provided that the dynamic database does not exceed a certain degree bound.In particular, we construct a data structure that allows to answer a Boolean FO+MOD query and to compute the size of the query result within constant time after every database update. Furthermore, after every update we are able to immediately enumerate the new query result with constant delay between the output tuples. The time needed to build the data structure is linear in the size of the database.Our results extend earlier work on the evaluation of first-order queries on static databases of bounded degree and rely on an effective Hanf normal form for FO+MOD recently obtained by [Heimberg, Kuske, and Schweikardt, LICS, 2016].Tue, 14 Mar 2017 21:43:22 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7053How Many Variables Are Needed to Express an Existential Positive Query?
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7054
The number of variables used by a first-order query is a fundamental measure which has been studied in numerous contexts, and which is known to be highly relevant to the task of query evaluation. In this article, we study this measure in the context of existential positive queries. Building on previous work, we present a combinatorial quantity defined on existential positive queries; we show that this quantity not only characterizes the minimum number of variables needed to express a given existential positive query by another existential positive query, but also that it characterizes the minimum number of variables needed to express a given existential positive query, over all first-order queries. Put differently and loosely, we show that for any existential positive query, no variables can ever be saved by moving out of existential positive logic to first-order logic. One component of this theorem’s proof is the construction of a winning strategy for a certain Ehrenfeucht-Fraiissé type game.Tue, 14 Mar 2017 21:43:22 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7054Expressive Power of Entity-Linking Frameworks
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7055
We develop a unifying approach to declarative entity linking by introducing the notion of an entity linking framework and an accompanying notion of the certain links in such a framework. In an entity linking framework, logic-based constraints are used to express properties of the desired link relations in terms of source relations and, possibly, in terms of other link relations. The definition of the certain links in such a framework makes use of weighted repairs and consistent answers in inconsistent databases. We demonstrate the modeling capabilities of this approach by showing that numerous concrete entity linking scenarios can be cast as such entity linking frameworks for suitable choices of constraints and weights. By using the certain links as a measure of expressive power, we investigate the relative expressive power of several entity linking frameworks and obtain sharp comparisons. In particular, we show that we gain expressive power if we allow constraints that capture non-recursive collective entity resolution, where link relations may depend on other link relations (and not just on source relations). Moreover, we show that an increase in expressive power also takes place when we allow constraints that incorporate preferences as an additional mechanism for expressing "goodness" of links.Tue, 14 Mar 2017 21:43:22 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7055k-Regret Minimizing Set: Efficient Algorithms and Hardness
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7056
We study the k-regret minimizing query (k-RMS), which is a useful operator for supporting multi-criteria decision-making. Given two integers k and r, a k-RMS returns r tuples from the database which minimize the k-regret ratio, defined as one minus the worst ratio between the k-th maximum utility score among all tuples in the database and the maximum utility score of the r tuples returned. A solution set contains only r tuples, enjoying the benefits of both top-k queries and skyline queries. Proposed in 2012, the query has been studied extensively in recent years. In this paper, we advance the theory and the practice of k-RMS in the following aspects. First, we develop efficient algorithms for k-RMS (and its decision version) when the dimensionality is 2. The running time of our algorithms outperforms those of previous ones. Second, we show that k-RMS is NP-hard even when the dimensionality is 3. This provides a complete characterization of the complexity of k-RMS, and answers an open question in previous studies. In addition, we present approximation algorithms for the problem when the dimensionality is 3 or larger.Tue, 14 Mar 2017 21:43:22 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7056The Design of Arbitrage-Free Data Pricing Schemes
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7057
Motivated by a growing market that involves buying and selling data over the web, we study pricing schemes that assign value to queries issued over a database. Previous work studied pricing mechanisms that compute the price of a query by extending a data seller’s explicit prices on certain queries, or investigated the properties that a pricing function should exhibit without detailing a generic construction. In this work, we present a formal framework for pricing queries over data that allows the construction of general families of pricing functions, with the main goal of avoiding arbitrage. We consider two types of pricing schemes: instance-independent schemes, where the price depends only on the structure of the query, and answer-dependent schemes, where the price also depends on the query output. Our main result is a complete characterization of the structure of pricing functions in both settings, by relating it to properties of a function over a lattice. We use our characterization, together with information-theoretic methods, to construct a variety of arbitrage-free pricing functions. Finally, we discuss various tradeoffs in the design space and present techniques for efficient computation of the proposed pricing functions.Tue, 14 Mar 2017 21:43:22 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7057Compression of Unordered XML Trees
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7058
Many XML documents are data-centric and do not make use of the inherent document order. Can we provide stronger compression for such documents through giving up order? We first consider compression via minimal dags (directed acyclic graphs) and study the worst case ratio of the size of the ordered dag divided by the size of the unordered dag, where the worst case is taken for all trees of size n. We prove that this worst case ratio is n / log n for the edge size and n log log n / log n for the node size. In experiments we compare several known compressors on the original document tree versus on a canonical version obtained by length-lexicographical sorting of subtrees. For some documents this difference is surprisingly large: reverse binary dags can be smaller by a factor of 3.7 and other compressors can be smaller by factors of up to 190.Tue, 14 Mar 2017 21:43:22 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7058Dynamic Complexity under Definable Changes
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7059
This paper studies dynamic complexity under definable change operations in the DynFO framework by Patnaik and Immerman. It is shown that for changes definable by parameter-free first-order formulas, all (uniform) AC1 queries can be maintained by first-order dynamic programs. Furthermore, many maintenance results for single-tuple changes are extended to more powerful change operations: (1) The reachability query for undirected graphs is first-order maintainable under single tuple changes and first-order defined insertions, likewise the reachability query for directed acyclic graphs under quantifier-free insertions. (2) Context-free languages are first-order maintainable under \EFO-defined changes. These results are complemented by several inexpressibility results, for example, that the reachability query cannot be maintained by quantifier-free programs under definable, quantifier-free deletions.Tue, 14 Mar 2017 21:43:22 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7059Constant Delay Enumeration for FO Queries over Databases with Local Bounded Expansion
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7060
We consider the evaluation of first-order queries over classes of databases with local bounded expansion. This class was introduced by Nesetril and Ossona de Mendez and generalizes many well known classes of databases, such as bounded degree, bounded tree width or bounded expansion. It is known that over classes of databases with local bounded expansion, first-order sentences can be evaluated in pseudo-linear time (pseudo-linear time means that for all \epsilon there exists an algorithm working in time O(n^{1+\epsilon})). Here, we investigate other scenarios, where queries are not sentences. We show that first-order queries can be enumerated with constant delay after a pseudo-linear preprocessing over any class of databases having locally bounded expansion. We also show that, in this context, counting the number of solutions can be done in pseudo-linear time.Tue, 14 Mar 2017 21:43:22 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7060m-tables: Representing Missing Data
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7061
Representation systems have been widely used to capture different forms of incomplete data in various settings. However, existing representation systems are not expressive enough to handle the more complex scenarios of missing data that can occur in practice: these could vary from missing attribute values, missing a known number of tuples, or even missing an unknown number of tuples. In this work, we propose a new representation system called m-tables, that can represent many different types of missing data. We show that m-tables form a closed, complete and strong representation system under both set and bag semantics and are strictly more expressive than conditional tables under both the closed and open world assumptions. We further study the complexity of computing certain and possible answers in m-tables. Finally, we discuss how to "interpret" m-tables through a novel labeling scheme that marks a type of generalized tuples as certain or possible.Tue, 14 Mar 2017 21:43:22 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7061Better Streaming Algorithms for the Maximum Coverage Problem
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7062
We study the classic NP-Hard problem of finding the maximum k-set coverage in the data stream model: given a set system of m sets that are subsets of a universe {1,...,n}, find the k sets that cover the most number of distinct elements. The problem can be approximated up to a factor 1-1/e in polynomial time. In the streaming-set model, the sets and their elements are revealed online. The main goal of our work is to design algorithms, with approximation guarantees as close as possible to 1-1/e, that use sublinear space o(mn). Our main results are: 1) Two (1-1/e-epsilon) approximation algorithms: One uses O(1/epsilon) passes and O(k/epsilon^2 polylog(m,n)) space whereas the other uses only a single pass but O(m/epsilon^2 polylog(m,n)) space. 2) We show that any approximation factor better than (1-(1-1/k)^k) in constant passes require space that is linear in m for constant k even if the algorithm is allowed unbounded processing time. We also demonstrate a single-pass, (1-epsilon) approximation algorithm using O(m/epsilon^2 min(k,1/epsilon) polylog(m,n)) space.We also study the maximum k-vertex coverage problem in the dynamic graph stream model. In this model, the stream consists of edge insertions and deletions of a graph on N vertices. The goal is to find k vertices that cover the most number of distinct edges. We show that any constant approximation in constant passes requires space that is linear in N for constant k whereas O(N/epsilon^2 polylog(m,n)) space is sufficient for a (1-epsilon) approximation and arbitrary k in a single pass. For regular graphs, we show that O(k/epsilon^3 polylog(m,n)) space is sufficient for a (1-epsilon) approximation in a single pass. We generalize this to a K-epsilon approximation when the ratio between the minimum and maximum degree is bounded below by K.Tue, 14 Mar 2017 21:43:22 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7062Rewritability in Monadic Disjunctive Datalog, MMSNP, and Expressive Description Logics (Invited Talk)
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7063
We study rewritability of monadic disjunctive Datalog programs, (the complements of) MMSNP sentences, and ontology-mediated queries (OMQs) based on expressive description logics of the ALC family and on conjunctive queries. We show that rewritability into FO and into monadic Datalog (MDLog) are decidable, and that rewritability into Datalog is decidable when the original query satisfies a certain condition related to equality. We establish 2NExpTime-completeness for all studied problems except rewritability into MDLog for which there remains a gap between 2NExpTime and 3ExpTime. We also analyze the shape of rewritings, which in the MMSNP case correspond to obstructions, and give a new construction of canonical Datalog programs that is more elementary than existing ones and also applies to non-Boolean queries.Tue, 14 Mar 2017 21:43:22 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7063The Smart Crowd - Learning from the Ones Who Know (Invited Talk)
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7064
One of the foremost challenges for information technology over the last few years has been to explore, understand, and extract useful information from large amounts of data. Some particular tasks such as annotating data or matching entities have been outsourced to human workers for many years. But the last few years have seen the rise of a new research field called crowdsourcing that aims at delegating a wide range of tasks to human workers, building formal frameworks, and improving the efficiency of these processes.In order to provide sound scientific foundations for crowdsourcing and support the development of efficient crowd sourcing processes, adequate formal models and algorithms must be defined. In particular, the models must formalize unique characteristics of crowd-based settings, such as the knowledge of the crowd and crowd-provided data; the interaction with crowd members; the inherent inaccuracies and disagreements in crowd answers; and evaluation metrics that capture the cost and effort of the crowd.Clearly, what may be achieved with the help of the crowd depends heavily on the properties and knowledge of the given crowd. In this talk we will focus on knowledgeable crowds. We will examine the use of such crowds, and in particular domain experts, for assisting solving data management problems. Specifically we will consider three dimensions of the problem: (1) How domain experts can help in improving the data itself, e.g. by gathering missing data and improving the quality of existing data, (2) How they can assist in gathering meta-data that facilitate improved data processing, and (3) How can we find and identify the most relevant crowd for a given data management task.Tue, 14 Mar 2017 21:43:22 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7064Graphs, Hypergraphs, and the Complexity of Conjunctive Database Queries (Invited Talk)
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7065
The complexity of evaluating conjunctive queries can depend significantly on the structure of the query. For example, it is well known that various notions of acyclicity can make the evaluation problem tractable. More generally, it seems that the complexity is connected to the "treelikeness" of the graph or hypergraph describing the query structure. In the lecture, we will review some of the notions of treelikeness that were proposed in the literature and how they are relevant for the complexity of evaluating conjunctive queries and related problems.Tue, 14 Mar 2017 21:43:22 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7065Distributed Query Monitoring through Convex Analysis: Towards Composable Safe Zones
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7066
Continuous tracking of complex data analytics queries over high-speed distributed streams is becoming increasingly important. Query tracking can be reduced to continuous monitoring of a condition over the global stream. Communication-efficient monitoring relies on locally processing stream data at the sites where it is generated, by deriving site-local conditions which collectively guarantee the global condition. Recently proposed geometric techniques offer a generic approach for splitting an arbitrary global condition into local geometric monitoring constraints (known as "Safe Zones"); still, their application to various problem domains has so far been based on heuristics and lacking a principled, compositional methodology. In this paper, we present the first known formal results on the difficult problem of effective Safe Zone (SZ) design for complex query monitoring over distributed streams. Exploiting tools from convex analysis, our approach relies on an algebraic representation of SZs which allows us to: (1) Formally define the notion of a "good" SZ for distributed monitoring problems; and, most importantly, (2) Tackle and solve the important problem of systematically composing SZs for monitored conditions expressed as Boolean formulas over simpler conditions (for which SZs are known); furthermore, we prove that, under broad assumptions, the composed SZ is good if the component SZs are good. Our results are, therefore, a first step towards a principled compositional solution to SZ design for distributed query monitoring. Finally, we discuss a number of important applications for our SZ design algorithms, also demonstrating how earlier geometric techniques can be seen as special cases of our framework.Tue, 14 Mar 2017 21:43:22 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7066Dagstuhl Reports, Volume 6, Issue 10, September 2016, Complete Issue
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7043
Dagstuhl Reports, Volume 6, Issue 10, September 2016, Complete IssueTue, 14 Mar 2017 08:12:06 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7043Dagstuhl Reports, Table of Contents, Volume 6, Issue 10, 2016
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7042
Table of Contents, FrontmatterTue, 14 Mar 2017 08:11:53 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7042Adaptive Isolation for Predictability and Security (Dagstuhl Seminar 16441)
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=6953
This report documents the program and the outcomes of Dagstuhl Seminar 16441 "Adaptive Isolation for Predictability and Security". Semiconductor technology is at the verge of integrating hundreds of processor cores on a single device. Indeed, affordable multi-processor system-on-a-chip (MPSoC) technology is becoming available. It is already heavily used for acceleration of applications from domains of graphics, gaming (e.g., GPUs) and high performance computing (e.g., Xeon Phi). The potential of MPSoCs is yet to explode for novel application areas of embedded and cyber-physical systems such as the domains of automotive (e.g., driver assistance systems), industrial automation and avionics where non-functional aspects of program execution must be enforceable. Instead of best-effort and average performance, these real-time applications demand timing predictability and/or security levels specifiable on a per-application basis. Therefore the cross-cutting topics of the seminar were methods for temporal and spatial isolation. These methods were discussed for their capabilities to enforce the above non-functional properties without sacrificing any efficiency or resource utilization. To be able to provide isolation instantaneously, e.g., even for just segments of a program under execution, adaptivity is essential at all hardware- and software layers. Support for adaptivity was the second focal aspect of the seminar. Here, virtualization and new adaptive resource reservation protocols were discussed and analyzed for their capabilities to provide application/job-wise predictable program execution qualities on demand at some costs and overheads. If the overhead can be kept low, there is a chance that adaptive isolation, the title of the seminar, may enable the adoption of MPSoC technology for many new application areas of embedded systems.Fri, 10 Mar 2017 07:57:07 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=6953Vocal Interactivity in-and-between Humans, Animals and Robots (VIHAR) (Dagstuhl Seminar 16442)
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=6971
This seminar was held in late 2016 and brought together, for the first time, researchers studying vocal interaction in a variety of different domains covering communications between all possible combinations of humans, animals, and robots. While each of these sub-domains has extensive histories of research progress, there is much potential for cross-fertilisation that currently remains underexplored. This seminar aimed at bridging this gap. In this report, we present the nascent research field of VIHAR and the major outputs from our seminar in the form of prioritised open research questions, abstracts from stimulus talks given by prominent researchers in their respective fields, and open problem statements by all participants.Fri, 10 Mar 2017 07:56:50 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=6971LIPIcs, Volume 66, STACS'17, Complete Volume
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7036
LIPIcs, Volume 66, STACS'17, Complete VolumeMon, 06 Mar 2017 13:44:17 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7036Computation over Compressed Structured Data (Dagstuhl Seminar 16431)
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=6952
This report documents the program and the outcomes of Dagstuhl Seminar 16431 "Computation over Compressed Structured Data".Mon, 06 Mar 2017 12:57:51 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=6952Universality of Proofs (Dagstuhl Seminar 16421)
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=6951
This report documents the program and the outcomes of Dagstuhl Seminar 16421 "Universality of Proofs" which took place October 16-21, 2016.The seminar was motivated by the fact that it is nowadays difficult to exchange proofs from one proof assistant to another one. Thus a formal proof cannot be considered as a universal proof, reusable in different contexts. The seminar aims at providing a comprehensive overview of the existing techniques for interoperability and going further into the development of a common objective and framework for proof developments that support the communication, reuse and interoperability of proofs. The seminar included participants coming from different fields of computer science such as logic, proof engineering, program verification, formal mathematics. It included overview talks, technical talks and breakout sessions. This report collects the abstracts of talks and summarizes the outcomes of the breakout sessions.Wed, 01 Mar 2017 13:34:17 +0100http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=6951