Towards a theory of Fa\c{c}ade-X data access: satisfiability of SPARQL basic graph patterns

Enrico Daga; Luigi Asprino

arxiv: 2602.11756 · v2 · submitted 2026-02-12 · 💻 cs.DB

Towards a theory of Fac{c}ade-X data access: satisfiability of SPARQL basic graph patterns

Luigi Asprino , Enrico Daga This is my paper

Pith reviewed 2026-05-16 05:52 UTC · model grok-4.3

classification 💻 cs.DB

keywords Façade-XSPARQLbasic graph patternssatisfiabilitydata integrationknowledge graphsquery evaluation

0 comments

The pith

An algorithm decides satisfiability of SPARQL basic graph patterns over Façade-X data sources.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a formal account of Façade-X, a technique that lets SPARQL queries run directly against data in formats such as CSV, XML, or relational tables by mapping each format to a restricted RDF-like structure. It concentrates on the question of which basic graph patterns are guaranteed to produce at least one solution when evaluated against any instance of such a structure. The authors supply a decision procedure that answers this question and confirm its practicality through experiments that include real-world queries. The result matters because it lets query planners avoid running patterns that can never succeed and supports more efficient integration pipelines that keep data in its original form.

Core claim

Façade-X specialises RDF to a meta-model that captures any data format expressible by a context-free grammar or the relational model; basic graph patterns over this model are satisfiable precisely when they respect the structural constraints of the meta-model, and this property is decidable by an algorithm that the authors define and implement.

What carries the argument

A decision algorithm that inspects a basic graph pattern against the possible node and edge bindings permitted by the Façade-X meta-model.

Load-bearing premise

The Façade-X meta-model correctly represents every data format that a context-free grammar can describe and the decision procedure is complete for all basic graph patterns written against that model.

What would settle it

A concrete basic graph pattern that the algorithm labels unsatisfiable yet returns at least one solution when run against a real Façade-X implementation, or a satisfiable pattern that the algorithm rejects.

read the original abstract

Data integration is the primary use case for knowledge graphs. However, integrated data are not typically graphs but come in different formats, for example, CSV, XML, or a relational database. Fa\c{c}ade-X is a recently proposed method for providing direct access to an open-ended set of data formats. The method includes a meta-model that specialises RDF to fit general data structures. This model allows to express SPARQL queries targeting data sources with those structures. Previous work formalised Fa\c{c}ade-X and demonstrated how it can theoretically represent any format expressible with a context-free grammar, as well as the relational model. A reference implementation, SPARQL Anything, demonstrates the feasibility of the approach in practice. It is noteworthy that Fa\c{c}ade-X utilises a fraction of RDF, and, consequently, not all SPARQL queries yield a solution (i.e. are satisfiable) when evaluated over a Fa\c{c}ade-X graph. In this article, we consolidate Fa\c{c}ade-X, and we study the satisfiability of basic graph patterns. The theory is accompanied by an algorithm for deciding the satisfiability of basic graph patterns on Fa\c{c}ade-X data sources. Furthermore, we provide extensive experiments with a proof-of-concept implementation, demonstrating practical feasibility, including with real-world queries. Our results pave the way for studying query execution strategies for Fa\c{c}ade-X data access with SPARQL and supporting developers to build more efficient data integration systems for knowledge graphs.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper supplies a new algorithm for deciding BGP satisfiability over Façade-X sources plus experiments on real queries, but the completeness argument needs the full derivation to hold up.

read the letter

The paper gives an algorithm for deciding the satisfiability of SPARQL basic graph patterns over Façade-X data sources and shows through experiments that it works on real queries. This is new because the prior formalization of Façade-X focused on representational completeness for various data formats, but did not address when a query actually has solutions. The new decision procedure fills that gap for a method that is already implemented in SPARQL Anything. The paper does well by connecting the theory to practice. The experiments cover extensive cases including real-world queries, which helps show that the approach is not just theoretical but feasible for data integration tasks where sources are CSV, XML, or relational. The soft spot is the completeness of the algorithm. The stress test highlights that we need assurance the procedure returns satisfiable exactly when there exists a Façade-X instance that satisfies the BGP, covering all patterns allowed by the meta-model. The abstract mentions the algorithm and experiments but does not detail an independent verification for every possible BGP shape. If the full paper includes a rigorous proof that addresses this, the concern is resolved; otherwise it remains a point for referees to check. This work is for people building or studying SPARQL access layers over non-RDF data. A reader focused on query optimization or satisfiability in knowledge graph integration would get direct value from the algorithm and the feasibility results. I would recommend sending it to peer review. The core contribution is clear and the experiments provide supporting evidence, so it merits referee attention even if the proof requires some strengthening.

