25 Search Results for "Orsi, Giorgio"

Volume

LIPIcs, Volume 68

20th International Conference on Database Theory (ICDT 2017)

ICDT 2017, March 21-24, 2017, Venice, Italy

Editors: Michael Benedikt and Giorgio Orsi

Document
Complete Volume
DOI: 10.4230/LIPIcs.ICDT.2017
LIPIcs, Volume 68, ICDT'17, Complete Volume

Authors: Michael Benedikt and Giorgio Orsi

Published in: LIPIcs, Volume 68, 20th International Conference on Database Theory (ICDT 2017)

Abstract
LIPIcs, Volume 68, ICDT'17, Complete Volume
Cite as

20th International Conference on Database Theory (ICDT 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 68, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Proceedings{benedikt_et_al:LIPIcs.ICDT.2017,
  title =	{{LIPIcs, Volume 68, ICDT'17, Complete Volume}},
  booktitle =	{20th International Conference on Database Theory (ICDT 2017)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-024-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{68},
  editor =	{Benedikt, Michael and Orsi, Giorgio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2017},
  URN =		{urn:nbn:de:0030-drops-70689},
  doi =		{10.4230/LIPIcs.ICDT.2017},
  annote =	{Keywords: Database Management, Normal Forms, Schema and Subschema, Query Languages, \lbrackSystems\rbrack Query Processing, Relational Databases, Distributed Databases}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.ICDT.2017.0
Front Matter, Table of Contents, Preface, Conference Organization, List of Authors

Authors: Michael Benedikt and Giorgio Orsi

Published in: LIPIcs, Volume 68, 20th International Conference on Database Theory (ICDT 2017)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization, List of Authors
Cite as

20th International Conference on Database Theory (ICDT 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 68, pp. 0:i-0:xii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{benedikt_et_al:LIPIcs.ICDT.2017.0,
  author =	{Benedikt, Michael and Orsi, Giorgio},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization, List of Authors}},
  booktitle =	{20th International Conference on Database Theory (ICDT 2017)},
  pages =	{0:i--0:xii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-024-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{68},
  editor =	{Benedikt, Michael and Orsi, Giorgio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2017.0},
  URN =		{urn:nbn:de:0030-drops-70446},
  doi =		{10.4230/LIPIcs.ICDT.2017.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization, List of Authors}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.ICDT.2017.1
Rewritability in Monadic Disjunctive Datalog, MMSNP, and Expressive Description Logics (Invited Talk)

Authors: Cristina Feier, Antti Kuusisto, and Carsten Lutz

Published in: LIPIcs, Volume 68, 20th International Conference on Database Theory (ICDT 2017)

Abstract
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.
Cite as

Cristina Feier, Antti Kuusisto, and Carsten Lutz. Rewritability in Monadic Disjunctive Datalog, MMSNP, and Expressive Description Logics (Invited Talk). In 20th International Conference on Database Theory (ICDT 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 68, pp. 1:1-1:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{feier_et_al:LIPIcs.ICDT.2017.1,
  author =	{Feier, Cristina and Kuusisto, Antti and Lutz, Carsten},
  title =	{{Rewritability in Monadic Disjunctive Datalog, MMSNP, and Expressive Description Logics}},
  booktitle =	{20th International Conference on Database Theory (ICDT 2017)},
  pages =	{1:1--1:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-024-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{68},
  editor =	{Benedikt, Michael and Orsi, Giorgio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2017.1},
  URN =		{urn:nbn:de:0030-drops-70636},
  doi =		{10.4230/LIPIcs.ICDT.2017.1},
  annote =	{Keywords: FO-Rewritability, MDDLog, MMSNP, DL, ontology mediated queries}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.ICDT.2017.2
Graphs, Hypergraphs, and the Complexity of Conjunctive Database Queries (Invited Talk)

Authors: Dániel Marx

Published in: LIPIcs, Volume 68, 20th International Conference on Database Theory (ICDT 2017)

Abstract
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.
Cite as

Dániel Marx. Graphs, Hypergraphs, and the Complexity of Conjunctive Database Queries (Invited Talk). In 20th International Conference on Database Theory (ICDT 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 68, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{marx:LIPIcs.ICDT.2017.2,
  author =	{Marx, D\'{a}niel},
  title =	{{Graphs, Hypergraphs, and the Complexity of Conjunctive Database Queries}},
  booktitle =	{20th International Conference on Database Theory (ICDT 2017)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-024-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{68},
  editor =	{Benedikt, Michael and Orsi, Giorgio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2017.2},
  URN =		{urn:nbn:de:0030-drops-70652},
  doi =		{10.4230/LIPIcs.ICDT.2017.2},
  annote =	{Keywords: Conjunctive queries, treewidth, complexity}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.ICDT.2017.3
The Smart Crowd - Learning from the Ones Who Know (Invited Talk)

Authors: Tova Milo

Published in: LIPIcs, Volume 68, 20th International Conference on Database Theory (ICDT 2017)

Abstract
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.
Cite as

Tova Milo. The Smart Crowd - Learning from the Ones Who Know (Invited Talk). In 20th International Conference on Database Theory (ICDT 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 68, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{milo:LIPIcs.ICDT.2017.3,
  author =	{Milo, Tova},
  title =	{{The Smart Crowd - Learning from the Ones Who Know}},
  booktitle =	{20th International Conference on Database Theory (ICDT 2017)},
  pages =	{3:1--3:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-024-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{68},
  editor =	{Benedikt, Michael and Orsi, Giorgio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2017.3},
  URN =		{urn:nbn:de:0030-drops-70643},
  doi =		{10.4230/LIPIcs.ICDT.2017.3},
  annote =	{Keywords: data management, crowdsourcing}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2017.4
GYM: A Multiround Distributed Join Algorithm

Authors: Foto N. Afrati, Manas R. Joglekar, Christopher M. Re, Semih Salihoglu, and Jeffrey D. Ullman

Published in: LIPIcs, Volume 68, 20th International Conference on Database Theory (ICDT 2017)

Abstract
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.
Cite as

Foto N. Afrati, Manas R. Joglekar, Christopher M. Re, Semih Salihoglu, and Jeffrey D. Ullman. GYM: A Multiround Distributed Join Algorithm. In 20th International Conference on Database Theory (ICDT 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 68, pp. 4:1-4:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{afrati_et_al:LIPIcs.ICDT.2017.4,
  author =	{Afrati, Foto N. and Joglekar, Manas R. and Re, Christopher M. and Salihoglu, Semih and Ullman, Jeffrey D.},
  title =	{{GYM: A Multiround Distributed Join Algorithm}},
  booktitle =	{20th International Conference on Database Theory (ICDT 2017)},
  pages =	{4:1--4:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-024-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{68},
  editor =	{Benedikt, Michael and Orsi, Giorgio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2017.4},
  URN =		{urn:nbn:de:0030-drops-70462},
  doi =		{10.4230/LIPIcs.ICDT.2017.4},
  annote =	{Keywords: Joins, Yannakakis, Bulk Synchronous Processing, GHDs}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2017.5
Top-k Querying of Unknown Values under Order Constraints

Authors: Antoine Amarilli, Yael Amsterdamer, Tova Milo, and Pierre Senellart

Published in: LIPIcs, Volume 68, 20th International Conference on Database Theory (ICDT 2017)

Abstract
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, but can 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.
Cite as

Antoine Amarilli, Yael Amsterdamer, Tova Milo, and Pierre Senellart. Top-k Querying of Unknown Values under Order Constraints. In 20th International Conference on Database Theory (ICDT 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 68, pp. 5:1-5:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{amarilli_et_al:LIPIcs.ICDT.2017.5,
  author =	{Amarilli, Antoine and Amsterdamer, Yael and Milo, Tova and Senellart, Pierre},
  title =	{{Top-k Querying of Unknown Values under Order Constraints}},
  booktitle =	{20th International Conference on Database Theory (ICDT 2017)},
  pages =	{5:1--5:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-024-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{68},
  editor =	{Benedikt, Michael and Orsi, Giorgio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2017.5},
  URN =		{urn:nbn:de:0030-drops-70457},
  doi =		{10.4230/LIPIcs.ICDT.2017.5},
  annote =	{Keywords: uncertainty, partial order, unknown values, crowdsourcing, interpolation}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2017.6
Combined Tractability of Query Evaluation via Tree Automata and Cycluits

Authors: Antoine Amarilli, Pierre Bourhis, Mikaël Monet, and Pierre Senellart

Published in: LIPIcs, Volume 68, 20th International Conference on Database Theory (ICDT 2017)

Abstract
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.
Cite as

Antoine Amarilli, Pierre Bourhis, Mikaël Monet, and Pierre Senellart. Combined Tractability of Query Evaluation via Tree Automata and Cycluits. In 20th International Conference on Database Theory (ICDT 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 68, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{amarilli_et_al:LIPIcs.ICDT.2017.6,
  author =	{Amarilli, Antoine and Bourhis, Pierre and Monet, Mika\"{e}l and Senellart, Pierre},
  title =	{{Combined Tractability of Query Evaluation via Tree Automata and Cycluits}},
  booktitle =	{20th International Conference on Database Theory (ICDT 2017)},
  pages =	{6:1--6:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-024-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{68},
  editor =	{Benedikt, Michael and Orsi, Giorgio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2017.6},
  URN =		{urn:nbn:de:0030-drops-70516},
  doi =		{10.4230/LIPIcs.ICDT.2017.6},
  annote =	{Keywords: query evaluation, tree automata, provenance, treewidth, circuits}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2017.7
The Complexity of Reverse Engineering Problems for Conjunctive Queries

Authors: Pablo Barceló and Miguel Romero

Published in: LIPIcs, Volume 68, 20th International Conference on Database Theory (ICDT 2017)

Abstract
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.
Cite as

Pablo Barceló and Miguel Romero. The Complexity of Reverse Engineering Problems for Conjunctive Queries. In 20th International Conference on Database Theory (ICDT 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 68, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{barcelo_et_al:LIPIcs.ICDT.2017.7,
  author =	{Barcel\'{o}, Pablo and Romero, Miguel},
  title =	{{The Complexity of Reverse Engineering Problems for Conjunctive Queries}},
  booktitle =	{20th International Conference on Database Theory (ICDT 2017)},
  pages =	{7:1--7:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-024-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{68},
  editor =	{Benedikt, Michael and Orsi, Giorgio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2017.7},
  URN =		{urn:nbn:de:0030-drops-70525},
  doi =		{10.4230/LIPIcs.ICDT.2017.7},
  annote =	{Keywords: reverse engineering, conjunctive queries, query by example, definability, treewidth, complexity of pebble games}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2017.8
Answering FO+MOD Queries Under Updates on Bounded Degree Databases

Authors: Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt

Published in: LIPIcs, Volume 68, 20th International Conference on Database Theory (ICDT 2017)

Abstract
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].
Cite as

Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt. Answering FO+MOD Queries Under Updates on Bounded Degree Databases. In 20th International Conference on Database Theory (ICDT 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 68, pp. 8:1-8:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{berkholz_et_al:LIPIcs.ICDT.2017.8,
  author =	{Berkholz, Christoph and Keppeler, Jens and Schweikardt, Nicole},
  title =	{{Answering FO+MOD Queries Under Updates on Bounded Degree Databases}},
  booktitle =	{20th International Conference on Database Theory (ICDT 2017)},
  pages =	{8:1--8:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-024-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{68},
  editor =	{Benedikt, Michael and Orsi, Giorgio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2017.8},
  URN =		{urn:nbn:de:0030-drops-70535},
  doi =		{10.4230/LIPIcs.ICDT.2017.8},
  annote =	{Keywords: dynamic databases, query enumeration, counting problem, first-order logic with modulo-counting quantifiers, Hanf locality}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2017.9
How Many Variables Are Needed to Express an Existential Positive Query?

Authors: Simone Bova and Hubie Chen

Published in: LIPIcs, Volume 68, 20th International Conference on Database Theory (ICDT 2017)

Abstract
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.
Cite as

Simone Bova and Hubie Chen. How Many Variables Are Needed to Express an Existential Positive Query?. In 20th International Conference on Database Theory (ICDT 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 68, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bova_et_al:LIPIcs.ICDT.2017.9,
  author =	{Bova, Simone and Chen, Hubie},
  title =	{{How Many Variables Are Needed to Express an Existential Positive Query?}},
  booktitle =	{20th International Conference on Database Theory (ICDT 2017)},
  pages =	{9:1--9:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-024-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{68},
  editor =	{Benedikt, Michael and Orsi, Giorgio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2017.9},
  URN =		{urn:nbn:de:0030-drops-70545},
  doi =		{10.4230/LIPIcs.ICDT.2017.9},
  annote =	{Keywords: existential positive queries, finite-variable logics, first-order logic, query optimization}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2017.10
Expressive Power of Entity-Linking Frameworks

Authors: Douglas Burdick, Ronald Fagin, Phokion G. Kolaitis, Lucian Popa, and Wang-Chiew Tan

Published in: LIPIcs, Volume 68, 20th International Conference on Database Theory (ICDT 2017)

Abstract
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.
Cite as

Douglas Burdick, Ronald Fagin, Phokion G. Kolaitis, Lucian Popa, and Wang-Chiew Tan. Expressive Power of Entity-Linking Frameworks. In 20th International Conference on Database Theory (ICDT 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 68, pp. 10:1-10:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{burdick_et_al:LIPIcs.ICDT.2017.10,
  author =	{Burdick, Douglas and Fagin, Ronald and Kolaitis, Phokion G. and Popa, Lucian and Tan, Wang-Chiew},
  title =	{{Expressive Power of Entity-Linking Frameworks}},
  booktitle =	{20th International Conference on Database Theory (ICDT 2017)},
  pages =	{10:1--10:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-024-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{68},
  editor =	{Benedikt, Michael and Orsi, Giorgio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2017.10},
  URN =		{urn:nbn:de:0030-drops-70554},
  doi =		{10.4230/LIPIcs.ICDT.2017.10},
  annote =	{Keywords: entity linking, entity resolution, constraints, repairs, certain links}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2017.11
k-Regret Minimizing Set: Efficient Algorithms and Hardness

Authors: Wei Cao, Jian Li, Haitao Wang, Kangning Wang, Ruosong Wang, Raymond Chi-Wing Wong, and Wei Zhan

Published in: LIPIcs, Volume 68, 20th International Conference on Database Theory (ICDT 2017)

Abstract
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.
Cite as

Wei Cao, Jian Li, Haitao Wang, Kangning Wang, Ruosong Wang, Raymond Chi-Wing Wong, and Wei Zhan. k-Regret Minimizing Set: Efficient Algorithms and Hardness. In 20th International Conference on Database Theory (ICDT 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 68, pp. 11:1-11:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{cao_et_al:LIPIcs.ICDT.2017.11,
  author =	{Cao, Wei and Li, Jian and Wang, Haitao and Wang, Kangning and Wang, Ruosong and Chi-Wing Wong, Raymond and Zhan, Wei},
  title =	{{k-Regret Minimizing Set: Efficient Algorithms and Hardness}},
  booktitle =	{20th International Conference on Database Theory (ICDT 2017)},
  pages =	{11:1--11:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-024-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{68},
  editor =	{Benedikt, Michael and Orsi, Giorgio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2017.11},
  URN =		{urn:nbn:de:0030-drops-70569},
  doi =		{10.4230/LIPIcs.ICDT.2017.11},
  annote =	{Keywords: multi-criteria decision-making, regret minimizing set, top-k query}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2017.12
The Design of Arbitrage-Free Data Pricing Schemes

Authors: Shaleen Deep and Paraschos Koutris

Published in: LIPIcs, Volume 68, 20th International Conference on Database Theory (ICDT 2017)

Abstract
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.
Cite as

Shaleen Deep and Paraschos Koutris. The Design of Arbitrage-Free Data Pricing Schemes. In 20th International Conference on Database Theory (ICDT 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 68, pp. 12:1-12:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{deep_et_al:LIPIcs.ICDT.2017.12,
  author =	{Deep, Shaleen and Koutris, Paraschos},
  title =	{{The Design of Arbitrage-Free Data Pricing Schemes}},
  booktitle =	{20th International Conference on Database Theory (ICDT 2017)},
  pages =	{12:1--12:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-024-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{68},
  editor =	{Benedikt, Michael and Orsi, Giorgio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2017.12},
  URN =		{urn:nbn:de:0030-drops-70574},
  doi =		{10.4230/LIPIcs.ICDT.2017.12},
  annote =	{Keywords: data pricing, determinacy, arbitrage}
}
  • Refine by Author
  • 2 Amarilli, Antoine
  • 2 Benedikt, Michael
  • 2 Koutris, Paraschos
  • 2 Milo, Tova
  • 2 Orsi, Giorgio
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 3 treewidth
  • 2 conjunctive queries
  • 2 crowdsourcing
  • 1 Bulk Synchronous Processing
  • 1 Conference Organization
  • Show More...

  • Refine by Type
  • 24 document
  • 1 volume

  • Refine by Publication Year
  • 25 2017

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact