CS Paper Radar

SPARQLcirc: Probabilistic Query Evaluation with Provenance Circuits

Jingcheng Wu, Ratan Bahadur Thapa, Daniel Hernández, Steffen Staab

cs.DB cs.AI ·submitted 2026-10-29 17:41 UTC · v1

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.

Comment
23 pages, 17 figures, 3 tables. Extended version with full proofs and additional experiments

Closest papers

Nearest neighbours by meaning across the whole index.

GraphRAGProv: GraphRAG Meets How-Provenance

cs.AI cs.DB ·2026-10-27 ·Wadie El Amrani, Luis Galárraga
similarity 0.63
Abstract

GraphRAG systems often use knowledge graphs to retrieve relevant context for an LLM that produces the final answer. That makes answers more inscrutable and therefore less appealing for domains where transparency is paramount. We present GraphRAGProv, an architecture that executes SPARQL queries over source-grounded RDF graphs to compute answers and their how-provenance polynomials. These polynomials record which statement occurrences were used and how they were combined. Because each occurrence is linked to its source text, users can follow these links to check whether the extracted statements reflect the text and whether the query combines them to answer the question. Querying thereby becomes a way to inspect and evaluate the text-to-graph transformation. Our interactive demo examines 400 cases from two multi-hop QA benchmarks, revealing extraction and query errors even when the final answer is correct.

0.19

Build2SPARQL: A Large-Scale Text-to-SPARQL Benchmark Dataset for Building Knowledge Graph Querying

cs.AI ·2026-09-22 ·Wooyoung Jung
benchmarkcode/data similarity 0.59
Abstract · 26 pages, 2 figures, 16 tables. Data paper. Dataset openly available at https://zenodo.org/records/20451474. Under review at the ASCE Journa…

Building automation systems are increasingly represented as semantic knowledge graphs (KGs) using ontologies such as Brick and ASHRAE 223P, creating a machine-readable substrate for artificial-intelligence applications. One promising application is translating natural-language questions into SPARQL (text-to-SPARQL), which would let building operators query these graphs through language agents, but progress is limited by the scarcity of large natural-language/SPARQL benchmarks. This paper presents Build2SPARQL, a large-scale benchmark for building KGs generated by a KG-grounded pipeline: SPARQL queries are produced and validated entirely by graph-traversal code, while large language models generate only the natural-language questions, keeping query correctness independent of model behavior. The pipeline mines six query-pattern families -- linear chains, branching, UNION, aggregation, OPTIONAL, and attribute-filtered -- and phrases each query across five vocabulary registers. Applied to 201 building KGs (180 Brick, 21 ASHRAE 223P), it yields 6,136 executable SPARQL queries and 30,680 questions. A two-rater human validation of 300 questions found 98.8% semantic fidelity, 98.8% naturalness, and 84.0% operational plausibility. A retrieval-augmented evaluation across three open-weight language models raised exact-match accuracy from 0.2-20% (zero-shot) to 56-65% (three-shot retrieved).

0.21

Diverse Why-Provenance for Datalog Queries

cs.DB ·2026-10-17 ·Marco Calautti, Mostafa Milani, Andreas Pieris
similarity 0.59
Abstract · Extended version of a conference submission

Datalog is a powerful rule-based language that allows us to express complex recursive queries and has found numerous applications over the years. Explaining why a result to a Datalog query is obtained is an essential task towards explainable and transparent data-intensive applications that rely on Datalog. A standard way of explaining a query result is the so-called why-provenance, which provides information about the witnesses to a query result in the form of subsets of the input database that as a whole can be used to derive that result. The state-of-the-art approach for efficiently computing the why-provenance explanations of a certain query result aims at enumerating, without repetitions, the relevant explanations by relying on off-the-shelf SAT solvers. However, whenever the set of explanations is very large, outputting the entire set might be prohibitively expensive. Moreover, it is questionable the practical usefulness of flooding the user with a very large number of explanations, many of them possibly differing only marginally. In this case, one can argue that it would be practically more useful to compute a small, sufficiently diverse subset of the set of why-provenance explanations. The present work initiates the study of the latter problem. In particular, we formalize the problem of interest as an optimization problem, and, after showing that it is highly intractable (it is NP-hard even in data complexity), we investigate whether ILP optimization solvers can be employed towards practical solutions. Our main finding is that this is achievable as long as we keep the requested set of explanations small, or we employ approximation algorithms (with error guarantees).

0.20

On Knowledge Compilation Languages for QBFs

cs.CC ·2026-10-14 ·Sravanthi Chede, Vaibhav Krishan, Anil Shukla
published similarity 0.59
Abstract · To be published in FSTTCS-2026

In this work, we design knowledge compilation languages for quantified Boolean formulas (QBFs), with a particular focus on model counting. We introduce various languages in increasing order of their power of representation, starting from a simple tree-based structure, and extending it to DAGs for a more efficient representation. We study the power and limitations of each language. We also show that QBF queries such as model counting and MaxQBF are easy to handle in all these languages. These languages naturally lead to various static proof systems for the #QBF problem, the model-counting version of the QBF problem. We compare these systems with one another and with a recently introduced line-based #QBF-system called Q-MICE (Chede, Chew, Krishan and Shukla, SAT `26). We show that a minor extension of the Q-MICE system efficiently simulates all these static proof systems, and is in fact exponentially stronger than each of them. We also initiate the implementation of a solver based on these languages. The solver compiles a representation of an input QBF in the proposed tree-like language, which is subsequently used for model counting. This is the first knowledge compilation based solver for #QBF which can handle QBFs with doubly exponential model counts as well. Experimentally, we compare its performance with the state-of-the-art #QBF-solver d4-QBF which works well for QBFs with small model counts.

0.26

Enabling Knowledge Graph Understanding at Scale with the EXplore Your Graphs ENgine (EXYGEN)

cs.AI cs.LG ·2026-09-10 ·Harshdeep Singh, Yurui Zhu, Giovanni Colavizza, Matteo Romanello
benchmark similarity 0.58
Abstract

We present EXYGEN (EXplore Your Graphs ENgine), a framework for knowledge graph (KG) understanding that enables conversational access to KGs at scale. We address two questions in sequence. First, how effectively can LLMs perform text-to-SPARQL generation given only automatically derived structured metadata and small graph samples, rather than task-specific fine-tuning? We integrate VoID descriptions and ShEx schemas into a retrieval-augmented generation (RAG) pipeline and ablate KG-derived context on the SciQA benchmark. Our best configuration -- combining ShEx schemas, retrieved triples, and example question-query pairs -- reaches an exact match of 0.419 on execution results without any LLM fine-tuning. We further find that lexical metrics such as F1 poorly predict query correctness, and that larger general-purpose LLMs can outperform smaller code-specialized ones once given sufficient context. Second, we ask how to generate the structured metadata that this method relies on from very large KGs, where KG metadata generation becomes computationally intractable. We introduce a predicate-coverage-aware parallel graph sampling strategy that preserves structural diversity while remaining computationally tractable. On OpenCitations Meta and GESIS, it retains high predicate coverage with minimal triple loss and reduces runtime by over 80x; on ORKG, sampling is not just faster but the only tractable path to obtain complete metadata. Together, these results show that structured schema context and lightweight prompting can substantially reduce reliance on fine-tuning for scalable conversational access to KGs, though closing the remaining gap to fully fine-tuned approaches will likely require reducing dependence on curated question-query exemplars -- whether through synthetic generation or an execution-feedback-driven approach -- and validating these findings beyond a single benchmark.

0.18

PAGR: Proof-Carrying Algebraic-Geometric Retrieval: A Quiver-, Provenance-, and Sheaf-Theoretic Framework for Grounded LLM Retrieval

cs.AI math.RTcs.IR ·2026-09-05 ·Xingting Wang, Min Wu
similarity 0.58
Abstract · 42 pages

