License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2023.14
URN: urn:nbn:de:0030-drops-177566
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17756/
Go to the corresponding LIPIcs Volume Portal

Amarilli, Antoine

Uniform Reliability for Unbounded Homomorphism-Closed Graph Queries

pdf-format:
LIPIcs-ICDT-2023-14.pdf (0.7 MB)

Abstract

We study the uniform query reliability problem, which asks, for a fixed Boolean query Q, given an instance I, how many subinstances of I satisfy Q. Equivalently, this is a restricted case of Boolean query evaluation on tuple-independent probabilistic databases where all facts must have probability 1/2. We focus on graph signatures, and on queries closed under homomorphisms. We show that for any such query that is unbounded, i.e., not equivalent to a union of conjunctive queries, the uniform reliability problem is #P-hard. This recaptures the hardness, e.g., of s-t connectedness, which counts how many subgraphs of an input graph have a path between a source and a sink.
This new hardness result on uniform reliability strengthens our earlier hardness result on probabilistic query evaluation for unbounded homomorphism-closed queries [Amarilli and Ceylan, 2021]. Indeed, our earlier proof crucially used facts with probability 1, so it did not apply to the unweighted case. The new proof presented in this paper avoids this; it uses our recent hardness result on uniform reliability for non-hierarchical conjunctive queries without self-joins [Antoine Amarilli and Benny Kimelfeld, 2022], along with new techniques.

BibTeX - Entry

@InProceedings{amarilli:LIPIcs.ICDT.2023.14,
  author =	{Amarilli, Antoine},
  title =	{{Uniform Reliability for Unbounded Homomorphism-Closed Graph Queries}},
  booktitle =	{26th International Conference on Database Theory (ICDT 2023)},
  pages =	{14:1--14:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-270-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{255},
  editor =	{Geerts, Floris and Vandevoort, Brecht},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/17756},
  URN =		{urn:nbn:de:0030-drops-177566},
  doi =		{10.4230/LIPIcs.ICDT.2023.14},
  annote =	{Keywords: Uniform reliability, #P-hardness, probabilistic databases}
}

Keywords: Uniform reliability, #P-hardness, probabilistic databases
Collection: 26th International Conference on Database Theory (ICDT 2023)
Issue Date: 2023
Date of publication: 17.03.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI