Metraipolis › archive › dc_dfd2d3e13700

SPARQLcirc: Probabilistic Query Evaluation with Provenance Circuits — arXiv:2611.00128

Source: arXiv (en)
Original: https://arxiv.org/abs/2611.00128
License (as archived): CC0-1.0
Archived: 2026-11-03T10:45:44.737Z
SHA-256 of the archived text: 1398bed2315dd88bb6d60164cd6e1dabbac37c43f13b6157f932e4a0e15624bf
Stable URL of this page: https://metraipolis.com/documento/dc_dfd2d3e13700

How to cite

SPARQLcirc: Probabilistic Query Evaluation with Provenance Circuits — arXiv:2611.00128 — arXiv (en), https://arxiv.org/abs/2611.00128 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_dfd2d3e13700 (Metraipolis archive dc_dfd2d3e13700, sha256 1398bed2315dd88bb6d60164cd6e1dabbac37c43f13b6157f932e4a0e15624bf)

BibTeX

@misc{dcdfd2d3e13700,
  title = {SPARQLcirc: Probabilistic Query Evaluation with Provenance Circuits — arXiv:2611.00128},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.00128},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_dfd2d3e13700; sha256 1398bed2315dd88bb6d60164cd6e1dabbac37c43f13b6157f932e4a0e15624bf},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.00128. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Probabilistic query evaluation (PQE) computes the probability of every answer of a query over a tuple-independent probabilistic knowledge graph. We study exact PQE for SPARQL over graphs accessed through SPARQL 1.1 endpoints. Shared triples among the derivations of an answer make exact PQE #P-hard in general. Knowledge compilation of the Boolean provenance of every answer yields exact probabilities, and the provenance formulas of different answers can share subformulas. We propose SPARQLcirc, which rewrites a SPARQL query into CONSTRUCT queries that name every gate by its content, so that the results of independent queries form one Boolean provenance circuit for all answers. The rewriting covers joins, unions, projection, filters, OPTIONAL, difference, and transitive closures. SPARQLcirc compiles the circuit and computes the exact probability of every answer by weighted model counting. For the evaluation, we draw random probabilities for the triples of WatDiv and gMark and the statements of Wikidata and evaluate the CONSTRUCT queries on GraphDB, Fuseki, and Oxigraph. The ratio of the end-to-end time of PQE with SPARQLcirc to that of PQE by compiling the provenance expressions of the SPARQL provenance rewriting NPCS decreases with the number of derivations.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.AI, nuovi lavori del giorno).
Categorie arXiv: Databases (cs.DB) ; Artificial Intelligence (cs.AI).
Pagina del lavoro: https://arxiv.org/abs/2611.00128 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T10:39:50.381Z dalla pagina https://arxiv.org/list/cs.AI/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).