arXiv preprint ·
SPARQLcirc: Probabilistic Query Evaluation with Provenance Circuits
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Databases
Rebuilding a Field's Open-Problem Catalog from the Literature: A Two-Layer Knowledge Graph, and Why Status Must Stay Proposed
Fidelity Synopses: Pre-Execution Plan Selection for Approximate Vector Search
When Imputation Changes the Nearest Neighbor: Exact Certification of Similarity Retrieval for Incomplete Sensor Time Series
A Multimodal Type 2 Diabetes Registry on DHIS2: A Design and Feasibility Study with the AI-READI Dataset
SpBench: An Agent-Native Framework for Cross-Engine Lakehouse Benchmarking
Get the few papers worth your time in Databases every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.