Referee Report

1 major / 1 minor

Summary. The paper consolidates the Façade-X meta-model for representing diverse data formats (CSV, XML, relational) as a specialization of RDF, provides an algorithm for deciding satisfiability of SPARQL basic graph patterns (BGPs) over Façade-X instances, and reports experiments with a proof-of-concept implementation including real-world queries.

Significance. If the decision procedure is complete, the work would support query optimization and execution strategies for SPARQL-based integration over heterogeneous sources by identifying unsatisfiable BGPs upfront, extending prior formalization that Façade-X can represent any context-free grammar structure.

major comments (1)

[Algorithm and decision procedure section] The section presenting the algorithm (and any accompanying proof or completeness argument) does not establish that the procedure returns 'satisfiable' exactly when a BGP has a solution over some Façade-X instance. The meta-model is claimed to capture all CFG-derived structures, yet no exhaustive argument or reduction shows coverage of every permitted BGP shape (e.g., arbitrary nesting or ordering), which is load-bearing for the central claim.

minor comments (1)

[Abstract] The abstract refers to 'extensive experiments' and 'practical feasibility' but does not name the specific metrics (e.g., runtime, query coverage) or the size/composition of the real-world query set used.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their thorough review and constructive feedback. We address the single major comment point by point below.

read point-by-point responses

Referee: [Algorithm and decision procedure section] The section presenting the algorithm (and any accompanying proof or completeness argument) does not establish that the procedure returns 'satisfiable' exactly when a BGP has a solution over some Façade-X instance. The meta-model is claimed to capture all CFG-derived structures, yet no exhaustive argument or reduction shows coverage of every permitted BGP shape (e.g., arbitrary nesting or ordering), which is load-bearing for the central claim.

Authors: We agree that the original manuscript presented the algorithm without a fully explicit formal proof of correctness and completeness. The Façade-X meta-model (consolidated here from prior formalization) is defined to capture all structures derivable from context-free grammars, which by construction includes arbitrary nesting and ordering. In the revised version we add a detailed proof by structural induction on BGP shape: we show that the decision procedure returns 'satisfiable' if and only if there exists a Façade-X instance (i.e., a valid CFG-derived structure) that matches the BGP. The proof proceeds by reducing satisfiability checking to the existence of a compatible root-to-leaf path in the meta-model tree, thereby covering every permitted BGP shape. revision: yes

Circularity Check

0 steps flagged

No significant circularity in the satisfiability decision procedure

full rationale

The paper introduces a new algorithm for deciding satisfiability of basic graph patterns over the Façade-X meta-model. While it cites the authors' own prior formalization for the meta-model's expressiveness over context-free grammars, the decision procedure itself is presented as an independent contribution whose correctness is not reduced to fitted parameters, self-definitional loops, or load-bearing self-citations. The central claim rests on the algorithm description plus experimental validation rather than renaming or re-deriving prior inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the assumption that the Façade-X meta-model is a faithful specialization of RDF for context-free and relational structures; no new free parameters or invented entities are introduced in the abstract.

axioms (1)

domain assumption Façade-X meta-model correctly represents any data format expressible by a context-free grammar and the relational model
Invoked when claiming that SPARQL queries can be expressed against those structures

pith-pipeline@v0.9.0 · 5586 in / 1244 out tokens · 58233 ms · 2026-05-16T05:52:05.568909+00:00 · methodology

Towards a theory of Fac{c}ade-X data access: satisfiability of SPARQL basic graph patterns

Core claim

What carries the argument

Load-bearing premise

What would settle it

discussion (0)