Retrieval-augmented generation is usually formulated as a statistical information-retrieval problem. Graph-based variants add relational structure, but the mathematical status of that structure is often left underspecified. Three distinct questions tend to be conflated: which statements are certified as knowledge, which latent representations are useful for retrieval, and which multi-hop compositions are semantically admissible. We propose Proof-Carrying Algebraic-Geometric Retrieval (PAGR), a framework that separates these questions mathematically. Its symbolic layer is a many-sorted relational theory generated by a typed quiver, path equations, and positive Horn inclusions. A quiver representation assigns inner-product spaces to entity types and linear operators to relations. A cellular sheaf measures local-to-global consistency. Semiring provenance records derivations and supports machine-checkable certificates. The central principle is epistemic separation: learned geometry may rank and organize evidence, but cannot promote a hypothesis to certified ground truth. We show the certification criterion is invariant under arbitrary replacement of learned components. Further results include a conditional completeness bound, identification of the isometry group as the relevant symmetry for residual-based retrieval, a cohomological consistency diagnostic, and a bounded-bisimulation index for admissible-path expansion. PAGR is a mathematical architecture for separating where a system should look from what it is allowed to treat as knowledge.

0.29

Constrained Entity Selection under Partial Knowledge for LLM-Based Knowledge Graph QA

cs.AI ·2026-08-25 ·Emanuel Kitzelmann
published similarity 0.58
Abstract · 8 pages, 2 tables. Submitted manuscript. Revised version published in KI 2026: Advances in Artificial Intelligence, LNCS 16830

Large language models are increasingly used for knowledge graph question answering (KGQA), but can fail to correctly ground answers in the underlying graph. Current approaches to LLM-based KGQA either rely on full semantic parsing into executable queries such as SPARQL, which is brittle in practice due to complex schemas or incompleteness of real-world KGs, or on LLM-reasoning and answer generation over KGs, which can be more robust but lacks formal guarantees. In this work, we study a complementary setting in which \emph{candidate} answers are generated by an LLM-based system and subsequently verified using lightweight symbolic constraints derived from the question. We introduce \emph{Constrained Entity Selection under Partial Knowledge (CES-PK)}, a problem formulation that focuses on eliminating invalid answers and providing symbolic support for valid ones without requiring construction of executable logical forms. To account for incomplete KGs, we employ a three-valued constraint semantics (\emph{satisfied, violated, unknown}) that avoids incorrect rejections under open-world assumptions. To demonstrate the effects of our method, we instantiate this framework over the Hetionet biomedical knowledge graph and evaluate the impact of type, relation, and exclusion constraints. Experiments show that precision improves by filtering invalid candidates, while recall is preserved due to retaining candidates whose constraints are not explicitly violated. Satisfied constraints provide additional positive symbolic evidence to rank remaining candidates.

0.34

The Complexity of Computing Class Probabilities in BID Probabilistic Databases

cs.DS ·2026-09-18 ·Sotiris Kanellopoulos, Ioannis Koutras, Aris Pagourtzis
theory similarity 0.58
Abstract

We study the problem of computing class probabilities in block-independent disjoint (BID) probabilistic databases. Given the probability with which each block in the database realizes each feasible tuple type, the goal is to compute the probability of a class of worlds specified by a given tuple multiplicity vector, thus grouping together worlds with the same bag (multiset) of realized tuple types. For this problem, we prove $\#\mathsf{P}$-hardness even for very restricted and structured inputs. On the other hand, we show that it admits an FPRAS, as well as $\mathsf{XP}$-time algorithms parameterized by the number of tuple types and the treewidth of an incidence graph modeling the connections between blocks and tuples. Finally, we show that augmenting the problem with certain compatibility constraints between block realizations renders it $\#\mathsf{XLP}$- and $\#\mathsf{XALP}$-hard parameterized by pathwidth and treewidth respectively, ruling out $\mathsf{FPT}$ algorithms under standard assumptions. We leave as an open question whether this also holds in the absence of compatibility constraints.

0.32