1 Search Results for "Ceylan, İsmail İlkan"

Document
DOI: 10.4230/LIPIcs.ICDT.2020.5
A Dichotomy for Homomorphism-Closed Queries on Probabilistic Graphs

Authors: Antoine Amarilli and İsmail İlkan Ceylan

Published in: LIPIcs, Volume 155, 23rd International Conference on Database Theory (ICDT 2020)

Abstract
We study the problem of probabilistic query evaluation (PQE) over probabilistic graphs, namely, tuple-independent probabilistic databases (TIDs) on signatures of arity two. Our focus is the class of queries that is closed under homomorphisms, or equivalently, the infinite unions of conjunctive queries, denoted UCQ∞. Our main result states that all unbounded queries in UCQ∞ are #P-hard for PQE. As bounded queries in UCQ∞ are already classified by the dichotomy of Dalvi and Suciu [Dalvi and Suciu, 2012], our results and theirs imply a complete dichotomy on PQE for UCQ∞ queries over probabilistic graphs. This dichotomy covers in particular all fragments in UCQ∞ such as negation-free (disjunctive) Datalog, regular path queries, and a large class of ontology-mediated queries on arity-two signatures. Our result is shown by reducing from counting the valuations of positive partitioned 2-DNF formulae (#PP2DNF) for some queries, or from the source-to-target reliability problem in an undirected graph (#U-ST-CON) for other queries, depending on properties of minimal models.
Cite as

Antoine Amarilli and İsmail İlkan Ceylan. A Dichotomy for Homomorphism-Closed Queries on Probabilistic Graphs. In 23rd International Conference on Database Theory (ICDT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 155, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{amarilli_et_al:LIPIcs.ICDT.2020.5,
  author =	{Amarilli, Antoine and Ceylan, \.{I}smail \.{I}lkan},
  title =	{{A Dichotomy for Homomorphism-Closed Queries on Probabilistic Graphs}},
  booktitle =	{23rd International Conference on Database Theory (ICDT 2020)},
  pages =	{5:1--5:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-139-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{155},
  editor =	{Lutz, Carsten and Jung, Jean Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2020.5},
  URN =		{urn:nbn:de:0030-drops-119295},
  doi =		{10.4230/LIPIcs.ICDT.2020.5},
  annote =	{Keywords: Tuple-independent database, #P-hardness, recursive queries, homomorphism-closed queries}
}
  • Refine by Author
  • 1 Amarilli, Antoine
  • 1 Ceylan, İsmail İlkan

  • Refine by Classification
  • 1 Theory of computation → Database query processing and optimization (theory)

  • Refine by Keyword
  • 1 #P-hardness
  • 1 Tuple-independent database
  • 1 homomorphism-closed queries
  • 1 recursive queries

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2020

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