RelShap: Relationally Consistent Shapley Explanations

# RelShap: Relationally Consistent Shapley Explanations
Source: [https://arxiv.org/html/2608.11508](https://arxiv.org/html/2608.11508)
###### Abstract

Machine learning pipelines commonly flatten relational data into single\-table representations, discarding structural constraints\. Widely used Shapley value\-based feature attributions then rely on feature independence, evaluating the model on combinations that could never arise in the underlying data, producing misleading explanations\. We proposeRelShap, a framework that incorporates relational constraints and data provenance into Shapley value computation, restricting both background data and coalition evaluation to relationally valid configurations\. The framework is estimator\-agnostic and composes with Kernel SHAP, Monte Carlo, and Leverage SHAP without altering their sampling or weighting properties\. Functional dependencies further induce equivalence classes over feature coalitions, whichRelShapexploits to reduce runtime without changing Shapley values; we provide a combinatorial characterization of the expected speedup\. Experiments across multiple datasets, models, and estimators show thatRelShapproduces explanations that are more faithful to the data\-generating process, correctly identifying the dominant feature in controlled settings where existing methods, including Conditional SHAP and ManifoldShap, do not\. Our code is available at:https://github\.com/duneag2/relshap\.

## 1Introduction

Most machine learning \(ML\) pipelines flatten relational data into single\-table representations for model training\([17](https://arxiv.org/html/2608.11508#bib.bib18)\)\. Once a predictive model is trained on such a flattened table, practitioners routinely seek to understand its predictions at the level of individual instances\. Shapley value\-based attributions\([48](https://arxiv.org/html/2608.11508#bib.bib21);[11](https://arxiv.org/html/2608.11508#bib.bib7);[34](https://arxiv.org/html/2608.11508#bib.bib6)\)have become a dominant approach for this purpose, assigning each input feature a score based on its contribution to the prediction\. Notably, relational ML is a well\-established setting\([46](https://arxiv.org/html/2608.11508#bib.bib19);[16](https://arxiv.org/html/2608.11508#bib.bib20)\), yet approaches that train directly on multi\-table data must ultimately attribute predictions to individual features and thus face the same explanation\-time flattening\.

In practice, this computation requires two conceptual choices:*background data selection*, which determines how feature absence is simulated using reference data, and*coalition selection*, which specifies which feature subsets are evaluated\. Existing methods instantiate different sides of the tension between being*true to the model*and*true to the data*\([6](https://arxiv.org/html/2608.11508#bib.bib15);[19](https://arxiv.org/html/2608.11508#bib.bib14);[28](https://arxiv.org/html/2608.11508#bib.bib13)\)\. SHAP\([34](https://arxiv.org/html/2608.11508#bib.bib6)\), the most widely used implementation, stays*true to the model*by assuming feature independence but potentially considers feature combinations that never arise in the data\.[1](https://arxiv.org/html/2608.11508#bib.bib8)instead remain*true to the data*by estimating conditional distribution, but only as true as the estimate itself, and the estimator’s errors propagate directly into the attributions\.

Both premises are problematic on data drawn from a relational database\. The flattening step can discard database\-level information, such as functional dependencies \(FDs\) that imply that some features are fully determined by others, and domain constraints that restrict admissible values\. Feature independence is violated by these very constraints, and conditional distribution estimation, while potentially avoiding that violation, introduces its own modeling assumptions\. When attribution methods ignore relational constraints, they may evaluate the model on inputs that could never arise from the underlying relational data, thereby fundamentally altering the resulting feature attributions\.

##### Core contribution:

We presentRelShap—*Relationally Consistent Shapley Explanations*—the first framework to integrate relational database constraints into Shapley value\-based feature attributions\.RelShapchanges the admissible space of the Shapley explanation itself: instead of relying on feature independence assumptions or additional distributional modeling, it restricts both background data and coalitions to relationally valid configurations through constraints derived from the database schema, query, and data\. Importantly, in controlled settings with known ground truth,RelShapcorrectly identifies the dominant feature where Kernel SHAP, Conditional SHAP, and ManifoldShap do not \(Section[4\.1](https://arxiv.org/html/2608.11508#S4.SS1)\)\. For instance, in a loan approval scenario \(Example[1](https://arxiv.org/html/2608.11508#Thmexample1)\), the explanation changes substantially depending on whether relational constraints are respected \(Figure[1](https://arxiv.org/html/2608.11508#S1.F1)\)\. The divergence is not a sampling artifact but a consequence of which feature combinations the explanation method permits\.

###### Example 1\.

Consider two tables,Applicants\(a\_id,age,life\_stage,empl\) andTransactions\(t\_id,a\_id,amount\), linked by applicant identifiera\_id\. Six representative applicants and their transactions are shown in Tables[1\(a\)](https://arxiv.org/html/2608.11508#S1.T1.st1)and[1\(b\)](https://arxiv.org/html/2608.11508#S1.T1.st2)\. A data analyst issues the query:

SELECTa\.a\_id,a\.age,a\.life\_stage,a\.empl,

SUM\(t\.amount\)AStotal\_amt

FROMApplicantsa,Transactionst

WHEREa\.a\_id=t\.a\_id

GROUPBYa\.a\_id,a\.age,a\.life\_stage,a\.empl;

to obtain an applicant\-level view, then drops the identifiera\_idand adds a targetloan\_approvedto yield the ML\-ready dataset in Table[1\(c\)](https://arxiv.org/html/2608.11508#S1.T1.st3)\.

ML practitioners computing explanations typically receive only this final flattened representation, with no visibility into the upstream structure\. Applicanta27applied for a loan, was rejected, and sought an explanation\. Kernel SHAP\([34](https://arxiv.org/html/2608.11508#bib.bib6)\), a widely used method, reportslife\_stageas the top driver of the prediction with a positive score \(Figure[1\(a\)](https://arxiv.org/html/2608.11508#S1.F1.sf1)\)\. This attribution, however, is an artifact of relationally invalid completions from Kernel SHAP\. For instance, fixingage=35\\texttt\{age\}=35and filling in the rest from applicanta29yields the combination\(age=35,life\_stage=older\)\(\\texttt\{age\}=35,\\texttt\{life\\\_stage\}=\\texttt\{older\}\), which is impossible under the FDage→life\_stage\\texttt\{age\}\\rightarrow\\texttt\{life\\\_stage\}\(first row of Table[1\(d\)](https://arxiv.org/html/2608.11508#S1.T1.st4)\)\.

RelShapinstead operates over a space of relationally valid completions, automatically extracting constraints from the data’s relational structure\. In this example, the data reveals a*functional dependency*\(FD\)age→life\_stage\\texttt\{age\}\\rightarrow\\texttt\{life\\\_stage\}: each age value maps to exactly one life stage\. Similarly, because the query aggregates all of an applicant’s transactions into a single row, each applicant identifier determines exactly onetotal\_amt\.RelShapenforces these constraints during Shapley computation: fixingage=35\\texttt\{age\}=35forceslife\_stage=middle\\texttt\{life\\\_stage\}=\\texttt\{middle\}\(second row of Table[1\(d\)](https://arxiv.org/html/2608.11508#S1.T1.st4)\); the remaining attributes are unconstrained and filled from a chosen background data point \(a29\)\. Additionally,RelShapsupports a*provenance\-aware*mode that traces each row of the flattened table back to its source tuples in the original tables\. Fixingage=35\\texttt\{age\}=35narrows the provenance toa27, the sole applicant with that age, at which point the schema determinesempl=self\_emp\\texttt\{empl\}=\\texttt\{self\\\_emp\}andtotal\_amt=119\\texttt\{total\\\_amt\}=119\(third row of Table[1\(d\)](https://arxiv.org/html/2608.11508#S1.T1.st4)\)\. Provenance\-based recovery is not always available when it does not resolve to a single tuple:age=63\\texttt\{age\}=63, for instance, is shared bya12anda29\. See Appendix[A](https://arxiv.org/html/2608.11508#A1)for a primer on relational concepts and a detailed description of howRelShapextracts constraints from the database schema, query structure, and data\.

Notably,*RelShapcomputes different Shapley values even without approximation\.*Under bothRelShapvariants,life\_stagereceives*exactly zero*attribution \(which does not necessarily generalize\), down from\+0\.2299\+0\.2299under Kernel SHAP \(Figure[1](https://arxiv.org/html/2608.11508#S1.F1)\), because the discovered FDage→life\_stage\\texttt\{age\}\\rightarrow\\texttt\{life\\\_stage\}makeslife\_stageredundant whenageis present in a coalition, once coalitions are projected to relationally valid completions \(Section[3](https://arxiv.org/html/2608.11508#S3)\)\. Kernel SHAP ignores this redundancy and distributes substantial attribution tolife\_stage\. The top\-ranked feature consequently changes fromlife\_stagetoage\. In all three cases, feature attribution values are computed*exactly*, over all background points and all coalitions; the divergence is not a sampling artifact but a consequence of which feature combinations the explanation method permits\.

Our contributions are as follows:

Table 1:Running example \(excerpt\)\(a\)Applicants\(excerpt\)a\_idagelife\_stageempla1263olderunempa1426youngunempa2454middleempa2522youngself\_empa2735middleself\_empa2963olderunemp
\(b\)Transactions\(excerpt\)t\_ida\_idamountt62a2547t67a2743t68a2759t69a2717t73a2950⋮\\vdots
\(c\)Flattened, ML\-ready dataset \(excerpt\):a27is highlighted\.agelife\_stageempltotal\_amtloan\_approved63olderunemp264126youngunemp94054middleemp235122youngself\_emp100035middleself\_emp119063olderunemp1140
\(d\)Completions forage=35\\texttt\{age\}=35under increasing relational awareness\. The first row violates the FDage→life\_stage\\texttt\{age\}\\rightarrow\\texttt\{life\\\_stage\}\.agelife\_stageempltotal\_amtKernel SHAP \(unaware\)35olderunemp114RelShap\(FDs only\)35middleunemp114RelShap\(FDs \+ provenance\)35middleself\_emp119

\(a\)Kernel SHAP\.\(b\)RelShap\(FDs only\)\.\(c\)RelShap\(FDs and provenance\)\.
Figure 1:Kernel SHAP vs\.RelShapfeature attributions for applicanta27in Example[1](https://arxiv.org/html/2608.11508#Thmexample1)under an XGBoost classifier\.1. 1\.RelShapalters both background data and coalition selection under relational constraints, producing attributions that correctly reflect the data\-generating structure \(Section[4\.1](https://arxiv.org/html/2608.11508#S4.SS1)\)\.
2. 2\.RelShapis agnostic to the choice of background data and coalition estimator: it enforces relational validity as a plug\-in restriction layer while preserving the chosen background modeling approach and the base estimator’s sampling and weighting scheme\.
3. 3\.*Computational effects:*RelShapachieves*orthogonal acceleration*by avoiding redundant coalition evaluations while preserving Shapley values \(Prop\.[1](https://arxiv.org/html/2608.11508#Thmproposition1)\)\. We combinatorially characterize the resulting speedup factor as a function of the coalition estimator and FD structure \(Thm\.[1](https://arxiv.org/html/2608.11508#Thmtheorem1)\)\.
4. 4\.We evaluateRelShapon 9 datasets across 4 models and 3 coalition estimators, empirically validating both the*semantic effects*and the runtime predictions of Thm\.[1](https://arxiv.org/html/2608.11508#Thmtheorem1)\.

## 2Preliminaries & Related Work

LetFFbe the set of input features,f:ℝ\|F\|→ℝf:\\mathbb\{R\}^\{\|F\|\}\\rightarrow\\mathbb\{R\}a predictive model trained on𝒟train\\mathcal\{D\}\_\{\\mathrm\{train\}\}, and𝐱∈𝒟test\\mathbf\{x\}\\in\\mathcal\{D\}\_\{\\mathrm\{test\}\}an instance to be explained\. To explain the predictionf⁡\(𝐱\)f\(\\mathbf\{x\}\), for any coalitionS⊆FS\\subseteq F,𝐱S\\mathbf\{x\}\_\{S\}denotes the projection of𝐱\\mathbf\{x\}ontoSS\. The Shapley value of featurei∈Fi\\in Fis defined as

ϕi​\(f\)=∑S⊆F∖\{i\}\|S\|\!​\(\|F\|−\|S\|−1\)\!\|F\|\!​\(f⁡\(𝐱S∪\{i\}\)−f⁡\(𝐱S\)\)\.\\phi\_\{i\}\(f\)=\\sum\_\{S\\subseteq F\\setminus\\\{i\\\}\}\\frac\{\|S\|\!\(\|F\|\-\|S\|\-1\)\!\}\{\|F\|\!\}\\bigl\(f\(\\mathbf\{x\}\_\{S\\cup\\\{i\\\}\}\)\-f\(\\mathbf\{x\}\_\{S\}\)\\bigr\)\.\(1\)
As discussed in Section[1](https://arxiv.org/html/2608.11508#S1), computing Eq\. \([1](https://arxiv.org/html/2608.11508#S2.E1)\) in practice requires two design choices:*background data selection*, which determines how features inF∖SF\\setminus Sare filled in when evaluatingff, and*coalition selection*, which subsetsS⊆F∖\{i\}S\\subseteq F\\setminus\\\{i\\\}are evaluated\. Since exhaustive enumeration over reference points and over the2\|F\|−12^\{\|F\|\-1\}coalitions is infeasible in practice, both are typically operationalized via*sampling*\. The two dimensions admit a multiplicity of instantiations\([49](https://arxiv.org/html/2608.11508#bib.bib12)\)and are typically treated as orthogonal\([57](https://arxiv.org/html/2608.11508#bib.bib10);[6](https://arxiv.org/html/2608.11508#bib.bib15)\)\.RelShapoperates at the level of*selection*rather than*sampling*: it restricts the admissible background and coalition spaces to relationally valid configurations, so it applies whether the values are then computed exactly or approximated by any estimators\. Appendices[B\.1](https://arxiv.org/html/2608.11508#A2.SS1)and[C](https://arxiv.org/html/2608.11508#A3)provide additional details\.

### 2\.1Background Data Selection

Let𝒫bg​\(𝐳F∖S\)\\mathcal\{P\}\_\{\\mathrm\{bg\}\}\(\\mathbf\{z\}\_\{F\\setminus S\}\)denote a background distribution over the absent features indexed byF∖SF\\setminus S, andBBbe the number of background samples \(possibly all reference data points\)\. With a completed input𝐱~​\(S,𝐳F∖S\)∈ℝ\|F\|\\tilde\{\\mathbf\{x\}\}\(S,\\mathbf\{z\}\_\{F\\setminus S\}\)\\in\\mathbb\{R\}^\{\|F\|\}, we define

f⁡\(𝐱S\)=𝔼𝐳F∖S∼𝒫bg​\[f⁡\(𝐱~​\(S,𝐳F∖S\)\)\]\.f\(\\mathbf\{x\}\_\{S\}\)=\\mathbb\{E\}\_\{\\mathbf\{z\}\_\{F\\setminus S\}\\sim\\mathcal\{P\}\_\{\\mathrm\{bg\}\}\}\\Bigl\[f\\bigl\(\\tilde\{\\mathbf\{x\}\}\(S,\\mathbf\{z\}\_\{F\\setminus S\}\)\\bigr\)\\Bigr\]\.
Methods differ in their choice of𝒫bg\\mathcal\{P\}\_\{\\mathrm\{bg\}\}\.*Interventional methods*\([28](https://arxiv.org/html/2608.11508#bib.bib13);[57](https://arxiv.org/html/2608.11508#bib.bib10)\), including default Kernel SHAP\([34](https://arxiv.org/html/2608.11508#bib.bib6)\), treat feature absence as an intervention and fill absent features from the empirical marginal distribution, which is assumption\-light but can break feature dependencies\.*Conditional SHAP*\([1](https://arxiv.org/html/2608.11508#bib.bib8)\)instead estimates the distribution of absent features given the observed ones, aiming to preserve dependencies but potentially introducing estimator error\.*Causal methods*\([25](https://arxiv.org/html/2608.11508#bib.bib9)\)intervene through a causal graph among the features, and*ManifoldShap*\([50](https://arxiv.org/html/2608.11508#bib.bib11)\)restricts completions to an estimated data manifold\. These methods span the*true to the model*vs\.*true to the data*axis discussed in Section[1](https://arxiv.org/html/2608.11508#S1)\(see Appendices[B\.2](https://arxiv.org/html/2608.11508#A2.SS2),[B\.3](https://arxiv.org/html/2608.11508#A2.SS3)for details\)\.

Importantly,RelShapis*orthogonal*to this axis: rather than choosing*what distribution*to put on the absent features, it constrains*which configurations*the chosen distribution is allowed to place mass on under relational constraints\. The two design dimensions therefore compose rather than conflict:RelShapcan be layered on top of any background data selection method\. By default we use marginal \(feature independence\) as the base when no relational constraints are available \(Def\.[1](https://arxiv.org/html/2608.11508#Thmdefinition1)\), to comply with the no\-distributional\-assumptions property\([49](https://arxiv.org/html/2608.11508#bib.bib12);[28](https://arxiv.org/html/2608.11508#bib.bib13)\)while removing the structurally infeasible inputs that[19](https://arxiv.org/html/2608.11508#bib.bib14)and[50](https://arxiv.org/html/2608.11508#bib.bib11)warn about\.

### 2\.2Coalition Selection

We drawMMcoalitions from a coalition distribution𝒫coal\\mathcal\{P\}\_\{\\mathrm\{coal\}\}overS⊆F∖\{i\}S\\subseteq F\\setminus\\\{i\\\}and approximate

ϕi​\(f\)≈1M​∑m=1Mw⁡\(S\(m\)\)​\(f⁡\(𝐱S\(m\)∪\{i\}\)−f⁡\(𝐱S\(m\)\)\)\.\\phi\_\{i\}\(f\)\\approx\\frac\{1\}\{M\}\\sum\_\{m=1\}^\{M\}w\\bigl\(S^\{\(m\)\}\\bigr\)\\Bigl\(f\(\\mathbf\{x\}\_\{S^\{\(m\)\}\\cup\\\{i\\\}\}\)\-f\(\\mathbf\{x\}\_\{S^\{\(m\)\}\}\)\\Bigr\)\.Different Shapley value estimators choose different𝒫coal\\mathcal\{P\}\_\{\\mathrm\{coal\}\}and importance weightww\.*Kernel SHAP*\([34](https://arxiv.org/html/2608.11508#bib.bib6)\)fits a weighted linear surrogate using the Shapley kernel, which concentrates weight on extreme \(very small or large\) coalition sizes\.*Monte Carlo \(MC\)*estimator samples coalitions from the Shapley\-weighted distribution, with coalition sizes sampled approximately uniformly\.*Leverage SHAP*\([39](https://arxiv.org/html/2608.11508#bib.bib22)\)uses leverage score\-based sampling, sampling the coalition size nearly uniformly and then sampling a coalition uniformly within that size\. Recent variants further improve estimation through residual estimation\([54](https://arxiv.org/html/2608.11508#bib.bib30)\)or Fourier basis reduction\([20](https://arxiv.org/html/2608.11508#bib.bib29)\)\.

RelShapis*estimator\-agnostic*and provides*orthogonal acceleration*: it preserves any base estimator’s sampling distribution, weights, and accuracy guarantees, canonicalizing sampled coalitions under relational validity \(Def\.[2](https://arxiv.org/html/2608.11508#Thmdefinition2)\)\.[55](https://arxiv.org/html/2608.11508#bib.bib32)also uses equivalence classes, but derives them from structural causal models \(see Appendix[H\.1](https://arxiv.org/html/2608.11508#A8.SS1)for a detailed comparison\)\.[35](https://arxiv.org/html/2608.11508#bib.bib47)studies lattice\-structured coalition spaces to reduce computations, but not for ML predictions\.

### 2\.3Relational Structure in ML Data

Many ML datasets originate from relational databases, where data is organized into multiple tables linked by keys\. Flattening this structure into a single table for model training discards integrity constraints that govern valid data combinations\. A*functional dependency*\(FD\)A→BA\\rightarrow Bstates that the value of attributes inAAuniquely determines the value ofBB; for instance, in Example[1](https://arxiv.org/html/2608.11508#Thmexample1),age→life\_stage\\texttt\{age\}\\rightarrow\\texttt\{life\\\_stage\}means each age value maps to exactly one life stage\.*Domain constraints*restrict attributes to valid ranges conditioned on other attributes \(e\.g\., ifregion=‘North America’\\texttt\{region\}=\\text\{\`North America'\}thencurrency∈\{‘USD’,‘CAD’,‘MXN’\}\\texttt\{currency\}\\in\\\{\\text\{\`USD'\},\\text\{\`CAD'\},\\text\{\`MXN'\}\\\}\)\.*Denial constraints*capture structural prohibitions such as mutual exclusivity in one\-hot encoded features\. Standard Shapley estimators are free to violate all of these, evaluating the model on feature combinations that could never arise in the data\-generating process\.RelShapsystematically prevents this\. A fuller introduction to relational concepts is in Appendix[A](https://arxiv.org/html/2608.11508#A1)\.

## 3TheRelShapFramework

### 3\.1Relational Constraints

RelShapfirst prepares relational constraints for downstream modules, either directly from relational inputs or from flattened\-only inputs through normalization \(Figure[2](https://arxiv.org/html/2608.11508#S3.F2)\)\. We denote a relational schema as𝒮\\mathcal\{S\}, a query as𝒬\\mathcal\{Q\}, and the resulting flattened dataset as𝒟\\mathcal\{D\}\. The schema, query, and resulting data together induce a collection of relational constraints, which we denote byΣ\{𝒮,𝒬,𝒟\}=ΣFD∪Σdom∪Σden\\Sigma^\{\\\{\\mathcal\{S\},\\mathcal\{Q\},\\mathcal\{D\}\\\}\}=\\Sigma\_\{\\mathrm\{FD\}\}\\cup\\Sigma\_\{\\mathrm\{dom\}\}\\cup\\Sigma\_\{\\mathrm\{den\}\}, whereΣFD\\Sigma\_\{\\mathrm\{FD\}\},Σdom\\Sigma\_\{\\mathrm\{dom\}\}, andΣden\\Sigma\_\{\\mathrm\{den\}\}are the sets of FDs, domain constraints, and denial constraints, respectively\. After extracting all relational constraints, users inspect them and specify which types of constraints to include and to what extent; we denote the resulting set byΣ\\Sigma\. Details are in Appendix[D\.1](https://arxiv.org/html/2608.11508#A4.SS1)\.

Relational schema\.ΣS\\Sigma^\{S\}contains schema\-declared integrity constraints: FDs from primary and unique keys, dependencies induced by foreign keys \(applied when the corresponding relations are joined in the query\), and conditional domain constraints \(e\.g\.,CHECKclauses\), ignoring unary type constraints already satisfied by the data\.

Query\.We parse𝒬\\mathcal\{Q\}using SQLGlot\([22](https://arxiv.org/html/2608.11508#bib.bib46)\)to extract query\-induced FDs and conditional domain rules\.ΣFD𝒬\\Sigma^\{\\mathcal\{Q\}\}\_\{\\mathrm\{FD\}\}identifiesGROUP BYclauses, window aggregation, top\-1 selection patterns, and self\-joins\.Σdom𝒬\\Sigma^\{\\mathcal\{Q\}\}\_\{\\mathrm\{dom\}\}capturesWHEREandJOINpredicates\.

Flattened data\.RelShapdiscovers exact minimal FDs with bounded left\-hand\-side size \(default22\) and single\-attribute right\-hand sides; multi\-attribute right\-hand sides can be derived via Armstrong’s axioms\([3](https://arxiv.org/html/2608.11508#bib.bib16)\)\. For anyL⊆FL\\subseteq Fand attributea∉La\\notin L, let𝒟/L\\mathcal\{D\}/Ldenote the partition of𝒟\\mathcal\{D\}induced by equality onLL; an FDL→aL\\rightarrow aholds if, for all equivalence classesC∈𝒟/LC\\in\\mathcal\{D\}/L,\|DISTINCTa​\(C\)\|≤1\|\\mathrm\{DISTINCT\}\_\{a\}\(C\)\|\\leq 1\. For each discovered FDA→BA\\rightarrow Bwith\|dom⁡\(B\)\|≤20\|\\mathrm\{dom\}\(B\)\|\\leq 20\(default\), we derive conditional domain rules\(B=s\)⇒φ⁡\(A\)\(B=s\)\\Rightarrow\\varphi\(A\): for categoricalAA,φ⁡\(A\)\\varphi\(A\)is the set of observed values; for continuousAA, an interval\[ℓs,us\]\[\\ell\_\{s\},u\_\{s\}\]estimated from the data\. We also extract denial constraints by identifying cycles in the FD set \(e\.g\.,A→BA\\rightarrow B,B→CB\\rightarrow C,C→AC\\rightarrow A\) and testing for structural patterns common in ML data, such as scaled one\-hot encodings and exclusive\-or among binary attributes\. By default, we use𝒟\\mathcal\{D\}for constraint discovery and𝒟train\\mathcal\{D\}\_\{\\mathrm\{train\}\}as the reference distribution \(see Appendix[D\.2](https://arxiv.org/html/2608.11508#A4.SS2)\)\.

![Refer to caption](https://arxiv.org/html/2608.11508v1/workflow_revision.png)Figure 2:RelShapworkflow\. The upper panel extracts relational constraints; the core applies relational background \(ΣFD\\Sigma\_\{\\mathrm\{FD\}\}\), provenance\-aware, and integrity constraints modes, which change explanations, and quotient mode, which reduces runtime while leaving Shapley values unchanged\.
### 3\.2Background and Coalition Selection

RelShapincorporates two types of relational constraints:*global*, applied to all test instances, and*local*, instantiated per test instance\.ΣFD\\Sigma\_\{\\mathrm\{FD\}\}is global; provenance\-aware constraints,Σdom\\Sigma\_\{\\mathrm\{dom\}\}, andΣden\\Sigma\_\{\\mathrm\{den\}\}are applied locally\.

###### Definition 1\(Relationally Consistent Background Distribution\)\.

Given a feature setFF, a coalitionS⊆FS\\subseteq F, an instance𝐱\\mathbf\{x\}, and a set of relational constraintsΣ\\Sigma, we define

𝒫bgRel=\{𝒫bgMarginal,if​Σ=∅,P^​\(𝐙F∖S\|𝐱~​\(S,𝐙F∖S\)⊧Σ\)otherwise\.\\mathcal\{P\}\_\{\\mathrm\{bg\}\}^\{\\mathrm\{Rel\}\}=\\begin\{cases\}\\mathcal\{P\}\_\{\\mathrm\{bg\}\}^\{\\mathrm\{Marginal\}\},&\\text\{if \}\\Sigma=\\varnothing,\\\\ \\widehat\{P\}\\bigl\(\\mathbf\{Z\}\_\{F\\setminus S\}\\,\\big\|\\,\\tilde\{\\mathbf\{x\}\}\(S,\\mathbf\{Z\}\_\{F\\setminus S\}\)\\models\\Sigma\\bigr\)&\\text\{otherwise\.\}\\end\{cases\}

Under Def\.[1](https://arxiv.org/html/2608.11508#Thmdefinition1), any coalitionsSSandS′S^\{\\prime\}are*Σ\\Sigma\-equivalent*, i\.e\.,S∼ΣS′S\\sim\_\{\\Sigma\}S^\{\\prime\}, if they induce the same set of relationally valid completions underΣ\\Sigma\. Accordingly,\[S\]Σ\[S\]\_\{\\Sigma\}denotes the*equivalence class*ofSSunder∼Σ\\sim\_\{\\Sigma\}, and the*Σ\\Sigma\-coalition space*𝒞Σ\\mathcal\{C\}\_\{\\Sigma\}is the*quotient*of the original coalition space by∼Σ\\sim\_\{\\Sigma\}, collapsing coalitions indistinguishable underΣ\\Sigma\.

###### Definition 2\(Quotient space coalition projection\)\.

Given𝒞Σ\\mathcal\{C\}\_\{\\Sigma\},*quotient space coalition projection*is a post\-sampling procedure that maps a coalitionS⊆F∖\{i\}S\\subseteq F\\setminus\\\{i\\\}drawn by any sampler to itsΣ\\Sigma\-equivalence class\[S\]Σ\[S\]\_\{\\Sigma\}\(i\.e\., each coalition value is replaced by its canonical representative underΣ\\Sigma\)\.

For example, ifΣ\\Sigmacontains an FDa→ba\\rightarrow bover\{a,b,c\}\\\{a,b,c\\\}, then\{a\}∼Σ\{a,b\}\\\{a\\\}\\sim\_\{\\Sigma\}\\\{a,b\\\}and\{a,c\}∼Σ\{a,b,c\}\\\{a,c\\\}\\sim\_\{\\Sigma\}\\\{a,b,c\\\}, and hence each pair belongs to the sameΣ\\Sigma\-equivalence class\. Under Def\.[2](https://arxiv.org/html/2608.11508#Thmdefinition2), once a coalition is evaluated, subsequent samples mapping to the sameΣ\\Sigma\-equivalence class reuse cached results without additional model calls\. Two properties hold, for distinct reasons\. First, quotient space coalition projection \(quotient mode\) leaves Shapley values unchanged \(Prop\.[1](https://arxiv.org/html/2608.11508#Thmproposition1)\) because it only reuses cached evaluations of equivalent coalitions\. Second, the base estimator’s coalition distribution, weighting scheme, and accuracy guarantees are preserved because all constraints \(FDs, provenance, integrity constraints\) are applied to each sampled coalition*before*quotient deduplication \(Algorithm[1](https://arxiv.org/html/2608.11508#alg1)\)\. Together these provide*orthogonal acceleration*underΣ≠∅\\Sigma\\neq\\varnothing\. See Appendix[H\.1](https://arxiv.org/html/2608.11508#A8.SS1)for details and proof\.

###### Proposition 1\(Shapley value invariance under quotient space coalition projection\)\.

*Quotient space coalition projection does not change the resulting Shapley value of featureii, i\.e\., using only relational background distribution with or without quotient space coalition projection yields identical Shapley values, and this holds for all coalition estimators\.*

Moreover, whenever∼Σ\\sim\_\{\\Sigma\}is non\-trivial, quotient projection strictly reduces the coalition space,\|𝒞Σ\|<2\|F\|−1\|\\mathcal\{C\}\_\{\\Sigma\}\|<2^\{\|F\|\-1\}\(see Appendix[F\.2](https://arxiv.org/html/2608.11508#A6.SS2)\); Section[3\.3](https://arxiv.org/html/2608.11508#S3.SS3)quantifies the expected reduction\.

#### Provenance\-aware mode

*Provenance\-aware*mode incorporates*local*constraints: identifier\-induced FDs \(primary and foreign keys; they are part of globalΣFD\\Sigma\_\{\\mathrm\{FD\}\}but applied instance by instance\) no longer explicit in the flattened table \(e\.g\., when identifiers are dropped as in Example[1](https://arxiv.org/html/2608.11508#Thmexample1)\)\. Given a coalition, we check whether an identifier can be inferred from the observed features\. In strict mode, dependencies are applied only when the identifier is uniquely determined; in relaxed mode, dependencies are applied to any attribute whose value is constant across the narrowed candidate set\. For instance, in Example[1](https://arxiv.org/html/2608.11508#Thmexample1), observing only the age ofa29yields candidates\{a12,a29\}\\\{\\texttt\{a12\},\\texttt\{a29\}\\\}; although the exact identifier is ambiguous,life\_stage\(which may already be determined byage\) andempltake the same value for both and can still be used\. Provenance\-aware mode is applicable even when no other relational structure exists within the feature tables \(e\.g\., discovered FDs\), and when identifiers have been dropped during flattening\. Standard \(non\-provenance\)RelShapis typically sufficient in with\-key settings where identifiers are retained \(e\.g\., recommender systems\)\.

### 3\.3Algorithm and Runtime Analysis

Algorithm 1RelShap1:Input:

𝒫coal\\mathcal\{P\}\_\{\\mathrm\{coal\}\},

Σ\\Sigma,

𝐱\\mathbf\{x\}\(instance\),

MM\(coalition budget\)

2:Output:canonical coalitions

ℳ\\mathcal\{M\}
3:

Seen←∅\\mathrm\{Seen\}\\leftarrow\\emptyset,

ℳ←\[\]\\mathcal\{M\}\\leftarrow\[\\ \]
4:for

t=1t=1to

MMdo

5:sample a raw coalition

m∼𝒫coalm\\sim\\mathcal\{P\}\_\{\\mathrm\{coal\}\}
6:if*relational background mode*under

ΣFD\\Sigma\_\{\\mathrm\{FD\}\}then

7:

m←CanonicalizeCoal​\(m\)m\\leftarrow\\textsc\{CanonicalizeCoal\}\(m\)
8:endif

9:if*provenance\-aware*modethen

10:

m←m∪ProvExpand​\(m,𝐱,ΣFD\)m\\leftarrow m\\cup\\textsc\{ProvExpand\}\(m,\\mathbf\{x\},\\Sigma\_\{\\mathrm\{FD\}\}\)
11:endif

12:if*integrity constraints*modethen

13:

m←m∪ICRepair​\(m,𝐱,Σdom∪Σden\)m\\leftarrow m\\cup\\textsc\{ICRepair\}\(m,\\mathbf\{x\},\\Sigma\_\{\\mathrm\{dom\}\}\\cup\\Sigma\_\{\\mathrm\{den\}\}\)
14:endif

15:if*quotient*mode and

m∈Seenm\\in\\mathrm\{Seen\}then

16:continue⊳\\trianglerightreuse cached evaluation

17:endif

18:

Seen←Seen∪\{m\}\\mathrm\{Seen\}\\leftarrow\\mathrm\{Seen\}\\cup\\\{m\\\};

ℳ←ℳ∪\{m\}\\mathcal\{M\}\\leftarrow\\mathcal\{M\}\\cup\\\{m\\\}
19:endfor

20:return

ℳ\\mathcal\{M\}

Algorithm[1](https://arxiv.org/html/2608.11508#alg1)orchestratesRelShap: it drawsMMraw coalitions from a base coalition distribution, maps each to its canonical representative, expands it with local provenance information when available, applies integrity constraints, and deduplicates coalitions\.CanonicalizeCoalletsΣ\\Sigma\-equivalent coalitions share one evaluation based onFDClosure;ProvExpandincorporates identifier\-induced dependencies using prebuilt inverted and row\-set indexes, requiring only identifier\-level lookups independent of dataset size, rather than full group\-by operations; andICRepairextends the coalition with features whose values are forced by domain and denial constraints \(all subroutines are in Appendix[G](https://arxiv.org/html/2608.11508#A7)\)\.RelShapfirst samples coalitions from the base coalition distribution and then applies all available relational constraints, reusing cached evaluations when possible and evaluating new coalitions otherwise\. This procedure preserves the base sampler’s draws while enforcing relational consistency and avoiding redundant evaluations \(\|ℳ\|≤M\|\\mathcal\{M\}\|\\leq M\)\.

##### Runtime analysis\.

The runtime reduction from*quotient space coalition projection*is the decrease from the sampling budgetMMto the number of distinct projected coalitions\|ℳ\|\|\\mathcal\{M\}\|\. Prior works\([13](https://arxiv.org/html/2608.11508#bib.bib48);[14](https://arxiv.org/html/2608.11508#bib.bib28)\)characterize\|𝒞Σ\|\|\\mathcal\{C\}\_\{\\Sigma\}\|for representative FD structures \(Appendix[H\.2](https://arxiv.org/html/2608.11508#A8.SS2)\), but only under deterministic coalition evaluation\.RelShapalso supports*stochastic*sampling from𝒫coal\\mathcal\{P\}\_\{\\mathrm\{coal\}\}, where widely used estimators sample with coalition size\-dependent probabilitiespk=Pr⁡\(\|S\|=k\)p\_\{k\}=\\Pr\(\|S\|=k\)\(Section[2\.2](https://arxiv.org/html/2608.11508#S2.SS2)\)\. We therefore decompose the probability of reaching each class by coalition size and derive the expected reduction combinatorially: speedup arises when the sampler repeatedly hits the same equivalence class, allowing evaluations to be reused\.

###### Theorem 1\(Expected reduction under quotient mode\)\.

Letq⁡\(C\)=PrS∼𝒫coal⁡\(\[S\]Σ=C\)q\(C\)=\\Pr\_\{S\\sim\\mathcal\{P\}\_\{\\mathrm\{coal\}\}\}\(\[S\]\_\{\\Sigma\}=C\)be the probability that a sampled coalition maps toΣ\\Sigma\-equivalence classC∈𝒞ΣC\\in\\mathcal\{C\}\_\{\\Sigma\}\. If the draws are i\.i\.d\., the expected number of distinct classes evaluated after projection mode is

𝔼⁡\[KM\]=∑C∈𝒞Σ\(1−\(1−q⁡\(C\)\)M\),\\mathbb\{E\}\[K\_\{M\}\]=\\sum\_\{C\\in\\mathcal\{C\}\_\{\\Sigma\}\}\\left\(1\-\(1\-q\(C\)\)^\{M\}\\right\),whereq⁡\(C\)=∑k=r⁡\(C\)\|F\|−1pk​NC​\(k\)\(\|F\|−1k\)q\(C\)=\\sum\_\{k=r\(C\)\}^\{\|F\|\-1\}p\_\{k\}\\frac\{N\_\{C\}\(k\)\}\{\\binom\{\|F\|\-1\}\{k\}\}is the probability of a sampled coalition landing in classCC\. Hence the normalized expected runtime speedup factor relative to the baseline sampler isRM=1−𝔼⁡\[KM\]/M\.R\_\{M\}=1\-\\mathbb\{E\}\[K\_\{M\}\]/\{M\}\.

NC​\(k\)N\_\{C\}\(k\)is the number of size\-kkcoalitions whose projection belongs toCC, andr⁡\(C\)=min⁡\{\|S\|∣\[S\]Σ=C\}r\(C\)=\\min\\\{\|S\|\\mid\[S\]\_\{\\Sigma\}=C\\\}is the minimum size of any coalition generatingCC\(rank\)\. For the FDa→ba\\rightarrow bover\{a,b,c\}\\\{a,b,c\\\}from Section[3\.2](https://arxiv.org/html/2608.11508#S3.SS2), quotient mode reduces\|𝒞Σ\|\|\\mathcal\{C\}\_\{\\Sigma\}\|from23=82^\{3\}=8to66\. Intuitively, FDs with small left\-hand sides \(LHSs\) induce classes with smallr⁡\(C\)r\(C\), so many coalitions collapse to the same class, yielding largeNC​\(k\)N\_\{C\}\(k\)at small sizes\. The improvement for*Kernel SHAP*is therefore amplified whenΣ\\Sigmacontains many low\-arity dependencies, since it concentrates mass on extreme coalition sizes and FDs with small LHSs are common in practice;*Monte Carlo*and*Leverage SHAP*spread mass more evenly acrosskk, so their improvement tracks the overall magnitude ofNC​\(k\)N\_\{C\}\(k\)\. We ignore implementation\-level costs \(e\.g\., lookup or indexing\) and assume i\.i\.d\. draws; sequential samplers may introduce mild dependence in practice\. Appendix[H\.3](https://arxiv.org/html/2608.11508#A8.SS3)provides a proof and Section[4](https://arxiv.org/html/2608.11508#S4)confirms that observed speedups closely match this analysis\.

## 4Experimental Evaluation

We evaluateRelShapon 9 datasets: 5 standard ML datasets normalized into relational form\([45](https://arxiv.org/html/2608.11508#bib.bib56)\)— Amazon Employee Access\([43](https://arxiv.org/html/2608.11508#bib.bib37)\), Churn\([42](https://arxiv.org/html/2608.11508#bib.bib38)\), Churn Modelling\([30](https://arxiv.org/html/2608.11508#bib.bib44)\), German Credit\([40](https://arxiv.org/html/2608.11508#bib.bib40)\), and SpeedDating\([41](https://arxiv.org/html/2608.11508#bib.bib39)\)— and 4 relational datasets: TPC\-H\([51](https://arxiv.org/html/2608.11508#bib.bib41)\), UW\-CSE\([37](https://arxiv.org/html/2608.11508#bib.bib43);[10](https://arxiv.org/html/2608.11508#bib.bib42)\), MovieLens 20M\([29](https://arxiv.org/html/2608.11508#bib.bib45)\), and a Synthetic dataset extending Example[1](https://arxiv.org/html/2608.11508#Thmexample1)with domain and denial constraints\.

We train logistic regression, XGBoost\([7](https://arxiv.org/html/2608.11508#bib.bib49)\), Random Forest\([32](https://arxiv.org/html/2608.11508#bib.bib50)\), and MLP\-PLR\([23](https://arxiv.org/html/2608.11508#bib.bib51)\), covering linear, tree\-based, and neural models, and compute explanations with Kernel SHAP, MC, and Leverage SHAP \(means and standard deviations over three seeds\) fornexplain=min⁡\(200,\|𝒟test\|\)n\_\{\\text\{explain\}\}=\\min\(200,\|\\mathcal\{D\}\_\{\\text\{test\}\}\|\)instances per dataset, using a per\-dataset convergence budgetMconvM\_\{\\mathrm\{conv\}\}at which Shapley estimates stabilize\([9](https://arxiv.org/html/2608.11508#bib.bib52);[56](https://arxiv.org/html/2608.11508#bib.bib55)\)\.

Relational constraint extraction is a one\-time preprocessing step reused across all explanations; it completes within 12 seconds on every dataset except SpeedDating \(482\.7482\.7s\) and MovieLens 20M \(98\.998\.9s\), where data\-driven FD discovery dominates, and its cost, typically offset by the resulting speedups, is excluded from runtime comparisons\. Setup details are in Appendices[I](https://arxiv.org/html/2608.11508#A9)and[J\.1](https://arxiv.org/html/2608.11508#A10.SS1)\.

##### In summary,

our experiments show that standard estimators query impossible worlds constantly; when ground truth is known,RelShapis the only method that recovers the correct explanation; on real data, the correction is large and systematic; and it comes at reduced, not increased, runtime\.

### 4\.1Validation with Ground Truth

We demonstrate thatRelShapyields more intuitive explanations than existing methods in a controlled setting, following experiments in[50](https://arxiv.org/html/2608.11508#bib.bib11)\. Building on Example[1](https://arxiv.org/html/2608.11508#Thmexample1), we consider a loan approval scenario restricted to two features \(ageandlife\_stage\), with an FDage→life\_stage\\texttt\{age\}\\rightarrow\\texttt\{life\\\_stage\}\. We define a synthetic predictorg\(𝐱\)=𝟏\{age\>50\}\+δr\(life\_stage\)1\{𝐱⊧̸Σ\},g\(\\mathbf\{x\}\)=\\mathbf\{1\}\\\{\\texttt\{age\}\>50\\\}\+\\delta\\,r\(\\texttt\{life\\\_stage\}\)\\,\\mathbf\{1\}\\\{\\mathbf\{x\}\\not\\models\\Sigma\\\},wherer⁡\(life\_stage\)∈\{0\.3,0\.6,0\.9\}r\(\\texttt\{life\\\_stage\}\)\\in\\\{0\.3,0\.6,0\.9\\\}assigns an arbitrary constant to each of the three life stages, andδ\\deltaranges from00to1010in increments of0\.50\.5\. Since every data instance satisfiesΣ\\Sigma, the second perturbation term is inactive during training and testing and is triggered only by relationally invalid combinations generated during Shapley computation\. Thus, predictions on the valid domain depend*only*onage, and a semantically intuitive explanation should assign greater importance toagethan tolife\_stageregardless ofδ\\delta\.

Figure[3](https://arxiv.org/html/2608.11508#S4.F3)shows how often each feature receives the larger absolute attribution asδ\\deltaincreases\. All three baselines rankagefirst more often thanlife\_stage; however, Kernel SHAP increasingly shifts attribution towardlife\_stageas invalid perturbations grow\. Conditional SHAP and ManifoldShap are less sensitive to increasingδ\\delta, but still ranklife\_stagefirst for a substantial fraction of instances\. In contrast,RelShapconsistently assigns the larger attribution toagefor allδ\\delta\. This indicates that the explanation change fromRelShapis not a mere difference; it is an*improvement*with respect to relational validity, achieved by eliminating*impossible worlds*\.

The mechanism behind these differences is instructive\. We measure*violation prevalence*: the fraction of coalitions violating at least one relational constraint\. Kernel SHAP fillslife\_stagefrom the marginal distribution, independently ofage, so31\.8%31\.8\\%of its coalitions violate the FD \(e\.g\.,age=35\\texttt\{age\}=35withlife\_stage=older\\texttt\{life\\\_stage\}=\\texttt\{older\}\); each violation activates the perturbation termδ​r​\(life\_stage\)\\delta\\,r\(\\texttt\{life\\\_stage\}\), and the resulting spurious attribution tolife\_stagegrows withδ\\delta\. Conditional SHAP, which estimates the conditional distribution oflife\_stagegivenage, and ManifoldShap, which restricts completions to an estimated data manifold, suppress most, but not all, violations \(4\.8%4\.8\\%and5\.1%5\.1\\%, respectively\), explaining their partial yet incomplete robustness\.RelShapenforces the FD exactly: its violation prevalence is0%0\\%, the perturbation term never activates, andlife\_stagereceives no spurious attribution\. Note that violation prevalence itself does not depend onδ\\delta: increasingδ\\deltamakes each violation more costly, not more frequent, which is why misattribution grows withδ\\deltawhile prevalence stays fixed\.

Figure 3:Comparison of top attribution frequency across methods asδ\\deltavaries; exact Shapley values computed via full coalition enumeration\.\(a\)Aggregated by estimators\.\(b\)Aggregated by comparison modes\.\(c\)Aggregated by datasets\.
Figure 4:Percentage of cases withΔ\>0\\Delta\>0, sliced by estimators, comparison modes, and datasets\. Error bars denote 95% CIs\.These results generalize beyond two features\. We repeat the experiment over four features \(age,life\_stage,empl,total\_amt\), where attribution ordering between a particular feature pair is no longer expected to hold in isolation, and examine how the overall attribution vector and feature ranking change asδ\\deltaincreases \(Appendix[J\.3](https://arxiv.org/html/2608.11508#A10.SS3)\)\.RelShapremains unchanged across all metrics, while all baselines exhibit increasing attribution and ranking shifts; a setting with additional provenance constraints behaves identically \(Appendix[J\.3](https://arxiv.org/html/2608.11508#A10.SS3)\)\. This shows that eliminating impossible worlds makesRelShapinsensitive to relationally invalid perturbations that are never observed during training or testing\.

Beyond the controlled setting, the UW\-CSE dataset permits full background and coalition enumeration\.RelShapchanges the feature ranking even under exact computation, showing that the change is not a sampling artifact\. Quotient mode further reduces runtime while preserving the Shapley values exactly, providing an empirical verification of Prop\.[1](https://arxiv.org/html/2608.11508#Thmproposition1)\. Additional validations on real datasets are in Appendix[J\.3](https://arxiv.org/html/2608.11508#A10.SS3)\.

### 4\.2Impossible Worlds in Practice

We compare default estimators against fiveRelShapconfigurations with progressively richer constraints: BG \(relational background mode\); BG \+ DCs; BG \+ Prov, Strict/Relaxed \(Relaxed subsumes Strict\); and All \(BG \+ Prov, Relaxed \+ DCs\)\. We first quantify how frequently conventional Shapley computation is exposed to*impossible worlds*\. Across the three estimators, average violation prevalence rises from6464–74%74\\%under BG to8282–93%93\\%under BG \+ Prov, Relaxed on datasets without DCs, and from6868–70%70\\%under BG to7272–76%76\\%under All \(Appendix[J\.4](https://arxiv.org/html/2608.11508#A10.SS4)\): invalidity becomes more pervasive as richer constraints are incorporated\.

ModeTop\-3 Jaccard1−RBO1\-\\mathrm\{RBO\}ΔJaccard\\Delta\_\{\\mathrm\{Jaccard\}\}ΔRBO\\Delta\_\{\\mathrm\{RBO\}\}BG0\.4520\.1900\.0570\.050BG \+ DCs0\.5660\.2160\.1680\.094BG \+ Prov, Strict0\.3770\.142−0\.023\-0\.0230\.011BG \+ Prov, Relaxed0\.4150\.1550\.0150\.024All0\.4300\.1720\.0360\.032Table 2:Explanation differences by comparison mode \(Default vs\. mode\), averaged over datasets, models, and estimators; standard deviations in Appendix Table[9](https://arxiv.org/html/2608.11508#A10.T9)\.Prevalence alone does not establish that explanations change; that also depends on the model’s response in the invalid region\. We therefore assess howRelShapchanges Shapley values relative to default estimators, finding shifts well beyond random ranking perturbation\. For each instance, we measure ranking differences using*Top\-33Jaccard distance*and*1−RBO1\-\\mathrm\{RBO\}*\(rank\-biased overlap\)\([53](https://arxiv.org/html/2608.11508#bib.bib54)\), capturing the three most influential features and the full top\-weighted ranking, respectively\. Against the Mallows null baseline range of[27](https://arxiv.org/html/2608.11508#bib.bib53), we defineΔ\\Deltaas the signed deviation from the range midpoint;Δ\>0\\Delta\>0indicates a change larger than expected at random, and we report95%95\\%confidence intervals \(CIs\) on the fraction of such cases\.

Figure[4](https://arxiv.org/html/2608.11508#S4.F4)shows the percentage of cases withΔ\>0\\Delta\>0\. This percentage exceeds50%50\\%across mostRelShapconfigurations, with changes occurring most frequently under MC, followed by Leverage SHAP and Kernel SHAP\. Dataset\-level effects are generally larger for constraint\-rich datasets—reaching nearly100%100\\%for SpeedDating—but are not strictly monotonic in the number of constraints \(Appendix[J](https://arxiv.org/html/2608.11508#A10)\)\. The effects are stable across predictive models, confirming thatRelShapis generally model\-agnostic \(Appendix[J\.2](https://arxiv.org/html/2608.11508#A10.SS2.SSSx1)\)\. Together with Section[4\.1](https://arxiv.org/html/2608.11508#S4.SS1), these results indicate that the observed ranking differences reflect meaningful corrections toward relationally valid explanations\.

Table[2](https://arxiv.org/html/2608.11508#S4.T2)reports the magnitude of these changes by configuration: domain and denial constraints yield the largest corrections, provenance effects depend on the mode, andΔ\>0\\Delta\>0on average in all but one mode–metric pair\. On TPC\-H, provenance mode replaces the top\-3 features almost entirely \(Top\-3 Jaccard0\.910\.91–0\.960\.96under Kernel SHAP and MC; Appendix Table[11](https://arxiv.org/html/2608.11508#A10.T11)\)\.

### 4\.3Effectiveness of Running Time Optimization

Quotient mode \(Q\) applies the quotient space coalition projection of Def\.[2](https://arxiv.org/html/2608.11508#Thmdefinition2)as an orthogonal acceleration on top of any configuration \(Appendix[J\.2](https://arxiv.org/html/2608.11508#A10.SS2.SSSx2.Px1)\)\. Across datasets and models, this optimization consistently reduces runtime for MC and Leverage SHAP, particularly on computationally costly datasets \(e\.g\., Amazon, TPC\-H\); Kernel SHAP also benefits from Q but is more variable, consistent with the estimator\-dependent analysis in Section[3\.3](https://arxiv.org/html/2608.11508#S3.SS3)\. Added relational processing does not typically impose a runtime penalty, and the reduction from Q grows with both background size and coalition budget\. Finally, observed reductions align with our combinatorial analysis: the empirical counterpart ofRMR\_\{M\}in Thm\.[1](https://arxiv.org/html/2608.11508#Thmtheorem1)correlates closely with measured reduction \(Pearson: mean0\.8060\.806, median0\.8750\.875; Kendallτ\\tau: mean0\.7410\.741, median0\.8330\.833\), reliably predicting*when*reduction occurs, though its magnitude depends on the dataset and sampling strategy\.

## 5Conclusion

Conventional Shapley value methods treat feature coalitions as unrestricted subsets, in effect querying relationally impossible worlds\.RelShapis the first estimator\-agnostic framework to systematically enforce relational consistency\. Extensive experiments show that the resulting explanations differ meaningfully from those of unconstrained estimators, and that in settings with known ground truth, the difference is an improvement\. Quotient mode preserves Shapley values exactly while provably reducing runtime\.

Limitations\.Our validation establishes improvement with respect to relational validity and synthetic ground truth, not human judgment; a user study is important future work\.RelShapalso treats the extracted, user\-vetted constraints as correct: spurious FDs discovered from small data would propagate to explanations\. See Appendix[L](https://arxiv.org/html/2608.11508#A12)for details\.

## Acknowledgments

This work was supported by NSF Awards No\. 2312930 and 2326193\. This work was supported in part through the NYU IT High Performance Computing resources, services, and staff expertise\.

## References

- Aaset al\.\(2021\)K\. Aaset al\.Explaining individual predictions when features are dependent: more accurate approximations to shapley values\.Artificial Intelligence298,pp\. 103502\.Cited by:[§B\.1](https://arxiv.org/html/2608.11508#A2.SS1.p3.1.1),[§D\.2](https://arxiv.org/html/2608.11508#A4.SS2.p3.1),[§1](https://arxiv.org/html/2608.11508#S1.p2.1),[§2\.1](https://arxiv.org/html/2608.11508#S2.SS1.p2.1)\.
- Alizad and Milani \(2025\)A\. Alizad and M\. MilaniRelation\-stratified sampling for shapley values estimation in relational databases\.arXiv preprint arXiv:2511\.22035\.Cited by:[Table 20](https://arxiv.org/html/2608.11508#A11.T20.3.5.1.1.1),[Appendix K](https://arxiv.org/html/2608.11508#A11.p1.1),[Appendix K](https://arxiv.org/html/2608.11508#A11.p3.1)\.
- Armstrong \(1974\)W\. W\. ArmstrongDependency structures of data base relationships\.InIFIP congress,Vol\.74,pp\. 580–583\.Cited by:[§D\.1](https://arxiv.org/html/2608.11508#A4.SS1.SSSx1.p2.1),[§3\.1](https://arxiv.org/html/2608.11508#S3.SS1.p4.1),[Remark 1](https://arxiv.org/html/2608.11508#Thmremark1.p1.1.1)\.
- Bertossiet al\.\(2023\)L\. Bertossi, B\. Kimelfeld, E\. Livshits, and M\. MonetThe shapley value in database management\.ACM Sigmod Record52\(2\),pp\. 6–17\.Cited by:[Table 20](https://arxiv.org/html/2608.11508#A11.T20.3.6.1.1.1),[Appendix K](https://arxiv.org/html/2608.11508#A11.p1.1),[Appendix K](https://arxiv.org/html/2608.11508#A11.p3.1)\.
- Bischlet al\.\(2021\)B\. Bischl, G\. Casalicchio, M\. Feurer, P\. Gijsbers, F\. Hutter, M\. Lang, R\. G\. Mantovani, J\. N\. van Rijn, and J\. VanschorenOpenML benchmarking suites\.Proceedings of the NeurIPS 2021 Datasets and Benchmarks Track\.Cited by:[Appendix I](https://arxiv.org/html/2608.11508#A9.p1.1)\.
- Chenet al\.\(2020\)H\. Chen, J\. D\. Janizek, S\. Lundberg, and S\. LeeTrue to the model or true to the data?\.arXiv preprint arXiv:2006\.16234\.Cited by:[§1](https://arxiv.org/html/2608.11508#S1.p2.1),[§2](https://arxiv.org/html/2608.11508#S2.p2.1)\.
- Chenet al\.\(2016\)T\. Chenet al\.Xgboost: a scalable tree boosting system\.InProceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining,pp\. 785–794\.Cited by:[§4](https://arxiv.org/html/2608.11508#S4.p2.1)\.
- Cheneyet al\.\(2009\)J\. Cheneyet al\.Provenance in databases: why, how, and where\.Foundations and Trends in Databases1\(4\),pp\. 379–474\.Cited by:[§A\.5](https://arxiv.org/html/2608.11508#A1.SS5.p3.1)\.
- Covertet al\.\(2020\)I\. Covertet al\.Improving kernelshap: practical shapley value estimation via linear regression\.arXiv preprint arXiv:2012\.01536\.Cited by:[§J\.1](https://arxiv.org/html/2608.11508#A10.SS1.p2.1),[§4](https://arxiv.org/html/2608.11508#S4.p2.1)\.
- CTU \(2003\)CTUUW\-cse\.Note:https://relational\.fel\.cvut\.cz/dataset/UW\-CSELast accessed: April 2026Cited by:[§4](https://arxiv.org/html/2608.11508#S4.p1.1)\.
- Dattaet al\.\(2016\)A\. Dattaet al\.Algorithmic transparency via quantitative input influence: theory and experiments with learning systems\.InIEEE Symposium on Security and Privacy, SP 2016, San Jose, CA, USA, May 22\-26, 2016,pp\. 598–617\.External Links:[Link](https://doi.org/10.1109/SP.2016.42),[Document](https://dx.doi.org/10.1109/SP.2016.42)Cited by:[§1](https://arxiv.org/html/2608.11508#S1.p1.1)\.
- Davidsonet al\.\(2022\)S\. Davidson, D\. Deutch, N\. Frost, B\. Kimelfeld, O\. Koren, and M\. MonetShapgraph: an holistic view of explanations through provenance graphs and shapley values\.InProceedings of the 2022 International Conference on Management of Data,pp\. 2373–2376\.Cited by:[Table 20](https://arxiv.org/html/2608.11508#A11.T20.3.4.1.1.1),[Appendix K](https://arxiv.org/html/2608.11508#A11.p1.1),[Appendix K](https://arxiv.org/html/2608.11508#A11.p3.1)\.
- Demetrovicset al\.\(1985\)J\. Demetrovicset al\.Minimum matrix representation of closure operations\.Discrete Applied Mathematics11\(2\),pp\. 115–128\.Cited by:[§H\.2](https://arxiv.org/html/2608.11508#A8.SS2.p1.1),[§3\.3](https://arxiv.org/html/2608.11508#S3.SS3.SSS0.Px1.p1.1)\.
- Demetrovicset al\.\(1992\)J\. Demetrovicset al\.Functional dependencies in relational databases: a lattice point of view\.Discrete Applied Mathematics40\(2\),pp\. 155–185\.Cited by:[§H\.2](https://arxiv.org/html/2608.11508#A8.SS2.p1.1),[§3\.3](https://arxiv.org/html/2608.11508#S3.SS3.SSS0.Px1.p1.1),[Lemma 1](https://arxiv.org/html/2608.11508#Thmlemma1),[Proposition 2](https://arxiv.org/html/2608.11508#Thmproposition2)\.
- Deutchet al\.\(2022\)D\. Deutch, N\. Frost, B\. Kimelfeld, and M\. MonetComputing the shapley value of facts in query answering\.InProceedings of the 2022 International Conference on Management of Data,pp\. 1570–1583\.Cited by:[Table 20](https://arxiv.org/html/2608.11508#A11.T20.3.3.1.1.1),[Appendix K](https://arxiv.org/html/2608.11508#A11.p1.1),[Appendix K](https://arxiv.org/html/2608.11508#A11.p3.1)\.
- Dwivediet al\.\(2025\)V\. P\. Dwivedi, C\. Kanatsoulis, S\. Huang, and J\. LeskovecRelational deep learning: challenges, foundations and next\-generation architectures\.InProceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V\. 2,pp\. 5999–6009\.Cited by:[§1](https://arxiv.org/html/2608.11508#S1.p1.1)\.
- Feyet al\.\(2024\)M\. Fey, W\. Hu, K\. Huang, J\. E\. Lenssen, R\. Ranjan, J\. Robinson, R\. Ying, J\. You, and J\. LeskovecPosition: relational deep learning \- graph representation learning on relational databases\.InProceedings of the 41st International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.235,pp\. 13592–13607\.Cited by:[§1](https://arxiv.org/html/2608.11508#S1.p1.1)\.
- Flajoletet al\.\(1992\)P\. Flajoletet al\.Birthday paradox, coupon collectors, caching algorithms and self\-organizing search\.Discrete Applied Mathematics39\(3\),pp\. 207–229\.Cited by:[§H\.3](https://arxiv.org/html/2608.11508#A8.SS3.p3.1)\.
- Fryeet al\.\(2021\)C\. Frye, D\. de Mijolla, T\. Begley, L\. Cowton, M\. Stanley, and I\. FeigeShapley explainability on the data manifold\.InInternational Conference on Learning Representations,Cited by:[§B\.2](https://arxiv.org/html/2608.11508#A2.SS2.p2.1),[§1](https://arxiv.org/html/2608.11508#S1.p2.1),[§2\.1](https://arxiv.org/html/2608.11508#S2.SS1.p3.1)\.
- Fumagalliet al\.\(2026\)F\. Fumagalli, L\. Butler, J\. S\. Kang, K\. Ramchandran, and R\. T\. WitterAn odd estimator for shapley values\.arXiv preprint arXiv:2602\.01399\.Cited by:[§C\.4](https://arxiv.org/html/2608.11508#A3.SS4.p1.1),[§2\.2](https://arxiv.org/html/2608.11508#S2.SS2.p1.2)\.
- Fumagalliet al\.\(2026\)F\. Fumagalliet al\.PolySHAP: extending kernelshap with interaction\-informed polynomial regression\.arXiv preprint arXiv:2601\.18608\.Cited by:[§C\.4](https://arxiv.org/html/2608.11508#A3.SS4.p1.1)\.
- GitHub \(2023\)GitHubSQLGlot\.Note:https://github\.com/tobymao/sqlglotLast accessed: April 2026Cited by:[§3\.1](https://arxiv.org/html/2608.11508#S3.SS1.p3.1)\.
- Gorishniyet al\.\(2022\)Y\. Gorishniyet al\.On embeddings for numerical features in tabular deep learning\.Advances in Neural Information Processing Systems35,pp\. 24991–25004\.Cited by:[§4](https://arxiv.org/html/2608.11508#S4.p2.1)\.
- Greenet al\.\(2007\)T\. J\. Greenet al\.Provenance semirings\.InProceedings of the Twenty\-Sixth ACM SIGMOD\-SIGACT\-SIGART Symposium on Principles of Database Systems,PODS ’07,New York, NY, USA,pp\. 31–40\.External Links:ISBN 9781595936851,[Link](https://doi.org/10.1145/1265530.1265535),[Document](https://dx.doi.org/10.1145/1265530.1265535)Cited by:[§A\.5](https://arxiv.org/html/2608.11508#A1.SS5.p3.1)\.
- Heskeset al\.\(2020\)T\. Heskeset al\.Causal shapley values: exploiting causal knowledge to explain individual predictions of complex models\.Advances in neural information processing systems33,pp\. 4778–4789\.Cited by:[§B\.1](https://arxiv.org/html/2608.11508#A2.SS1.p4.1.1),[§B\.3](https://arxiv.org/html/2608.11508#A2.SS3.p3.1),[§B\.3](https://arxiv.org/html/2608.11508#A2.SS3.p4.1),[§B\.3](https://arxiv.org/html/2608.11508#A2.SS3.p5.2),[§2\.1](https://arxiv.org/html/2608.11508#S2.SS1.p2.1)\.
- Huhtalaet al\.\(1999\)Y\. Huhtala, J\. Kärkkäinen, P\. Porkka, and H\. ToivonenTANE: an efficient algorithm for discovering functional and approximate dependencies\.The Computer Journal42\(2\),pp\. 100–111\.Cited by:[§A\.2](https://arxiv.org/html/2608.11508#A1.SS2.p2.1)\.
- Hwanget al\.\(2026\)H\. Hwang, S\. Lee, L\. Rosenblatt, S\. E\. Whang, and J\. StoyanovichExplanation multiplicity in shap: characterization and assessment\.arXiv preprint arXiv:2601\.12654\.Cited by:[§4\.2](https://arxiv.org/html/2608.11508#S4.SS2.p2.1)\.
- Janzinget al\.\(2020\)D\. Janzinget al\.Feature relevance quantification in explainable ai: a causal problem\.InInternational Conference on artificial intelligence and statistics,pp\. 2907–2916\.Cited by:[§B\.1](https://arxiv.org/html/2608.11508#A2.SS1.p2.1.1),[§B\.2](https://arxiv.org/html/2608.11508#A2.SS2.p2.1),[§1](https://arxiv.org/html/2608.11508#S1.p2.1),[§2\.1](https://arxiv.org/html/2608.11508#S2.SS1.p2.1),[§2\.1](https://arxiv.org/html/2608.11508#S2.SS1.p3.1)\.
- Kaggle \(2016\)KaggleMovieLens 20m dataset\.Note:https://www\.kaggle\.com/datasets/grouplens/movielens\-20m\-datasetLast accessed: April 2026Cited by:[§4](https://arxiv.org/html/2608.11508#S4.p1.1)\.
- Kaggle \(2020\)KaggleChurn modelling\.Note:https://www\.kaggle\.com/datasets/shubh0799/churn\-modelling/dataLast accessed: April 2026Cited by:[§4](https://arxiv.org/html/2608.11508#S4.p1.1)\.
- Labergeet al\.\(2022\)G\. Laberge, U\. Aïvodji, S\. Hara, F\. Khomh,et al\.Fool shap with stealthily biased sampling\.arXiv preprint arXiv:2205\.15419\.Cited by:[§D\.2](https://arxiv.org/html/2608.11508#A4.SS2.p2.1)\.
- Liawet al\.\(2002\)A\. Liawet al\.Classification and regression by randomforest\.R news2\(3\),pp\. 18–22\.Cited by:[§4](https://arxiv.org/html/2608.11508#S4.p2.1)\.
- Livshitset al\.\(2021\)E\. Livshits, L\. Bertossi, B\. Kimelfeld, and M\. SebagThe shapley value of tuples in query answering\.Logical Methods in Computer Science17\.Cited by:[Table 20](https://arxiv.org/html/2608.11508#A11.T20.3.2.1.1.1),[Appendix K](https://arxiv.org/html/2608.11508#A11.p1.1),[Appendix K](https://arxiv.org/html/2608.11508#A11.p2.1)\.
- Lundberg and Lee \(2017\)S\. M\. Lundberg and S\. LeeA unified approach to interpreting model predictions\.InAdvances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4\-9, 2017, Long Beach, CA, USA,I\. Guyon, U\. von Luxburg, S\. Bengio, H\. M\. Wallach, R\. Fergus, S\. V\. N\. Vishwanathan, and R\. Garnett \(Eds\.\),pp\. 4765–4774\.External Links:[Link](https://proceedings.neurips.cc/paper/2017/hash/8a20a8621978632d76c43dfd28b67767-Abstract.html)Cited by:[§B\.1](https://arxiv.org/html/2608.11508#A2.SS1.p2.1),[§B\.2](https://arxiv.org/html/2608.11508#A2.SS2.p2.1),[§C\.1](https://arxiv.org/html/2608.11508#A3.SS1.p1.1.1),[§D\.1](https://arxiv.org/html/2608.11508#A4.SS1.SSSx3.p3.1),[§D\.2](https://arxiv.org/html/2608.11508#A4.SS2.p3.1),[§1](https://arxiv.org/html/2608.11508#S1.SS0.SSS0.Px1.p2.1),[§1](https://arxiv.org/html/2608.11508#S1.p1.1),[§1](https://arxiv.org/html/2608.11508#S1.p2.1),[§2\.1](https://arxiv.org/html/2608.11508#S2.SS1.p2.1),[§2\.2](https://arxiv.org/html/2608.11508#S2.SS2.p1.2)\.
- Maafaet al\.\(2018\)K\. Maafaet al\.Algorithms for computing the shapley value of cooperative games on lattices\.Discrete Applied Mathematics249,pp\. 91–105\.Cited by:[§2\.2](https://arxiv.org/html/2608.11508#S2.SS2.p2.1),[Remark 1](https://arxiv.org/html/2608.11508#Thmremark1.p3.1.1)\.
- McElfreshet al\.\(2023\)D\. McElfresh, S\. Khandagale, J\. Valverde, V\. Prasad C, G\. Ramakrishnan, M\. Goldblum, and C\. WhiteWhen do neural nets outperform boosted trees on tabular data?\.Advances in Neural Information Processing Systems36,pp\. 76336–76369\.Cited by:[Appendix I](https://arxiv.org/html/2608.11508#A9.p1.1)\.
- Motlet al\.\(2015\)J\. Motlet al\.The ctu prague relational learning repository\.arXiv preprint arXiv:1511\.03086\.Cited by:[§4](https://arxiv.org/html/2608.11508#S4.p1.1)\.
- Motwaniet al\.\(1995\)R\. Motwaniet al\.Randomized algorithms\.Cambridge University Press\.Cited by:[§H\.3](https://arxiv.org/html/2608.11508#A8.SS3.p3.1)\.
- Musco and Witter \(2025\)C\. Musco and R\. T\. WitterProvably accurate shapley value estimation via leverage score sampling\.InThe Thirteenth International Conference on Learning Representations,Cited by:[§C\.3](https://arxiv.org/html/2608.11508#A3.SS3.p1.1.1),[§2\.2](https://arxiv.org/html/2608.11508#S2.SS2.p1.2)\.
- OpenML \(2014\)OpenMLCredit\-g\.Note:https://www\.openml\.org/d/31Last accessed: April 2026Cited by:[§4](https://arxiv.org/html/2608.11508#S4.p1.1)\.
- OpenML \(2016\)OpenMLSpeedDating\.Note:https://www\.openml\.org/d/40536Last accessed: April 2026Cited by:[§4](https://arxiv.org/html/2608.11508#S4.p1.1)\.
- OpenML \(2017\)OpenMLChurn\.Note:https://www\.openml\.org/d/40701Last accessed: April 2026Cited by:[§4](https://arxiv.org/html/2608.11508#S4.p1.1)\.
- OpenML \(2022\)OpenMLAmazon employee access\.Note:https://www\.openml\.org/d/43900Last accessed: April 2026Cited by:[§4](https://arxiv.org/html/2608.11508#S4.p1.1)\.
- Papenbrocket al\.\(2015\)T\. Papenbrocket al\.Functional dependency discovery: an experimental evaluation of seven algorithms\.PVLDB8\(10\),pp\. 1082–1093\.Cited by:[§A\.2](https://arxiv.org/html/2608.11508#A1.SS2.p2.1)\.
- Papenbrocket al\.\(2017\)T\. Papenbrocket al\.Data\-driven schema normalization\.\.InEDBT,Vol\.17,pp\. 342–353\.Cited by:[§4](https://arxiv.org/html/2608.11508#S4.p1.1)\.
- Robinsonet al\.\(2024\)J\. Robinsonet al\.Relbench: a benchmark for deep learning on relational databases\.NeurIPS37,pp\. 21330–21341\.Cited by:[§1](https://arxiv.org/html/2608.11508#S1.p1.1)\.
- Rubachevet al\.\(2025\)I\. Rubachev, N\. Kartashev, Y\. Gorishniy, and A\. BabenkoTabred: analyzing pitfalls and filling the gaps in tabular deep learning benchmarks\.International Conference on Learning Representations\.Cited by:[Appendix I](https://arxiv.org/html/2608.11508#A9.p1.1)\.
- Shapleyet al\.\(1953\)L\. S\. Shapleyet al\.A value for n\-person games\.Princeton University Press Princeton\.Cited by:[§1](https://arxiv.org/html/2608.11508#S1.p1.1)\.
- Sundararajanet al\.\(2020\)M\. Sundararajanet al\.The many shapley values for model explanation\.InInternational conference on machine learning,pp\. 9269–9278\.Cited by:[§B\.2](https://arxiv.org/html/2608.11508#A2.SS2.p2.1),[§2\.1](https://arxiv.org/html/2608.11508#S2.SS1.p3.1),[§2](https://arxiv.org/html/2608.11508#S2.p2.1)\.
- Taufiqet al\.\(2023\)M\. F\. Taufiqet al\.Manifold restricted interventional shapley values\.InInternational Conference on Artificial Intelligence and Statistics,pp\. 5079–5106\.Cited by:[§B\.1](https://arxiv.org/html/2608.11508#A2.SS1.p5.1),[§B\.1](https://arxiv.org/html/2608.11508#A2.SS1.p5.1.1),[§2\.1](https://arxiv.org/html/2608.11508#S2.SS1.p2.1),[§2\.1](https://arxiv.org/html/2608.11508#S2.SS1.p3.1),[§4\.1](https://arxiv.org/html/2608.11508#S4.SS1.p1.1)\.
- TPC \(2014\)TPCTPC\-h\.Note:https://www\.tpc\.org/tpch/Last accessed: April 2026Cited by:[§4](https://arxiv.org/html/2608.11508#S4.p1.1)\.
- Vanschorenet al\.\(2014\)J\. Vanschoren, J\. N\. Van Rijn, B\. Bischl, and L\. TorgoOpenML: networked science in machine learning\.ACM SIGKDD Explorations Newsletter15\(2\),pp\. 49–60\.Cited by:[Appendix I](https://arxiv.org/html/2608.11508#A9.p1.1)\.
- Webberet al\.\(2010\)W\. Webberet al\.A similarity measure for indefinite rankings\.ACM Transactions on Information Systems \(TOIS\)28\(4\),pp\. 1–38\.Cited by:[§4\.2](https://arxiv.org/html/2608.11508#S4.SS2.p2.1)\.
- Witteret al\.\(2025\)R\. T\. Witteret al\.Regression\-adjusted monte carlo estimators for shapley values and probabilistic values\.InThe Thirty\-ninth Annual Conference on Neural Information Processing Systems,Cited by:[§C\.4](https://arxiv.org/html/2608.11508#A3.SS4.p1.1),[§2\.2](https://arxiv.org/html/2608.11508#S2.SS2.p1.2)\.
- Witteret al\.\(2026\)R\. T\. Witter, Á\. Parafita, T\. Garriga, M\. Muschalik, F\. Fumagalli, A\. Brando, and L\. RosenblattExactly computing do\-shapley values\.arXiv preprint arXiv:2602\.07203\.Cited by:[§C\.4](https://arxiv.org/html/2608.11508#A3.SS4.p2.1),[§2\.2](https://arxiv.org/html/2608.11508#S2.SS2.p2.1),[Remark 1](https://arxiv.org/html/2608.11508#Thmremark1.p3.1.1)\.
- Yuanet al\.\(2022\)H\. Yuanet al\.An empirical study of the effect of background data size on the stability of shapley additive explanations \(shap\) for deep learning models\.arXiv preprint arXiv:2204\.11351\.Cited by:[§J\.1](https://arxiv.org/html/2608.11508#A10.SS1.p2.1),[§4](https://arxiv.org/html/2608.11508#S4.p2.1)\.
- Zernet al\.\(2023\)A\. Zernet al\.Interventional shap values and interaction values for piecewise linear regression trees\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.37,pp\. 11164–11173\.Cited by:[§B\.1](https://arxiv.org/html/2608.11508#A2.SS1.p2.1.1),[§2\.1](https://arxiv.org/html/2608.11508#S2.SS1.p2.1),[§2](https://arxiv.org/html/2608.11508#S2.p2.1)\.

## Appendix APrimer on Relational Concepts

This appendix provides background on relational database concepts used throughout the paper, aimed at readers whose primary background is in machine learning or explainable AI rather than data management\.

### A\.1Relational databases and tables

A*relational database*organizes data into a collection of*tables*\(also called*relations*\), each with a fixed set of named columns \(*attributes*\) and a variable set of rows \(*tuples*\)\. For example, in Example[1](https://arxiv.org/html/2608.11508#Thmexample1), the database contains two tables:Applicantswith attributesa\_id,age,life\_stage,empl, andTransactionswith attributest\_id,a\_id,amount\.

Tables are linked through shared attributes\. In the example,a\_idappears in both tables: it uniquely identifies each applicant inApplicantsand references the corresponding applicant inTransactions\. One applicant may have many transactions \(a*one\-to\-many*relationship\)\. This multi\-table structure allows the database to store each applicant’s attributes once, avoiding redundancy\.

### A\.2Keys and functional dependencies

A*key*is a set of attributes that uniquely identifies each row in a table\. InApplicants,a\_idis the*primary key*: no two rows share the samea\_id\. A key induces*functional dependencies*\(FDs\): ifa\_iduniquely identifies a row, then knowinga\_iddetermines all other attributes in that row\. Formally, we writea\_id→age\\texttt\{a\\\_id\}\\rightarrow\\texttt\{age\},a\_id→life\_stage\\texttt\{a\\\_id\}\\rightarrow\\texttt\{life\\\_stage\}, etc\.

FDs are not limited to keys\. Any deterministic relationship between attributes is an FD\. For instance, if every 35\-year\-old in the data has life stage “middle,” every 63\-year\-old has life stage “older,” and so on, thenage→life\_stage\\texttt\{age\}\\rightarrow\\texttt\{life\\\_stage\}holds\. This FD can be*discovered*directly from the data, without any schema declaration\. FD discovery is a well\-studied problem in the database community\([26](https://arxiv.org/html/2608.11508#bib.bib1);[44](https://arxiv.org/html/2608.11508#bib.bib57)\)\.

### A\.3Queries and aggregation

A*query*retrieves and transforms data from one or more tables\. The SQL query in Example[1](https://arxiv.org/html/2608.11508#Thmexample1)joinsApplicantswithTransactions\(matching rows bya\_id\), then groups the result by applicant and computes the sum of transaction amounts \(SUM\(t\.amount\) AS total\_amt\)\. TheGROUP BYclause produces exactly one output row per applicant, which means the grouping attributes \(here,a\_id\) uniquely determine the aggregated value\. This creates a*query\-induced FD*:a\_id→total\_amt\\texttt\{a\\\_id\}\\rightarrow\\texttt\{total\\\_amt\}\.

After the query executes, the identifiera\_idis typically dropped before model training, since identifiers carry no predictive signal\. However, the FDs thata\_idinduced remain latent in the flattened table\.

### A\.4Integrity constraints beyond FDs

Relational databases support several kinds of constraints beyond functional dependencies:

##### Domain constraints

restrict the values an attribute can take, possibly conditioned on other attributes\. For example, ifregion=‘North America’\\texttt\{region\}=\\text\{\`North America'\}thencurrency∈\{‘USD’,‘CAD’,‘MXN’\}\\texttt\{currency\}\\in\\\{\\text\{\`USD'\},\\text\{\`CAD'\},\\text\{\`MXN'\}\\\}\. These constraints capture real\-world restrictions that the data must satisfy\.

##### Denial constraints

express prohibitions: certain combinations of attribute values must never co\-occur\. A common example arises with one\-hot encoded categorical variables\. If a categorical attributegenderis encoded as three binary columns \(gender\_male,gender\_female,gender\_nonbinary\), then at most one column may equal 1 in any row\. Standard Shapley estimators can produce completions like\(1,1,0\)\(1,1,0\), violating this mutual exclusivity\.

##### Referential constraints

\(foreign keys\) require that a value appearing in one table must exist in another\. In the example, everya\_idinTransactionsmust correspond to an existinga\_idinApplicants\.

### A\.5Provenance

*Data provenance*tracks where each row in a derived dataset came from\. When a query joins and aggregates multiple source tables to produce a flattened ML\-ready table, provenance records, for each output row, which source tuples contributed to it\. In Example[1](https://arxiv.org/html/2608.11508#Thmexample1), the row withage=35\\texttt\{age\}=35in the flattened table was derived from applicanta27and transactionst67,t68,t69\.

Provenance is useful because it recovers structural information that flattening discards\. If we know that a particular output row came from a single source applicant, we can apply the source table’s constraints \(e\.g\., the schema\-level FDa\_id→empl\\texttt\{a\\\_id\}\\rightarrow\\texttt\{empl\}\) to further restrict which feature completions are valid during Shapley computation\.

Provenance tracking is a well\-studied area in the database community\([24](https://arxiv.org/html/2608.11508#bib.bib5);[8](https://arxiv.org/html/2608.11508#bib.bib2)\)\.RelShapuses a lightweight form of provenance that traces flattened rows back to their source tuples via identifier\-induced FDs that are no longer explicit in the feature set \(Section[3](https://arxiv.org/html/2608.11508#S3)\)\.

### A\.6What flattening loses

ML pipelines typically receive only the final flattened table\. This flattening discards several kinds of structural information:

- •FDsthat were enforced by the schema or induced by the query \(e\.g\.,age→life\_stage\\texttt\{age\}\\rightarrow\\texttt\{life\\\_stage\}\) become invisible; standard Shapley estimators freely generate combinations like\(age=35,life\_stage=older\)\(\\texttt\{age\}=35,\\texttt\{life\\\_stage\}=\\texttt\{older\}\)that violate them\.
- •Domain constraintssuch as valid value ranges or conditional restrictions are no longer enforced\.
- •Denial constraintssuch as one\-hot mutual exclusivity are not represented in the flat schema\.
- •Provenanceinformation linking each row to its source tuples is lost when identifiers are dropped\.

RelShaprecovers this information, either from the original relational schema and query \(when available\) or by discovering constraints directly from the data\. Section[3](https://arxiv.org/html/2608.11508#S3)describes the extraction procedure; the three sources of constraints \(schema\-level, query\-level, and data\-driven\) are detailed in Section[3\.1](https://arxiv.org/html/2608.11508#S3.SS1)\.

## Appendix BDetails about background data selection

### B\.1Background data selection methods

Sinceffis defined on the full feature spaceℝ\|F\|\\mathbb\{R\}^\{\|F\|\}, the entries of𝐱S\\mathbf\{x\}\_\{S\}corresponding toj∈F∖Sj\\in F\\setminus Smust be filled in\. Let𝒫bg​\(𝐳F∖S\)\\mathcal\{P\}\_\{\\mathrm\{bg\}\}\(\\mathbf\{z\}\_\{F\\setminus S\}\)denote a background distribution over the absent features indexed byF∖SF\\setminus S, letBBbe the number of background samples \(possibly all reference data points\), and𝐳F∖S\(1\),…,𝐳F∖S\(B\)∼𝒫bg\.\\mathbf\{z\}\_\{F\\setminus S\}^\{\(1\)\},\\ldots,\\mathbf\{z\}\_\{F\\setminus S\}^\{\(B\)\}\\sim\\mathcal\{P\}\_\{\\mathrm\{bg\}\}\.For a coalitionS⊆FS\\subseteq F, we construct a completed input𝐱~​\(S,𝐳F∖S\)∈ℝ\|F\|\\tilde\{\\mathbf\{x\}\}\(S,\\mathbf\{z\}\_\{F\\setminus S\}\)\\in\\mathbb\{R\}^\{\|F\|\}by

x~j​\(S,𝐳F∖S\)=\{xj,if​j∈S,zj,if​j∈F∖S,\\tilde\{x\}\_\{j\}\(S,\\mathbf\{z\}\_\{F\\setminus S\}\)=\\begin\{cases\}x\_\{j\},&\\text\{if \}j\\in S,\\\\ z\_\{j\},&\\text\{if \}j\\in F\\setminus S,\\end\{cases\}and define

f⁡\(𝐱S\)=𝔼𝐳F∖S∼𝒫bg​\[f⁡\(𝐱~​\(S,𝐳F∖S\)\)\]\.f\(\\mathbf\{x\}\_\{S\}\)=\\mathbb\{E\}\_\{\\mathbf\{z\}\_\{F\\setminus S\}\\sim\\mathcal\{P\}\_\{\\mathrm\{bg\}\}\}\\Bigl\[f\\bigl\(\\tilde\{\\mathbf\{x\}\}\(S,\\mathbf\{z\}\_\{F\\setminus S\}\)\\bigr\)\\Bigr\]\.Methods differ in their choice of𝒫bg\\mathcal\{P\}\_\{\\mathrm\{bg\}\}\. We describe the four most representative instantiations below, and discuss the conceptual landscape they span at the end of this section\.

*Interventional approach\([28](https://arxiv.org/html/2608.11508#bib.bib13);[57](https://arxiv.org/html/2608.11508#bib.bib10)\)*treats feature absence as an intervention rather than as a conditioning event\. Under the standard assumption of feature independence, the distribution of the remaining features unchanged, so𝒫bg\\mathcal\{P\}\_\{\\mathrm\{bg\}\}reduces to the empirical*marginal*distribution of the training data,𝒫bgMarginal=πF∖S​\(𝒟train\)\\mathcal\{P\}\_\{\\mathrm\{bg\}\}^\{\\mathrm\{Marginal\}\}=\\pi\_\{F\\setminus S\}\(\\mathcal\{D\}\_\{\\mathrm\{train\}\}\); we refer to this construction as the*marginal*approach throughout the paper\. Default Kernel SHAP\([34](https://arxiv.org/html/2608.11508#bib.bib6)\)is its most widely deployed implementation\. Under this choice, dependencies between observed features in𝐱\\mathbf\{x\}and the imputed features in𝐳\\mathbf\{z\}are broken: the completed input𝐱~​\(S,𝐳\)\\tilde\{\\mathbf\{x\}\}\(S,\\mathbf\{z\}\)may lie off the data manifold, although it may coincidentally fall on it\.

*Conditional approach\([1](https://arxiv.org/html/2608.11508#bib.bib8)\)*sets𝒫bg\\mathcal\{P\}\_\{\\mathrm\{bg\}\}to the conditional distribution of the absent features given the observed ones, estimated from𝒟train\\mathcal\{D\}\_\{\\mathrm\{train\}\}via, e\.g\., a multivariate Gaussian assumption, a Gaussian copula, or an empirical conditional,𝒫bgConditional=P^​\(𝐙F∖S∣𝐗S=𝐱S\)\\mathcal\{P\}\_\{\\mathrm\{bg\}\}^\{\\mathrm\{Conditional\}\}=\\widehat\{P\}\\bigl\(\\mathbf\{Z\}\_\{F\\setminus S\}\\mid\\mathbf\{X\}\_\{S\}=\\mathbf\{x\}\_\{S\}\\bigr\)\. The estimated distribution may not faithfully recover the true underlying one and can introduce spurious dependencies, but the formulation aims to capture inter\-feature dependencies and is referred to as*observational*\.

*Causal approach\([25](https://arxiv.org/html/2608.11508#bib.bib9)\)*extends the interventional formulation by exploiting a known causal graph among the features:𝒫bgCausal=P^​\(𝐙F∖S∣d​o​\(𝐗S=𝐱S\)\)\\mathcal\{P\}\_\{\\mathrm\{bg\}\}^\{\\mathrm\{Causal\}\}=\\widehat\{P\}\\bigl\(\\mathbf\{Z\}\_\{F\\setminus S\}\\mid do\(\\mathbf\{X\}\_\{S\}=\\mathbf\{x\}\_\{S\}\)\\bigr\), where Pearl’sd​o​\(⋅\)do\(\\cdot\)propagates the intervention through the assumed causal mechanisms rather than \(as in the marginal case\) leaving𝐙F∖S\\mathbf\{Z\}\_\{F\\setminus S\}unchanged\. Two cases arise depending on the structure:*cycle*\(bidirectional, similar to the conditional approach\) and*chain*\(unidirectional\)\.

*On\-manifold approach\([50](https://arxiv.org/html/2608.11508#bib.bib11)\)*does not specify a probabilistic form for𝒫bg\\mathcal\{P\}\_\{\\mathrm\{bg\}\}\. Instead, it restricts attention to a region of interestZZthat approximates the geometric data manifold and excludes off\-manifold samples:𝒫bgManifold=P^​\(𝐙F∖S∣d​o​\(𝐗S=𝐱S\),𝐗∈Z\)\\mathcal\{P\}\_\{\\mathrm\{bg\}\}^\{\\mathrm\{Manifold\}\}=\\widehat\{P\}\\bigl\(\\mathbf\{Z\}\_\{F\\setminus S\}\\mid do\(\\mathbf\{X\}\_\{S\}=\\mathbf\{x\}\_\{S\}\),\\;\\mathbf\{X\}\\in Z\\bigr\)\. Membership inZZis determined by a surrogate manifold classifiergg\(e\.g\., via kernel density estimation\), and off\-manifold samples are generated through perturbation; the resulting explanations may depend on the quality of the classifier\. ManifoldShap\([50](https://arxiv.org/html/2608.11508#bib.bib11)\)is the canonical instance\.

### B\.2Perspectives on background data selection

The four formulations above span the*true to the model*vs\.*true to the data*axis introduced in Section[1](https://arxiv.org/html/2608.11508#S1): the marginal construction \(default Kernel SHAP\) stays*true to the model*by ignoring inter\-feature dependencies, while the conditional, causal, and on\-manifold approaches each attempt, in different ways, to stay*true to the data*by capturing or respecting such dependencies\.RelShapis orthogonal to this axis: rather than choosing*what distribution*to put on the absent features, it constrains*which configurations*the chosen distribution is allowed to place mass on\. Given any base background distribution𝒫bgbase\\mathcal\{P\}\_\{\\mathrm\{bg\}\}^\{\\mathrm\{base\}\}\(marginal, conditional, causal, or manifold\),RelShaprestricts its support to completions that satisfy the relational constraintsΣ\\Sigmaextracted from the schema, query, and data \(Def\.[1](https://arxiv.org/html/2608.11508#Thmdefinition1)\)\. The two design dimensions therefore compose rather than conflict:RelShapcan be layered on top of any of the four formulations above\.

By default we use the marginal \(Kernel SHAP\([34](https://arxiv.org/html/2608.11508#bib.bib6)\)\) as the base, since it requires no distributional assumptions and is widely used; relational restriction then rules out completions that are infeasible under the schema and query \(e\.g\.,𝚊𝚐𝚎=35\\mathtt\{age\}=35paired with𝚕𝚒𝚏𝚎​\_​𝚜𝚝𝚊𝚐𝚎=𝚘𝚕𝚍𝚎𝚛\\mathtt\{life\\\_stage\}=\\mathtt\{older\}when the FD𝚊𝚐𝚎→𝚕𝚒𝚏𝚎​\_​𝚜𝚝𝚊𝚐𝚎\\mathtt\{age\}\\to\\mathtt\{life\\\_stage\}has been identified\) without estimating any conditional density\. This restriction preserves the no\-distributional assumptions property advocated by[49](https://arxiv.org/html/2608.11508#bib.bib12)and[28](https://arxiv.org/html/2608.11508#bib.bib13)while removing the structural off\-manifold inputs[19](https://arxiv.org/html/2608.11508#bib.bib14)warns about\. Appendix[B\.3](https://arxiv.org/html/2608.11508#A2.SS3)formalizes this on a two\-feature linear model\.

### B\.3True to the data vs\. True to the model

Let

X1∼Unif⁡\{1,2,…,8\},X2=g⁡\(X1\)=⌈X12⌉\.X\_\{1\}\\sim\\mathrm\{Unif\}\\\{1,2,\\dots,8\\\},\\;\\;X\_\{2\}=g\(X\_\{1\}\)=\\left\\lceil\\frac\{X\_\{1\}\}\{2\}\\right\\rceil\.with

𝔼⁡\[X1\]=4\.5,𝔼⁡\[X2\]=2\.5\.\\mathbb\{E\}\[X\_\{1\}\]=4\.5,\\;\\;\\mathbb\{E\}\[X\_\{2\}\]=2\.5\.Then fix a target point

x=\(x1,x2\)=\(k,b\),b=⌈k2⌉\.x=\(x\_\{1\},x\_\{2\}\)=\(k,b\),\\;\\;b=\\left\\lceil\\frac\{k\}\{2\}\\right\\rceil\.
Kernel SHAP\.Absent features are filled independently from their marginal distributions by ignoring dependencies present in the data, which follows a*true to the model*perspective\.

One\-way \(unidirectional\) FD\-aware \(X1→X2X\_\{1\}\\to X\_\{2\}\)\.IfX1X\_\{1\}is observed,X2X\_\{2\}is deterministically recovered viagg, following a*true to the data*viewpoint\. If onlyX2X\_\{2\}is observed, we assume no information aboutX1X\_\{1\}and fall back to the Kernel SHAP treatment \(*true to the model*\)\. It aligns with theRelShapapproach when only the functional dependency is known, and also corresponds to thechaincase in\([25](https://arxiv.org/html/2608.11508#bib.bib9)\)\.

Bidirectionally aware \(X1↔X2X\_\{1\}\\leftrightarrow X\_\{2\}\)\.This aligns with thecyclecase described in\([25](https://arxiv.org/html/2608.11508#bib.bib9)\), reflecting*true to the data*perspective where observing either feature determines the other\. In this example, knowing the functionggalone is not sufficient, sinceggis not injective \(many\-to\-one\), and therefore an inverse functiong−1g^\{\-1\}does not exist\. The preimage setg−1​\(x2\)=\{x1∣g⁡\(x1\)=x2\}g^\{\-1\}\(x\_\{2\}\)=\\\{x\_\{1\}\\mid g\(x\_\{1\}\)=x\_\{2\}\\\}indicates that observingX2X\_\{2\}only reveals a range of possible values forX1X\_\{1\}, rather than its exact value\. Therefore, in this setting we assume that the dataset is fully known, i\.e\., the exact pairs\(X1,X2\)\(X\_\{1\},X\_\{2\}\)are available\.

Since the goal of this example is to illustrate how feature dependence affects attribution, we assume a simple linear model

f⁡\(x1,x2\)=α​x1\+β​x2,f\(x\_\{1\},x\_\{2\}\)=\\alpha x\_\{1\}\+\\beta x\_\{2\},whereα,β∈ℝ\\alpha,\\beta\\in\\mathbb\{R\}, and intentionally exclude nonlinear interactions or the absence of one of the features \(i\.e\., single\-feature settings discussed in\([25](https://arxiv.org/html/2608.11508#bib.bib9)\)\), so that the analysis focuses only on the presence of feature dependence\. In all three cases,

f∅=𝔼⁡\[f⁡\(X1,X2\)\]=α​𝔼​\[X1\]\+β​𝔼​\[X2\]=4\.5​α\+2\.5​β\.f\_\{\\emptyset\}=\\mathbb\{E\}\[f\(X\_\{1\},X\_\{2\}\)\]=\\alpha\\mathbb\{E\}\[X\_\{1\}\]\+\\beta\\mathbb\{E\}\[X\_\{2\}\]=4\.5\\alpha\+2\.5\\beta\.f\{1,2\}=f⁡\(k,b\)=α​k\+β​b\.f\_\{\\\{1,2\\\}\}=f\(k,b\)=\\alpha k\+\\beta b\.
Kernel SHAP\.

f\{1\}=𝔼⁡\[f⁡\(k,X2\)\]=α​k\+β​𝔼​\[X2\]=α​k\+2\.5​βf\_\{\\\{1\\\}\}=\\mathbb\{E\}\[f\(k,X\_\{2\}\)\]=\\alpha k\+\\beta\\mathbb\{E\}\[X\_\{2\}\]=\\alpha k\+2\.5\\betaf\{2\}=𝔼⁡\[f⁡\(X1,b\)\]=α​𝔼​\[X1\]\+β​b=4\.5​α\+β​bf\_\{\\\{2\\\}\}=\\mathbb\{E\}\[f\(X\_\{1\},b\)\]=\\alpha\\mathbb\{E\}\[X\_\{1\}\]\+\\beta b=4\.5\\alpha\+\\beta b
The resulting Shapley values:

ϕ1Marginal=12​\(f\{1\}−f∅\)\+12​\(f\{1,2\}−f\{2\}\)=α⁡\(k−4\.5\)\\phi\_\{1\}^\{\\mathrm\{Marginal\}\}=\\frac\{1\}\{2\}\(f\_\{\\\{1\\\}\}\-f\_\{\\emptyset\}\)\+\\frac\{1\}\{2\}\(f\_\{\\\{1,2\\\}\}\-f\_\{\\\{2\\\}\}\)=\\alpha\(k\-4\.5\)ϕ2Marginal=12​\(f\{2\}−f∅\)\+12​\(f\{1,2\}−f\{1\}\)=β⁡\(b−2\.5\)\\phi\_\{2\}^\{\\mathrm\{Marginal\}\}=\\frac\{1\}\{2\}\(f\_\{\\\{2\\\}\}\-f\_\{\\emptyset\}\)\+\\frac\{1\}\{2\}\(f\_\{\\\{1,2\\\}\}\-f\_\{\\\{1\\\}\}\)=\\beta\(b\-2\.5\)
X1→X2X\_\{1\}\\to X\_\{2\}\.

IfX1X\_\{1\}is known, thenX2X\_\{2\}is determined:

f\{1\}=f⁡\(k,g⁡\(k\)\)=f⁡\(k,b\)=α​k\+β​bf\_\{\\\{1\\\}\}=f\(k,g\(k\)\)=f\(k,b\)=\\alpha k\+\\beta b
If onlyX2X\_\{2\}is known,X1X\_\{1\}cannot be recovered since the mappingggis not assumed to be known \(otherwise a piecewise inverse could be specified\)\. Thus the marginal distribution ofX1X\_\{1\}is used,

f\{2\}=𝔼⁡\[f⁡\(X1,b\)\]=α​𝔼​\[X1\]\+β​b=4\.5​α\+β​bf\_\{\\\{2\\\}\}=\\mathbb\{E\}\[f\(X\_\{1\},b\)\]=\\alpha\\mathbb\{E\}\[X\_\{1\}\]\+\\beta b=4\.5\\alpha\+\\beta b
The resulting Shapley values:

ϕ1FD=12​\(f\{1\}−f∅\)\+12​\(f\{1,2\}−f\{2\}\)\\phi\_\{1\}^\{\\mathrm\{FD\}\}=\\frac\{1\}\{2\}\(f\_\{\\\{1\\\}\}\-f\_\{\\emptyset\}\)\+\\frac\{1\}\{2\}\(f\_\{\\\{1,2\\\}\}\-f\_\{\\\{2\\\}\}\)=12​\[\(α​k\+β​b\)−\(4\.5​α\+2\.5​β\)\]\+12​\[\(α​k\+β​b\)−\(4\.5​α\+β​b\)\]=\\frac\{1\}\{2\}\[\(\\alpha k\+\\beta b\)\-\(4\.5\\alpha\+2\.5\\beta\)\]\+\\frac\{1\}\{2\}\[\(\\alpha k\+\\beta b\)\-\(4\.5\\alpha\+\\beta b\)\]=α⁡\(k−4\.5\)\+β2​\(b−2\.5\)=\\alpha\(k\-4\.5\)\+\\frac\{\\beta\}\{2\}\(b\-2\.5\)ϕ2FD=12​\(f\{2\}−f∅\)\+12​\(f\{1,2\}−f\{1\}\)\\phi\_\{2\}^\{\\mathrm\{FD\}\}=\\frac\{1\}\{2\}\(f\_\{\\\{2\\\}\}\-f\_\{\\emptyset\}\)\+\\frac\{1\}\{2\}\(f\_\{\\\{1,2\\\}\}\-f\_\{\\\{1\\\}\}\)=12​\[\(4\.5​α\+β​b\)−\(4\.5​α\+2\.5​β\)\]\+12​\[\(α​k\+β​b\)−\(α​k\+β​b\)\]=\\frac\{1\}\{2\}\[\(4\.5\\alpha\+\\beta b\)\-\(4\.5\\alpha\+2\.5\\beta\)\]\+\\frac\{1\}\{2\}\[\(\\alpha k\+\\beta b\)\-\(\\alpha k\+\\beta b\)\]=β2​\(b−2\.5\)=\\frac\{\\beta\}\{2\}\(b\-2\.5\)
Difference from the marginal case\.

ϕ1FD−ϕ1Marginal=β2​\(b−2\.5\),\\phi\_\{1\}^\{\\mathrm\{FD\}\}\-\\phi\_\{1\}^\{\\mathrm\{Marginal\}\}=\\frac\{\\beta\}\{2\}\(b\-2\.5\),ϕ2FD−ϕ2Marginal=−β2​\(b−2\.5\)\.\\phi\_\{2\}^\{\\mathrm\{FD\}\}\-\\phi\_\{2\}^\{\\mathrm\{Marginal\}\}=\-\\frac\{\\beta\}\{2\}\(b\-2\.5\)\.
Thus part of the attribution that would otherwise be assigned to the derived featureX2X\_\{2\}is transferred to the root featureX1X\_\{1\}when the dependencyX1→X2X\_\{1\}\\to X\_\{2\}is respected\. The exact magnitude of this effect depends on the model coefficientβ\\betaonX2X\_\{2\}, and on the deviation ofbbfrom its mean value𝔼⁡\[X2\]=2\.5\\mathbb\{E\}\[X\_\{2\}\]=2\.5\.

X1↔X2X\_\{1\}\\leftrightarrow X\_\{2\}\.

f\{1\}=f\{2\}=f\{1,2\}=α​k\+β​bf\_\{\\\{1\\\}\}=f\_\{\\\{2\\\}\}=f\_\{\\\{1,2\\\}\}=\\alpha k\+\\beta b
The resulting Shapley values:

ϕ1=ϕ2=12​\(f\{1,2\}−f∅\)=12​\(α​k\+β​b−4\.5​α−2\.5​β\)\\phi\_\{1\}=\\phi\_\{2\}=\\frac\{1\}\{2\}\(f\_\{\\\{1,2\\\}\}\-f\_\{\\emptyset\}\)=\\frac\{1\}\{2\}\(\\alpha k\+\\beta b\-4\.5\\alpha\-2\.5\\beta\)
Discussion\.

The three approaches produce qualitatively different attributions since they incorporate the dependency structure to different extents, even when all other conditions held fixed\. The marginal approach ignores the relation between the variables and treatsX1X\_\{1\}andX2X\_\{2\}as independently manipulable\. As a result, the Shapley values are allocated according to the model coefficients, with only the mean subtracted from each feature\. ForX1↔X2X\_\{1\}\\leftrightarrow X\_\{2\}case, the two variables become informationally indistinguishable, making the Shapley values split evenly between the two features\. Overall, the resulting attributions still depend on the model coefficient, reflecting the*true to the model*perspective\. However, by incorporating the functional dependency structure \(X1→X2X\_\{1\}\\to X\_\{2\}\), part of the attribution that would otherwise be assigned to the derived attributeX2X\_\{2\}is transferred to the root attributeX1X\_\{1\}\. This reflects a*true to the data*perspective, where the explanation respects the dependency structure of the underlying data\. Importantly, this simplified redistribution arises since we considered only two features with a single FD between them\. As the number of features or FDs increases, the reallocation is governed by the joint dependency structure, making the resulting Shapley value more complex and less directly traceable\.

## Appendix CDetails about coalition samplers

In this section, we restate the formulations used in existing works using our notation and describe their coalition sampling procedures based on their code implementations\. This clarification is necessary for our theoretical development in Section[3\.3](https://arxiv.org/html/2608.11508#S3.SS3)\.

### C\.1Kernel SHAP

*Kernel SHAP\([34](https://arxiv.org/html/2608.11508#bib.bib6)\)*estimates Shapley values by fitting a weighted linear surrogate whose solution coincides withϕ⁡\(f\)\\phi\(f\)\. Each coalition is weighted by the*Shapley kernel*,

wKernel​\(S\)=\|F\|−1\(\|F\|\|S\|\)​\|S\|​\(\|F\|−\|S\|\),w\_\{\\mathrm\{Kernel\}\}\(S\)=\\frac\{\|F\|\-1\}\{\\binom\{\|F\|\}\{\|S\|\}\\,\|S\|\\,\(\|F\|\-\|S\|\)\},which depends only on\|S\|\|S\|and concentrates weight on extreme \(very small or very large\) coalition sizes; coalitions are sampled accordingly\. A coalition is a subsetS⊆FS\\subseteq F, equivalently represented by a binary maskz′∈\{0,1\}\|F\|z^\{\\prime\}\\in\\\{0,1\\\}^\{\|F\|\}where\|F\|\|F\|denote the number of features considered in the explanation, and letS⁡\(z′\)=\{j∈F∣zj′=1\}S\(z^\{\\prime\}\)=\\\{j\\in F\\mid z^\{\\prime\}\_\{j\}=1\\\}\.

Coalitions are sampled using a hybrid strategy\. First, a subset sizes∈\{1,…,\|F\|−1\}s\\in\\\{1,\\ldots,\|F\|\-1\\\}is drawn, excluding the trivial coalitions corresponding to the empty and full sets\. These trivial cases are handled separately and computed once since there is only one coalition of each type, whereas intermediate sizes contain multiple candidates\.

For non\-trivial coalitions, Kernel SHAP defines a coalition sampling distribution𝒫coalKernel\\mathcal\{P\}^\{\\mathrm\{Kernel\}\}\_\{\\mathrm\{coal\}\}by first allocating probability mass across subset sizes according to

𝒫coalKernel​\(\|S\|=s\)∝1s⁡\(\|F\|−s\)\.\\mathcal\{P\}^\{\\mathrm\{Kernel\}\}\_\{\\mathrm\{coal\}\}\(\|S\|=s\)\\;\\propto\\;\\frac\{1\}\{s\(\|F\|\-s\)\}\.Once a subset sizessis determined, a coalitionS⊆FS\\subseteq Fwith\|S\|=s\|S\|=sis sampled uniformly at random among all subsets of that size, i\.e\.,

𝒫coalKernel​\(S∣\|S\|=s\)=1\(\|F\|s\)\.\\mathcal\{P\}^\{\\mathrm\{Kernel\}\}\_\{\\mathrm\{coal\}\}\(S\\mid\|S\|=s\)=\\frac\{1\}\{\\binom\{\|F\|\}\{s\}\}\.Consequently, the overall coalition sampling distribution satisfies

𝒫coalKernel​\(S\)∝1\(\|F\|\|S\|\)​\|S\|​\(\|F\|−\|S\|\),\\mathcal\{P\}^\{\\mathrm\{Kernel\}\}\_\{\\mathrm\{coal\}\}\(S\)\\;\\propto\\;\\frac\{1\}\{\\binom\{\|F\|\}\{\|S\|\}\\,\|S\|\(\|F\|\-\|S\|\)\},which matches the size\-dependent structure induced by the Shapley kernel stated below\.

In practice, when the number of features is sufficiently small, Kernel SHAP deterministically enumerates all coalitions of a given size whenever the sampling budget permits\. Concretely, if the requested number of samples exceeds the number of possible non\-trivial coalitions \(i\.e\.,2\|F\|−22^\{\|F\|\}\-2\), the algorithm simply enumerates the entire coalition space instead of performing random sampling\. The randomized sampling scheme described above is therefore used only when the feature dimension is large enough that full enumeration becomes infeasible\.

During random sampling with replacement, duplicate coalitions may occasionally occur\. Although the number of possible coalitions grows exponentially with the number of features\-making such collisions relatively unlikely in practice\-Kernel SHAP handles them explicitly\. When a coalition that has already been observed is drawn again, the algorithm does not add a new row to the regression design matrix\. Instead, it increases the weight associated with the existing coalition so that the resulting weighted regression correctly reflects the number of times that coalition was sampled\.

Given a coalition budgetMM, we sample coalitionsS\(1\),…,S\(M\)∼𝒫coalKernelS^\{\(1\)\},\\ldots,S^\{\(M\)\}\\sim\\mathcal\{P\}\_\{\\mathrm\{coal\}\}^\{\\mathrm\{Kernel\}\}, Kernel SHAP assigns each coalition a regression weight determined by the Shapley kernel:

wKernel​\(S\(m\)\)∝π⁡\(\|F\|,\|S\(m\)\|\),w\_\{\\mathrm\{Kernel\}\}\\\!\\left\(S^\{\(m\)\}\\right\)\\;\\propto\\;\\pi\\bigl\(\|F\|,\|S^\{\(m\)\}\|\\bigr\),where the Shapley kernel is a size\-dependent function defined for nontrivial coalitions \(0<\|S⁡\(z′\)\|<\|F\|0<\|S\(z^\{\\prime\}\)\|<\|F\|\) as:

π⁡\(z′\)=π⁡\(\|F\|,\|S⁡\(z′\)\|\)=\|F\|−1\(\|F\|\|S⁡\(z′\)\|\)​\|S⁡\(z′\)\|​\(\|F\|−\|S⁡\(z′\)\|\)\.\\pi\(z^\{\\prime\}\)=\\pi\\bigl\(\|F\|,\|S\(z^\{\\prime\}\)\|\\bigr\)=\\frac\{\|F\|\-1\}\{\\binom\{\|F\|\}\{\|S\(z^\{\\prime\}\)\|\}\\,\|S\(z^\{\\prime\}\)\|\\,\(\|F\|\-\|S\(z^\{\\prime\}\)\|\)\}\.
Then Kernel SHAP fits a linear surrogateg⁡\(z′\)=ϕ0\+∑j∈Fϕj​zj′g\(z^\{\\prime\}\)=\\phi\_\{0\}\+\\sum\_\{j\\in F\}\\phi\_\{j\}z^\{\\prime\}\_\{j\}by minimizing the weighted squared loss

min⁡∑m=1Mϕ0,\{ϕj\}j∈F⁡w⁡\(S\(m\)\)​\(f⁡\(𝐱~​\(S\(m\)\)\)−ϕ0−∑j∈Fϕj​zj′\(m\)\)2,\\min\_\{\\phi\_\{0\},\\\{\\phi\_\{j\}\\\}\_\{j\\in F\}\}\\sum\_\{m=1\}^\{M\}w\\bigl\(S^\{\(m\)\}\\bigr\)\\,\\Bigl\(f\\bigl\(\\tilde\{\\mathbf\{x\}\}\(S^\{\(m\)\}\)\\bigr\)\-\\phi\_\{0\}\-\\sum\_\{j\\in F\}\\phi\_\{j\}z^\{\\prime\(m\)\}\_\{j\}\\Bigr\)^\{2\},subject to the two endpoint constraints induced byπ⁡\(z′\)=∞\\pi\(z^\{\\prime\}\)=\\infty:

g⁡\(𝟎\)=f⁡\(𝐱~​\(∅\)\)andg⁡\(𝟏\)=f⁡\(𝐱~​\(F\)\),g\(\\mathbf\{0\}\)=f\(\\tilde\{\\mathbf\{x\}\}\(\\emptyset\)\)\\quad\\text\{and\}\\quad g\(\\mathbf\{1\}\)=f\(\\tilde\{\\mathbf\{x\}\}\(F\)\),which are equivalent toϕ0=f​\(𝐱~​\(∅\)\)\\phi\_\{0\}=f\(\\tilde\{\\mathbf\{x\}\}\(\\emptyset\)\)and∑j∈Fϕj=f⁡\(𝐱~​\(F\)\)−f⁡\(𝐱~​\(∅\)\)\\sum\_\{j\\in F\}\\phi\_\{j\}=f\(\\tilde\{\\mathbf\{x\}\}\(F\)\)\-f\(\\tilde\{\\mathbf\{x\}\}\(\\emptyset\)\)\. The resulting coefficients\{ϕj\}j∈F\\\{\\phi\_\{j\}\\\}\_\{j\\in F\}are the Kernel SHAP attributions\.

### C\.2Monte Carlo coalition estimator

*Monte Carlo \(MC\) estimator*fixes a feature of interesti∈Fi\\in Fand samples coalitionsS⊆F∖\{i\}S\\subseteq F\\setminus\\\{i\\\}from the Shapley\-weighted distribution

𝒫coalMC​\(S∣i\)=\|S\|\!​\(\|F\|−\|S\|−1\)\!\|F\|\!,wMC​\(S\)=1\.\\mathcal\{P\}\_\{\\mathrm\{coal\}\}^\{\\mathrm\{MC\}\}\(S\\mid i\)=\\frac\{\|S\|\!\(\|F\|\-\|S\|\-1\)\!\}\{\|F\|\!\},\\qquad w\_\{\\mathrm\{MC\}\}\(S\)=1\.Since𝒫coalMC\\mathcal\{P\}\_\{\\mathrm\{coal\}\}^\{\\mathrm\{MC\}\}matches the coefficients in Eq\. \([1](https://arxiv.org/html/2608.11508#S2.E1)\), the resulting estimator is unbiased forϕi​\(f\)\\phi\_\{i\}\(f\)\. It is conceptually simple but may require many samples to converge\. In practice, coalition sizes are sampled approximately uniformly\. Each Monte Carlo draw first samples a pivot \(a feature to explain\)i∼Unif⁡\(F\)\.i\\sim\\mathrm\{Unif\}\(F\)\.Conditioned onii, the estimator samples coalitionsS⊆F∖\{i\}S\\subseteq F\\setminus\\\{i\\\}by first sampling a coalition size

K∼Unif⁡\(\{0,1,…,\|F\|−1\}\),K\\sim\\mathrm\{Unif\}\(\\\{0,1,\\ldots,\|F\|\-1\\\}\),and then sampling a subsetSSuniformly at random among all size\-KKsubsets ofF∖\{i\}F\\setminus\\\{i\\\}\. This two\-stage procedure induces a distribution over coalitionsS⊆F∖\{i\}S\\subseteq F\\setminus\\\{i\\\}\. For any fixediiand coalitionS⊆F∖\{i\}S\\subseteq F\\setminus\\\{i\\\}, the probability thatSSis sampled is

ℙ⁡\(S∣i\)\\displaystyle\\mathbb\{P\}\(S\\mid i\)=ℙ⁡\(\|S\|=k∣i\)⋅ℙ⁡\(S∣\|S\|=k,i\)\\displaystyle=\\mathbb\{P\}\(\|S\|=k\\mid i\)\\cdot\\mathbb\{P\}\(S\\mid\|S\|=k,i\)=1\|F\|⋅1\(\|F\|−1\|S\|\)=\|S\|\!​\(\|F\|−\|S\|−1\)\!\|F\|\!,\\displaystyle=\\frac\{1\}\{\|F\|\}\\cdot\\frac\{1\}\{\\binom\{\|F\|\-1\}\{\|S\|\}\}=\\frac\{\|S\|\!\(\|F\|\-\|S\|\-1\)\!\}\{\|F\|\!\},which exactly matches the Shapley coefficient in Eq\. \([1](https://arxiv.org/html/2608.11508#S2.E1)\)\. Each Monte Carlo draw samples a pivot uniformly, a coalition size uniformly, and a subset uniformly within that size, inducing a Shapley\-weighted distribution over coalitions\.

### C\.3Leverage SHAP

*Leverage SHAP\([39](https://arxiv.org/html/2608.11508#bib.bib22)\)*solves the same regression formulation as Kernel SHAP but adopts a*leverage score*\-based sampling strategy with provable accuracy guarantees\. It first selects a coalition size with approximately equal probability and then samples a coalition uniformly at random among all coalitions of that size, so all sizes appear with comparable frequency rather than the extremes being overrepresented\. The regression weight \(the leverage score\) depends only on\|S\|\|S\|\. LetZ∈ℝρ×\|F\|Z\\in\\mathbb\{R\}^\{\\rho\\times\|F\|\}andy∈ℝρy\\in\\mathbb\{R\}^\{\\rho\}denote the full regression system \(as in Kernel SHAP\) over all coalitions with0<\|S\|<\|F\|0<\|S\|<\|F\|\(which bringsρ=2\|F\|−2\\rho=2^\{\|F\|\}\-2\), where each row corresponds to a coalition indicator vector\. To enforce the efficiency constraint, define the projection matrixP=I−1\|F\|​𝟏𝟏⊤P=I\-\\frac\{1\}\{\|F\|\}\\mathbf\{1\}\\mathbf\{1\}^\{\\top\}and consider the unconstrained systemA=Z​PA=ZPandb=y−Z​𝟏​v⁡\(𝟏\)−v⁡\(𝟎\)\|F\|b=y\-Z\\mathbf\{1\}\\,\\frac\{v\(\\mathbf\{1\}\)\-v\(\\mathbf\{0\}\)\}\{\|F\|\}\.

Leverage SHAP samples coalitions according to a distribution𝒫coalLeverage\\mathcal\{P\}\_\{\\mathrm\{coal\}\}^\{\\mathrm\{Leverage\}\}over0<\|S\|<\|F\|0<\|S\|<\|F\|\. In this problem, the leverage scores admit a closed form: all coalitions of the same size share the same score, and the total sampling mass is allocated by coalition size\. Consequently, the sampling design is stratified by coalition size\. Letmsm\_\{s\}denote the number of sampled coalitions of sizessamong theMMdraws with∑s=1\|F\|−1ms=M\\sum\_\{s=1\}^\{\|F\|\-1\}m\_\{s\}=Mfor a given budgetMM\. Within each stratum corresponding to coalition sizess,msm\_\{s\}coalitions are sampled uniformly without replacement from the\(\|F\|s\)\\binom\{\|F\|\}\{s\}possible coalitions of that size\. Then every coalitionSSwith\|S\|=s\|S\|=shas the same inclusion probability

𝒫coalLeverage​\(S\)=p⁡\(S\)=m\|S\|\(\|F\|\|S\|\)\.\\mathcal\{P\}\_\{\\mathrm\{coal\}\}^\{\\mathrm\{Leverage\}\}\(S\)=p\(S\)=\\frac\{m\_\{\|S\|\}\}\{\\binom\{\|F\|\}\{\|S\|\}\}\.
Given the sampled coalitionsS\(1\),…,S\(M\)S^\{\(1\)\},\\ldots,S^\{\(M\)\}generated by this stratified sampling design, the estimator solves a reweighted least\-squares problem with per\-sample weight

wLeverage​\(S\(m\)\)∝π⁡\(\|S\(m\)\|\)𝒫coalLeverage​\(S\(m\)\),w\_\{\\mathrm\{Leverage\}\}\\\!\\left\(S^\{\(m\)\}\\right\)\\propto\\frac\{\\pi\\\!\\left\(\|S^\{\(m\)\}\|\\right\)\}\{\\mathcal\{P\}\_\{\\mathrm\{coal\}\}^\{\\mathrm\{Leverage\}\}\\\!\\left\(S^\{\(m\)\}\\right\)\},whereπ⁡\(⋅\)\\pi\(\\cdot\)denotes the Shapley kernel defined in Appendix[C\.1](https://arxiv.org/html/2608.11508#A3.SS1)\. The estimator then solves

ϕ^⟂=arg⁡min⁡∑m=1Mβ⁡wLeverage​\(S\(m\)\)​\(⟨a⁡\(S\(m\)\),β⟩−b⁡\(S\(m\)\)\)2,\\hat\{\\phi\}\_\{\\perp\}=\\arg\\min\_\{\\beta\}\\sum\_\{m=1\}^\{M\}w\_\{\\mathrm\{Leverage\}\}\\\!\\left\(S^\{\(m\)\}\\right\)\\Bigl\(\\langle a\(S^\{\(m\)\}\),\\beta\\rangle\-b\(S^\{\(m\)\}\)\\Bigr\)^\{2\},wherea⁡\(S\)a\(S\)andb⁡\(S\)b\(S\)denote the corresponding row ofAAand entry ofbb\. Finally, it returns

ϕ^=ϕ^⟂\+v⁡\(𝟏\)−v⁡\(𝟎\)\|F\|​𝟏,\\hat\{\\phi\}=\\hat\{\\phi\}\_\{\\perp\}\+\\frac\{v\(\\mathbf\{1\}\)\-v\(\\mathbf\{0\}\)\}\{\|F\|\}\\mathbf\{1\},which satisfies the efficiency constraint by construction\. In practice, ridge regularization may be added if the subsampled normal matrix is ill\-conditioned\.

### C\.4Perspectives on coalition selection

The three estimators above span a design space defined by bias, variance, and accuracy guarantees: Kernel SHAP is faster but biased toward extreme coalition sizes; MC is unbiased but slow to converge; Leverage SHAP equalizes coverage across sizes and offers provable accuracy guarantees\. Recent estimators improve this space along orthogonal directions:[54](https://arxiv.org/html/2608.11508#bib.bib30)reduce variance via residual estimation against a learned surrogate, while PolySHAP\([21](https://arxiv.org/html/2608.11508#bib.bib31)\)and OddSHAP\([20](https://arxiv.org/html/2608.11508#bib.bib29)\)use higher\-order polynomial regression and Fourier\-basis reduction, respectively, to improve accuracy and efficiency\.

RelShapis orthogonal to all of these: rather than introducing a new sampling distribution or weighting scheme, it acts as a plug\-in restriction layer that prunes the coalition space to relationally valid configurations before any estimator is applied \(Def\.[1](https://arxiv.org/html/2608.11508#Thmdefinition1)\)\. It therefore composes with any of these estimators without modifying their sampling distributions, weights, and accuracy guarantees, and contributes*orthogonal acceleration*by collapsing coalitions that are equivalent under the relational constraints \(Section[3](https://arxiv.org/html/2608.11508#S3)\)\. The most directly comparable approach is that of[55](https://arxiv.org/html/2608.11508#bib.bib32), which likewise reduce the coalition space via equivalence classes, but using structural causal models that require explicit causal assumptions and intervention semantics;RelShapderives its equivalence structure from declared schema constraints and observed FDs in the data, with no causal assumption required\.

## Appendix DDetails about relational constraints

### D\.1Data\-level relational constraints

#### Discovered functional dependencies

For anyL⊆FL\\subseteq Fand attributea∉La\\notin L, let𝒟/L\\mathcal\{D\}/Ldenote the partition of𝒟\\mathcal\{D\}induced by equality onLL\. We say thatL→aL\\rightarrow aholds*exactly*in𝒟\\mathcal\{D\}if, for every equivalence classC∈𝒟/LC\\in\\mathcal\{D\}/L, attributeaatakes at most one distinct value withinCC:

∀C∈𝒟/L,\|DISTINCTa​\(C\)\|≤1,\\forall\\,C\\in\\mathcal\{D\}/L,\\;\\bigl\|\\mathrm\{DISTINCT\}\_\{a\}\(C\)\\bigr\|\\leq 1,whereDISTINCTa​\(C\)\\mathrm\{DISTINCT\}\_\{a\}\(C\)denotes the set of distinct values of attributeaawithin groupCC\.

We restrict the left\-hand side to at most a user\-specified bound—default22, except for UW\-CSE \(33\)—and consider only single\-attribute right\-hand sides; multi\-attribute right\-hand sides can be derived via Armstrong’s axioms\([3](https://arxiv.org/html/2608.11508#bib.bib16)\)during background data selection \(Section[3\.2](https://arxiv.org/html/2608.11508#S3.SS2)\)\. We retain only minimal FDs: for a fixedaa, ifL→aL\\rightarrow aholds and there existsL′⊂LL^\{\\prime\}\\subset Lsuch thatL′→aL^\{\\prime\}\\rightarrow aalso holds, thenL→aL\\rightarrow ais discarded\. FDs discovered at this stage may overlap with those extracted at the schema and query levels; we retain all and let the user decide which levels to include\.

##### Approximate FDs\.

To tolerate limited violations, we additionally support approximate FDs\. For a candidate pair\(L,a\)\(L,a\), the approximation error is

err⁡\(L→a\)=\|\{C∈𝒟/L\|\|DISTINCTa​\(C\)\|\>1\}\|\|𝒟/L\|\.\\mathrm\{err\}\(L\\rightarrow a\)=\\frac\{\\bigl\|\\bigl\\\{C\\in\\mathcal\{D\}/L\\;\\big\|\\;\\bigl\|\\mathrm\{DISTINCT\}\_\{a\}\(C\)\\bigr\|\>1\\bigr\\\}\\bigr\|\}\{\|\\mathcal\{D\}/L\|\}\.We recordL→aL\\rightarrow aas an approximate FD iferr⁡\(L→a\)≤ε\\mathrm\{err\}\(L\\rightarrow a\)\\leq\\varepsilon, whereε\\varepsilonis a user\-defined tolerance threshold\. While our implementation supports approximate FDs, we restrict all experiments to exact FDs\.

#### Conditional domain rules

For each discovered FDA→BA\\rightarrow Bwheredom⁡\(B\)\\mathrm\{dom\}\(B\)has bounded cardinality \(at most a user\-defined threshold, default2020\), we iterate over valuess∈dom⁡\(B\)s\\in\\mathrm\{dom\}\(B\)and construct implications of the form

\(B=s\)⇒φ⁡\(A\),\(B=s\)\\Rightarrow\\varphi\(A\),whereφ⁡\(A\)\\varphi\(A\)is a domain restriction onAAestimated from the tuples in𝒟\\mathcal\{D\}satisfyingB=sB=s\. Two cases arise:

- •CategoricalAA\.φ⁡\(A\)\\varphi\(A\)restrictsAAto the set of distinct values co\-occurring withB=sB=sin the data\.
- •ContinuousAA\.φ⁡\(A\)\\varphi\(A\)restrictsAAto an empirical interval\[ℓs,us\]\[\\ell\_\{s\},u\_\{s\}\], whereℓs\\ell\_\{s\}andusu\_\{s\}are computed either from the minimum and maximum values or from user\-specified lower and upper quantiles to reduce sensitivity to outliers\.

For example, from an FDage→life\_stage\\texttt\{age\}\\rightarrow\\texttt\{life\\\_stage\}, suppose that the observed domain oflife\_stagein𝒟\\mathcal\{D\}isdom⁡\(life\_stage\)=\{young,middle,older\}\\mathrm\{dom\}\(\\texttt\{life\\\_stage\}\)=\\\{\\texttt\{young\},\\texttt\{middle\},\\texttt\{older\}\\\}\. For eachs∈dom⁡\(life\_stage\)s\\in\\mathrm\{dom\}\(\\texttt\{life\\\_stage\}\), we construct

\(life\_stage=s\)⇒\(ℓs≤age≤us\),\(\\texttt\{life\\\_stage\}=s\)\\Rightarrow\\bigl\(\\ell\_\{s\}\\leq\\texttt\{age\}\\leq u\_\{s\}\\bigr\),whereℓs\\ell\_\{s\}andusu\_\{s\}are estimated empirically from tuples in𝒟\\mathcal\{D\}withlife\_stage=s\\texttt\{life\\\_stage\}=s\.

#### Denial constraints

We identify denial constraints via cycles in the exact FD set\. For a set of attributes\{A,B,C\}\\\{A,B,C\\\}, ifA→BA\\rightarrow B,B→CB\\rightarrow C, andC→AC\\rightarrow Aall hold in𝒟\\mathcal\{D\}, the attributes are mutually determined and form a cyclic dependency\. For each cycle, we test for two characteristic patterns:

- •Scaled one\-hot\.Each entry takes values in\{0,κ\}\\\{0,\\kappa\\\}for someκ∈ℤ\>0\\kappa\\in\\mathbb\{Z\}\_\{\>0\}, and in every tuple at most one column in the set is nonzero\.
- •nn\-ary exclusive or \(XOR\)\.All entries are in\{0,1\}\\\{0,1\\\}, and the sum over thecccolumns has a fixed parity modulo22\.

Caveat\.A categorical variable could be manually one\-hot encoded by the user to avoid imposing an artificial ordinal structure \(e\.g\., encoding categories as 1, 2, 3\) on inherently unordered categories\. Suppose that the model is trained directly on these columns without integrating the preprocessing step into a pipeline usingColumnTransformerfrom thescikit\-learnpackage\. In this case, Shapley value computations without background data selection in RelShap may produce infeasible inputs, sinceffrefers only to the prediction model and does not include the preprocessing transformation\. For example, under the standard Kernel SHAP procedure\([34](https://arxiv.org/html/2608.11508#bib.bib6)\), if we explain an instance withgender\_male=1\\texttt\{gender\\\_male\}=1and consider a female background data point, the completed input becomes\(\(gender\_male,gender\_female,gender\_nonbinary𝙾𝙿𝙴𝙽\)=\(1,1,0\)\)=\(1,1,0\), which does not correspond to any validgendercategory\. Such combinations violate the implicit one\-hot constraint but are not prevented by conventional SHAP implementations\. This motivates reflecting relational constraints, especially denial constraints, during background data selection\.

### D\.2On the choice of reference data

We first clarify that including test data in FD discovery or lookup table \(LUT\) construction does not lead to a data leakage\. These steps are performed solely during the Shapley value computation and are independent of model training\. Referencing test data in the post\-hoc explanation phase does not alter the trained model parameters or influence predictive performance\.

Second, the choice of reference data itself has negligible impact when the training and full data distributions remain aligned\. Prior work such as Fool SHAP\([31](https://arxiv.org/html/2608.11508#bib.bib17)\)shows that SHAP explanations can be substantially distorted when the background data is adversarially manipulated or heavily skewed\. Thus, the key issue is not which reference dataset is selected \-DtrainD\_\{\\text\{train\}\}orDD\- but whether the reference distribution exhibits substantial shift from the model’s training distribution\. In this work, we do not consider significant distributional shifts, and thus such choice does not materially affect the explanations and is treated as a design choice\.

Existing approaches including Kernel SHAP\([34](https://arxiv.org/html/2608.11508#bib.bib6)\)and the conditional approach\([1](https://arxiv.org/html/2608.11508#bib.bib8)\), typically use onlyDtrainD\_\{\\mathrm\{train\}\}as the background data\. While the intention is to respect the training data distribution on which the model was fitted, explanations are ultimately evaluated on test instances\. Consequently, absent features are filled using reference data points solely fromDtrainD\_\{\\mathrm\{train\}\}, which may introduce unrealistic or distributionally mismatched combinations, making such replacements semantically ambiguous\.

Table[3](https://arxiv.org/html/2608.11508#A4.T3)summarizes the four possible combinations of these choices and their potential implications, which may or may not arise in practice depending on the specific configuration\. In our experiments, we use𝒟\\mathcal\{D\}for discovery and𝒟train\\mathcal\{D\}\_\{\\mathrm\{train\}\}for LUT construction by default\. We evaluate each combination along three properties:*Mismatch*indicates whether the discovered relational constraints may not be realizable using values available in the LUT, potentially yielding invalid or undefined instantiations during background or coalition construction for test data points\. It occurs only whenDiscovery⊈LUT\\mathrm\{Discovery\}\\nsubseteq\\mathrm\{LUT\}\.*Hit*indicates whether all values required to instantiate missing features of a test instance are present in the LUT, so that background data points can be constructed without failure\. In particular, this is guaranteed when the LUT is constructed from the full dataset𝒟\\mathcal\{D\}\.*Test*indicates whether test data are used to construct either the discovered constraints or the LUT\.

Table 3:Four possible combinations of discovery data for data\-driven constraint extraction and lookup table \(LUT\) for background data selection, evaluated in terms of possible mismatch, hit \(coverage\), and the use of test data\. ✓ indicates that the corresponding phenomenon may occur, while ✗ denotes that it cannot occur\. For mismatch and test, non\-occurrence is preferable, whereas for hit, occurrence is desirable\.Discovery–LUTMismatchHitTest𝒟train\\mathcal\{D\}\_\{\\mathrm\{train\}\}–𝒟train\\mathcal\{D\}\_\{\\mathrm\{train\}\}✗✗✗𝒟train\\mathcal\{D\}\_\{\\mathrm\{train\}\}–𝒟\\mathcal\{D\}✗✓✓𝒟\\mathcal\{D\}–𝒟train\\mathcal\{D\}\_\{\\mathrm\{train\}\}✓✓✓𝒟\\mathcal\{D\}–𝒟\\mathcal\{D\}✗✓✓

## Appendix EAdditional mathematical details

###### Definition 3\(Σ\\Sigma\-coalition equivalence\)\.

Under the relationally consistent background semantics in Def\.[1](https://arxiv.org/html/2608.11508#Thmdefinition1), we define an equivalence relation over coalitions\. GivenΣ\\Sigmaand a feature of interesti∈Fi\\in F, for any coalitionsS,S′⊆F∖\{i\}S,S^\{\\prime\}\\subseteq F\\setminus\\\{i\\\},SSandS′S^\{\\prime\}are*Σ\\Sigma\-equivalent*, i\.e\.,S∼ΣS′,S\\sim\_\{\\Sigma\}S^\{\\prime\},if they induce the same set of relationally valid completions underΣ\\Sigma\. Formally,

\{𝐱~​\(S,𝐳F∖S\)\|𝐱~​\(S,𝐳F∖S\)⊧Σ\}=\{𝐱~​\(S′,𝐳F∖S′\)\|𝐱~​\(S′,𝐳F∖S′\)⊧Σ\}\.\\bigl\\\{\\tilde\{\\mathbf\{x\}\}\(S,\\mathbf\{z\}\_\{F\\setminus S\}\)\\,\\big\|\\,\\tilde\{\\mathbf\{x\}\}\(S,\\mathbf\{z\}\_\{F\\setminus S\}\)\\models\\Sigma\\bigr\\\}=\\bigl\\\{\\tilde\{\\mathbf\{x\}\}\(S^\{\\prime\},\\mathbf\{z\}\_\{F\\setminus S^\{\\prime\}\}\)\\,\\big\|\\,\\tilde\{\\mathbf\{x\}\}\(S^\{\\prime\},\\mathbf\{z\}\_\{F\\setminus S^\{\\prime\}\}\)\\models\\Sigma\\bigr\\\}\.

###### Definition 4\(Σ\\Sigma\-coalition equivalence class\)\.

Following Def\.[3](https://arxiv.org/html/2608.11508#Thmdefinition3), for any coalitionS⊆F∖\{i\}S\\subseteq F\\setminus\\\{i\\\}, its*Σ\\Sigma\-equivalence class*is defined as:

\[S\]Σ=\{T⊆F∖\{i\}∣T∼ΣS\}\.\[S\]\_\{\\Sigma\}=\\\{T\\subseteq F\\setminus\\\{i\\\}\\mid T\\sim\_\{\\Sigma\}S\\\}\.

###### Definition 5\(Σ\\Sigma\-coalition space\)\.

*Σ\\Sigma\-coalition space*is the quotient space of the original coalition space\{S⊆F∖\{i\}\}\\\{S\\subseteq F\\setminus\\\{i\\\}\\\}under the equivalence relation∼Σ\\sim\_\{\\Sigma\}, which collapses coalitions that are indistinguishable underΣ\\Sigma\. Formally,

𝒞Σ=\{S⊆F∖\{i\}\}/∼Σ=\{\[S\]Σ∣S⊆F∖\{i\}\}\.\\mathcal\{C\}\_\{\\Sigma\}=\\\{S\\subseteq F\\setminus\\\{i\\\}\\\}\\big/\\sim\_\{\\Sigma\}=\\\{\[S\]\_\{\\Sigma\}\\mid S\\subseteq F\\setminus\\\{i\\\}\\\}\.

As noted in Section[3\.2](https://arxiv.org/html/2608.11508#S3.SS2), non\-trivial∼Σ\\sim\_\{\\Sigma\}implies\|𝒞Σ\|<2\|F\|−1\|\\mathcal\{C\}\_\{\\Sigma\}\|<2^\{\|F\|\-1\}in the deterministic setting, without considering randomness in coalition sampling; see Appendix[F\.2](https://arxiv.org/html/2608.11508#A6.SS2)for the proof\.

## Appendix FProofs

### F\.1Proof of Prop\.[1](https://arxiv.org/html/2608.11508#Thmproposition1)

###### Proof\.

By Def\.[3](https://arxiv.org/html/2608.11508#Thmdefinition3), for anyS,S′⊆F∖\{i\}S,S^\{\\prime\}\\subseteq F\\setminus\\\{i\\\}withS∼ΣS′S\\sim\_\{\\Sigma\}S^\{\\prime\},f⁡\(𝐱~​\(S,𝐳\)\)=f⁡\(𝐱~​\(S′,𝐳′\)\)f\\\!\\left\(\\tilde\{\\mathbf\{x\}\}\(S,\\mathbf\{z\}\)\\right\)=f\\\!\\left\(\\tilde\{\\mathbf\{x\}\}\(S^\{\\prime\},\\mathbf\{z\}^\{\\prime\}\)\\right\)for all relationally valid completions𝐳,𝐳′\\mathbf\{z\},\\mathbf\{z\}^\{\\prime\}underΣ\\Sigma\. Let\{C1,…,CK\}\\\{C\_\{1\},\\dots,C\_\{K\}\\\}be the partition of\{S⊆F∖\{i\}\}\\\{S\\subseteq F\\setminus\\\{i\\\}\\\}induced by∼Σ\\sim\_\{\\Sigma\}\. Starting from the Shapley value definition and grouping coalitions by theirΣ\\Sigma\-equivalence classes, we obtain:

ϕi\\displaystyle\\phi\_\{i\}=∑k=1K∑S∈Ckw⁡\(S\)​\(f⁡\(𝐱~​\(S∪\{i\},𝐳\)\)−f⁡\(𝐱~​\(S,𝐳\)\)\)\\displaystyle=\\sum\_\{k=1\}^\{K\}\\sum\_\{S\\in C\_\{k\}\}w\(S\)\\,\\Big\(f\(\\tilde\{\\mathbf\{x\}\}\(S\\cup\\\{i\\\},\\mathbf\{z\}\)\)\-f\(\\tilde\{\\mathbf\{x\}\}\(S,\\mathbf\{z\}\)\)\\Big\)=∑k=1K\(∑S∈Ckw⁡\(S\)\)​\(f⁡\(𝐱~​\(S^k∪\{i\},𝐳\)\)−f⁡\(𝐱~​\(S^k,𝐳\)\)\),\\displaystyle=\\sum\_\{k=1\}^\{K\}\\left\(\\sum\_\{S\\in C\_\{k\}\}w\(S\)\\right\)\\Big\(f\(\\tilde\{\\mathbf\{x\}\}\(\\hat\{S\}\_\{k\}\\cup\\\{i\\\},\\mathbf\{z\}\)\)\-f\(\\tilde\{\\mathbf\{x\}\}\(\\hat\{S\}\_\{k\},\\mathbf\{z\}\)\)\\Big\),whereS^k\\hat\{S\}\_\{k\}is any representative ofCkC\_\{k\}\. Since the original Shapley sum can be partitioned according toΣ\\Sigma\-equivalence classes and the inner expression is identical for allS∈CkS\\in C\_\{k\}, the above expression coincides with the Shapley computation over𝒞Σ\\mathcal\{C\}\_\{\\Sigma\}\. ∎

### F\.2Proof of Coalition Space Reduction

Here we prove the claim in Section[3\.2](https://arxiv.org/html/2608.11508#S3.SS2)that non\-trivial∼Σ\\sim\_\{\\Sigma\}implies\|𝒞Σ\|<2\|F\|−1\|\\mathcal\{C\}\_\{\\Sigma\}\|<2^\{\|F\|\-1\}\.

###### Proof\.

The original coalition domain\{S⊆F∖\{i\}\}\\\{S\\subseteq F\\setminus\\\{i\\\}\\\}has cardinality\|\{S⊆F∖\{i\}\}\|=2\|F\|−1\\lvert\\\{S\\subseteq F\\setminus\\\{i\\\}\\\}\\rvert=2^\{\|F\|\-1\}\. TheΣ\\Sigma\-coalition space𝒞Σ\\mathcal\{C\}\_\{\\Sigma\}consists of the∼Σ\\sim\_\{\\Sigma\}\-equivalence classes over this domain, which form a partition; thus each element of the domain belongs to exactly one equivalence class\. If∼Σ\\sim\_\{\\Sigma\}is non\-trivial, then there exist distinctS,S′⊆F∖\{i\}S,S^\{\\prime\}\\subseteq F\\setminus\\\{i\\\}such thatS∼ΣS′S\\sim\_\{\\Sigma\}S^\{\\prime\}\. Hence at least one equivalence class contains at least two elements\. Since the equivalence classes partition the domain, having a block of size at least two implies that the number of blocks is strictly smaller than the number of elements being partitioned\. Therefore,\|𝒞Σ\|<2\|F\|−1\.\\lvert\\mathcal\{C\}\_\{\\Sigma\}\\rvert\\;<\\;2^\{\|F\|\-1\}\.∎

## Appendix GAlgorithms

Algorithm 2CanonicalizeCoal1:

S←\{fj∈F∣mj=1\}S\\leftarrow\\\{f\_\{j\}\\in F\\mid m\_\{j\}=1\\\}
2:if

SSinCanonMapthen

3:

C←CanonMap​\[S\]C\\leftarrow\\textsc\{CanonMap\}\[S\]
4:else

5:

C←FDClosure​\(S\)C\\leftarrow\\textsc\{FDClosure\}\(S\)⊳\\trianglerightAppendix Alg\.[3](https://arxiv.org/html/2608.11508#alg3)

6:

CanonMap​\[S\]←C\\textsc\{CanonMap\}\[S\]\\leftarrow C
7:endif

8:Set

mj←1m\_\{j\}\\leftarrow 1for all

fj∈Cf\_\{j\}\\in C
9:return

mm

Each coalition mask sampled by the base estimator is*canonicalized*: it is expanded to its FD\-closed representative underΣFD\\Sigma\_\{\\mathrm\{FD\}\}, so thatΣ\\Sigma\-equivalent coalitions map to the same canonical mask \(Alg\.[2](https://arxiv.org/html/2608.11508#alg2)\)\. A coalition maskmmis a binary vector over the featuresFF:mj=1m\_\{j\}=1marks featurefjf\_\{j\}as observed \(provided by the base sampler\) andmj=0m\_\{j\}=0marks it as unobserved \(to be completed from the background data points\)\. Alg\.[2](https://arxiv.org/html/2608.11508#alg2)maps each mask to its FD\-closed form by computingFDClosure​\(S\)\\textsc\{FDClosure\}\(S\)\(Appendix Alg\.[3](https://arxiv.org/html/2608.11508#alg3)\), whereS=\{fj∣mj=1\}S=\\\{f\_\{j\}\\mid m\_\{j\}=1\\\}, and setting to11every entry in the closure\. A memoization cacheCanonMapstores computed closures, so each distinct input coalition incurs the closure computation at most once\.

Algorithm 3FDClosure: Canonicalizing a coalition under the Armstrong’s axioms1:Input:coalition feature set

SS
2:Output:FD\-closed coalition

CC
3:

C←SC\\leftarrow S; initialize an empty queue

QQ
4:foreach FD rule

L→rL\\rightarrow rin

ΣFD\\Sigma\_\{\\mathrm\{FD\}\}do

5:

τL→r←\|L∖C\|\\tau\_\{L\\rightarrow r\}\\leftarrow\|L\\setminus C\|⊳\\triangleright\# of unsatisfied LHS attributes

6:if

τL→r=0\\tau\_\{L\\rightarrow r\}=0and

r∉Cr\\notin Cthen

7:

C←C∪\{r\}C\\leftarrow C\\cup\\\{r\\\}; enqueue

rrinto

QQ
8:endif

9:endfor

10:while

QQnot emptydo

11:

attrnew←\\mathrm\{\{attr\}\_\{new\}\}\\leftarrowdequeue from

QQ
12:foreach FD rule

L→rL\\rightarrow rwith

attrnew∈L\\mathrm\{\{attr\}\_\{new\}\}\\in Ldo

13:

τL→r←τL→r−1\\tau\_\{L\\rightarrow r\}\\leftarrow\\tau\_\{L\\rightarrow r\}\-1
14:if

τL→r=0\\tau\_\{L\\rightarrow r\}=0and

r∉Cr\\notin Cthen

15:

C←C∪\{r\}C\\leftarrow C\\cup\\\{r\\\}; enqueue

rrinto

QQ
16:endif

17:endfor

18:endwhile

19:return

CC

In this section, we provide the algorithmic and implementation details\. In Alg\.[3](https://arxiv.org/html/2608.11508#alg3), for each FD ruleL→rL\\rightarrow r, the algorithm maintains a counterτL→r=\|L∖C\|\\tau\_\{L\\rightarrow r\}=\|L\\setminus C\|, which records how many attributes in the left\-hand side \(LHS\) are not yet present in the current closureCC\. When this counter reaches zero, the rule is triggered andrris added toCC\. When a new attributeattrnew\\mathrm\{\{attr\}\_\{new\}\}is added toCC, it is enqueued and used to update only those FD rules whose LHS containsattrnew\\mathrm\{\{attr\}\_\{new\}\}, by decrementing their counters\. This incremental propagation avoids repeatedly scanning all FD rules and yields an efficient computation of the FD closure\. As noted earlier, we restrict the right\-hand side \(RHS\) of each FD to be a single attribute, while allowing the LHS to include up to a user\-specified maximum number of attributes \(default 2\)\.

Algorithm 4BuildHits: Build per\-identifier candidate sets via inverted index1:functionBuildHits\(

D,S,𝐱^,τ,modeD,\\;S,\\;\\hat\{\\mathbf\{x\}\},\\;\\tau,\\;\\mathrm\{mode\}\)

2:

hits←\[\]\\textit\{hits\}\\leftarrow\[\]
3:foreach

id∈D\\texttt\{id\}\\in Ddo

4:

Kid←\{f∈S∣f​determinesid\}K\_\{\\texttt\{id\}\}\\leftarrow\\\{f\\in S\\mid f\\text\{ determines \}\\texttt\{id\}\\\}
5:if

Kid=∅K\_\{\\texttt\{id\}\}=\\emptysetthencontinue

6:endif

7:

𝒞id←⋂f∈Kidℐ⁡\[id\]​\[f\]​\[x^f\]\\mathcal\{C\}\_\{\\texttt\{id\}\}\\leftarrow\\bigcap\_\{f\\in K\_\{\\texttt\{id\}\}\}\\mathcal\{I\}\[\\texttt\{id\}\]\[f\]\[\\hat\{x\}\_\{f\}\]⊳\\trianglerightO\(\|Kid\|\)\(\|K\_\{\\texttt\{id\}\}\|\)

8:ifmode

=Strict=\\textsc\{Strict\}and

0<\|𝒞id\|≤τ0<\|\\mathcal\{C\}\_\{\\texttt\{id\}\}\|\\leq\\tauthen

9:append

\(id,Kid,𝒞id\)\(\\texttt\{id\},\\;K\_\{\\texttt\{id\}\},\\;\\mathcal\{C\}\_\{\\texttt\{id\}\}\)tohits

10:elseifmode

=Relaxed=\\textsc\{Relaxed\}and

\|𝒞id\|\>0\|\\mathcal\{C\}\_\{\\texttt\{id\}\}\|\>0then

11:

Ridconst←R\_\{\\texttt\{id\}\}^\{\\textsf\{const\}\}\\leftarrowfeatures constant across

ℛ​𝒮​\[id\]​\[𝒞id\]\\mathcal\{RS\}\[\\texttt\{id\}\]\[\\mathcal\{C\}\_\{\\texttt\{id\}\}\]
12:append

\(id,Kid,𝒞id,Ridconst\)\(\\texttt\{id\},\\;K\_\{\\texttt\{id\}\},\\;\\mathcal\{C\}\_\{\\texttt\{id\}\},\\;R\_\{\\texttt\{id\}\}^\{\\textsf\{const\}\}\)tohits

13:endif

14:endfor

15:returnhits

16:endfunction

Algorithm 5ApplyByIntersection: Multi\-identifier joint rule application1:functionApplyByIntersection\(

hits,ℛ​𝒮,S,m,ΣFD,τ,mode\\textit\{hits\},\\mathcal\{RS\},S,m,\\Sigma\_\{\\mathrm\{FD\}\},\\;\\tau,\\;\\mathrm\{mode\}\)

2:

𝒫←⋂\(id,…\)∈hitsℛ​𝒮​\[id\]​\[𝒞id\]\\mathcal\{P\}\\leftarrow\\bigcap\_\{\(\\texttt\{id\},\\ldots\)\\,\\in\\,\\textit\{hits\}\}\\mathcal\{RS\}\[\\texttt\{id\}\]\[\\mathcal\{C\}\_\{\\texttt\{id\}\}\]⊳\\trianglerightAlg\.[4](https://arxiv.org/html/2608.11508#alg4)

3:if

𝒫=∅\\mathcal\{P\}=\\emptysetthenreturn

mm
4:endif

5:foreach

\(id,Kid,𝒞id,Ridconst\)∈hits\(\\texttt\{id\},K\_\{\\texttt\{id\}\},\\mathcal\{C\}\_\{\\texttt\{id\}\},R\_\{\\texttt\{id\}\}^\{\\textsf\{const\}\}\)\\in\\textit\{hits\}do

6:foreach

\(L→r\)∈ΣFD\(L\\rightarrow r\)\\in\\Sigma\_\{\\mathrm\{FD\}\}involvingidwith

L⊆SL\\subseteq Sdo

7:if\(mode =Strictand

\|\{id​\(p\)∣p∈𝒫\}\|≤τ\|\\\{\\texttt\{id\}\(p\)\\mid p\\in\\mathcal\{P\}\\\}\|\\leq\\tau\)

8:or\(mode =Relaxedand

rris constant on

𝒫\\mathcal\{P\}\)then

9:

mr←1m\_\{r\}\\leftarrow 1
10:endif

11:endfor

12:endfor

13:return

mm
14:endfunction

Algorithm 6ProvExpand: Dropped\-identifier based local mask expansion1:Input:mask

mm; instance

𝐱\\mathbf\{x\}; dropped identifiers

DD; FD set

ΣFD\\Sigma\_\{\\mathrm\{FD\}\}\(

\|LHS\|≤2\|\\mathrm\{LHS\}\|\\leq 2\); inverted index

ℐ\\mathcal\{I\}; row\-sets

ℛ​𝒮\\mathcal\{RS\}; threshold

τ\\tau; mode

∈\{Strict,Relaxed\}\\in\\\{\\textsc\{Strict\},\\textsc\{Relaxed\}\\\}
2:Output:expanded mask

mm
3:if

\(m,𝐱\)∈cache\(m,\\,\\mathbf\{x\}\)\\in\\textsf\{cache\}thenreturn

cache​\[\(m,𝐱\)\]\\textsf\{cache\}\[\(m,\\,\\mathbf\{x\}\)\]
4:endif

5:

S←\{fj∣mj=1\}S\\leftarrow\\\{f\_\{j\}\\mid m\_\{j\}=1\\\}
6:

𝐱^←Canonicalize​\(𝐱\)\\hat\{\\mathbf\{x\}\}\\leftarrow\\textsc\{Canonicalize\}\(\\mathbf\{x\}\)⊳\\triangleright𝐱^\\hat\{\\mathbf\{x\}\}cached per instance

7:

8:// Stage 1: build per\-identifier candidate sets via inverted index

9:

hits←BuildHits​\(D,S,𝐱^,τ,mode\)\\textit\{hits\}\\leftarrow\\textsc\{BuildHits\}\(D,\\;S,\\;\\hat\{\\mathbf\{x\}\},\\;\\tau,\\;\\mathrm\{mode\}\)
10:

11:// Stage 2: multi\-identifier row intersection

12:if

\|hits\|≥2\|\\textit\{hits\}\|\\geq 2then

13:

m←ApplyByIntersection​\(hits,ℛ​𝒮,S,m,ΣFD,τ,mode\)m\\leftarrow\\textsc\{ApplyByIntersection\}\(\\textit\{hits\},\\mathcal\{RS\},S,m,\\allowbreak\\Sigma\_\{\\mathrm\{FD\}\},\\tau,\\mathrm\{mode\}\)
14:

S←\{fj∣mj=1\}S\\leftarrow\\\{f\_\{j\}\\mid m\_\{j\}=1\\\}
15:endif

16:

17:// Stage 3: per\-identifier rule application \(using updatedSS\)

18:foreach

id∈D\\texttt\{id\}\\in Dwith

0<\|𝒞id\|≤τ0<\|\\mathcal\{C\}\_\{\\texttt\{id\}\}\|\\leq\\taudo

19:foreach

\(L→r\)∈ΣFD\(L\\rightarrow r\)\\in\\Sigma\_\{\\mathrm\{FD\}\}involvingidwith

L⊆SL\\subseteq Sdo

20:

mr←1m\_\{r\}\\leftarrow 1
21:endfor

22:endfor

23:

S←\{fj∣mj=1\}S\\leftarrow\\\{f\_\{j\}\\mid m\_\{j\}=1\\\}
24:

25:// Stage 4: Over\-threshold identifiers \(mode =Relaxedonly\)

26:ifmode

=Relaxed=\\textsc\{Relaxed\}then

27:foreach

id∈D\\texttt\{id\}\\in Ddo

28:

Kid←\{f∈S∣f​determinesid\}K\_\{\\texttt\{id\}\}\\leftarrow\\\{f\\in S\\mid f\\text\{ determines \}\\texttt\{id\}\\\}
29:

𝒞id←⋂f∈Kidℐ⁡\[id\]​\[f\]​\[x^f\]\\mathcal\{C\}\_\{\\texttt\{id\}\}\\leftarrow\\bigcap\_\{f\\in K\_\{\\texttt\{id\}\}\}\\mathcal\{I\}\[\\texttt\{id\}\]\[f\]\[\\hat\{x\}\_\{f\}\]
30:if

\|𝒞id\|\>τ\|\\mathcal\{C\}\_\{\\texttt\{id\}\}\|\>\\tauthen

31:

Ridconst←R\_\{\\texttt\{id\}\}^\{\\textsf\{const\}\}\\leftarrowfeatures constant across

ℛ​𝒮​\[id\]​\[𝒞id\]\\mathcal\{RS\}\[\\texttt\{id\}\]\[\\mathcal\{C\}\_\{\\texttt\{id\}\}\]
32:foreach

\(L→r\)∈ΣFD\(L\\rightarrow r\)\\in\\Sigma\_\{\\mathrm\{FD\}\}involvingidwith

L⊆SL\\subseteq S,

r∈Ridconstr\\in R\_\{\\texttt\{id\}\}^\{\\textsf\{const\}\}do

33:

mr←1m\_\{r\}\\leftarrow 1
34:endfor

35:endif

36:endfor

37:endif

38:

cache​\[\(m,𝐱\)\]←m\\textsf\{cache\}\[\(m,\\,\\mathbf\{x\}\)\]\\leftarrow m
39:return

mm

Algorithm 7ICRepair: Repairing input data points under integrity constraints \(domain and denial constraints\)1:foreach input data point

𝐱\\mathbf\{x\}do

2:

𝐱fixed←\{xj∣mj=1\}\\mathbf\{x\}\_\{\\mathrm\{fixed\}\}\\leftarrow\\\{x\_\{j\}\\mid m\_\{j\}=1\\\}⊳\\trianglerightfixed \(do not modify\)

3:

𝐱repair←\{xj∣mj=0\}\\mathbf\{x\}\_\{\\mathrm\{repair\}\}\\leftarrow\\\{x\_\{j\}\\mid m\_\{j\}=0\\\}⊳\\trianglerightrepairable

4:foreach rule

\(ℓ⇒r\)∈Σdom\(\\ell\\Rightarrow r\)\\in\\Sigma\_\{\\mathrm\{dom\}\}do

5:if

𝐱repair\\mathbf\{x\}\_\{\\mathrm\{repair\}\}satisfies

ℓ\\ellbut violates

rrthen

6:modify

𝐱repair\\mathbf\{x\}\_\{\\mathrm\{repair\}\}to satisfy

rr⊳\\trianglerightpolicy\-dependent

7:endif

8:endfor

9:foreach

ψ∈Σden\\psi\\in\\Sigma\_\{\\mathrm\{den\}\}do

10:if

𝐱repair\\mathbf\{x\}\_\{\\mathrm\{repair\}\}violates

ψ\\psithen

11:modify only

𝐱repair\\mathbf\{x\}\_\{\\mathrm\{repair\}\}to satisfy

ψ\\psi
12:endif

13:endfor

14:endfor

15:return

𝐱\\mathbf\{x\}

Alg\.[4](https://arxiv.org/html/2608.11508#alg4)resolves candidate entity identifiers for each dropped identifier column using a pre\-built inverted indexℐ​\[id\]​\[f\]​\[v\]→frozenset of id\-values\\mathcal\{I\}\[\\texttt\{id\}\]\[f\]\[v\]\\to\\textit\{frozenset of id\-values\}, requiringO⁡\(∑id∈D\|Kid\|\)O\\\!\\left\(\\sum\_\{\\texttt\{id\}\\in D\}\|K\_\{\\texttt\{id\}\}\|\\right\)frozenset intersection operations per coalition \(covering both single and composite keys on the LHS\), and avoiding any per\-coalition scan or groupby operation over the reference data\. Alg\.[5](https://arxiv.org/html/2608.11508#alg5)handles the case where two or more identifiers are simultaneously active\. It intersects pre\-built row\-index setsℛ​𝒮\\mathcal\{RS\}\(from Alg\.[4](https://arxiv.org/html/2608.11508#alg4)\) across all active identifiers to obtain the jointly consistent row set𝒫\\mathcal\{P\}, and applies FD rules whose conclusions are consistent within𝒫\\mathcal\{P\}\. After callingBuildHitsandApplyByIntersection, Alg\.[6](https://arxiv.org/html/2608.11508#alg6)applies FD rules per identifier using the updatedSS, and if under*Relaxed*mode, it additionally activates features that are constant across over\-threshold entity groups\. The result for each \(mask, instance\) pair is cached to avoid recomputation across the many coalitions that share the same pattern\. Alg\.[7](https://arxiv.org/html/2608.11508#alg7)only repairs values in the absent feature coordinates \(mj=0m\_\{j\}=0\) so that the constructed inputs satisfyΣdom∪Σden\\Sigma\_\{\\mathrm\{dom\}\}\\cup\\Sigma\_\{\\mathrm\{den\}\}under the chosen repair policy\. For numeric constraints, we consider the following three repair policies:

Minimal edit \(projection\)\.The value is projected to the nearest feasible point within the allowed interval\. For example, under

\{life\_stage=middle\}⇒18≤age≤64,\\\{\\texttt\{life\\\_stage\}=\\texttt\{middle\}\\\}\\Rightarrow 18\\leq\\texttt\{age\}\\leq 64,if an instance haslife\_stage=middlebut hasage=16\\texttt\{age\}=16, and theageattribute is repairable \(i\.e\.,mj=0m\_\{j\}=0\), the value is minimally adjusted to the nearest valid boundary, namelyage=18\\texttt\{age\}=18, thereby enforcing the smallest possible modification\.

Random feasible resampling\.A new value is sampled uniformly at random from feasible values observed in the lookup table \(reference data\), subject to satisfying the constraint\. In the above example, any value appearing in the reference table within the range\[18,64\]\[18,\\,64\]may be selected\.

Distance\-weighted random resampling\.A new feasible value is sampled from the reference table with probability proportional to a distance\-based weight, so that values closer to the original value are more likely to be selected\. In the above example, values such as 18 or 19 are more likely than distant values such as 60\. Letoobe the original value and let𝒱=\{v1,…,vK\}\\mathcal\{V\}=\\\{v\_\{1\},\\ldots,v\_\{K\}\\\}be the set of feasible values in the lookup table\. Definedk=\|vk−o\|d\_\{k\}=\|v\_\{k\}\-o\|andwk=11\+dkw\_\{k\}=\\frac\{1\}\{1\+d\_\{k\}\}, and samplevkv\_\{k\}with probabilityPr\[v=vk\]=wk∑j=1Kwj\.\\Pr\[v=v\_\{k\}\]=\\frac\{w\_\{k\}\}\{\\sum\_\{j=1\}^\{K\}w\_\{j\}\}\.

For categorical constraints including denial constraints, there is typically no natural notion of distance\. For example, under a constraint of the form

\{region=‘EU’\}⇒currency∈\{EUR,CHF,GBP\}\\\{\\texttt\{region\}=\\texttt\{\`EU'\}\\\}\\Rightarrow\\texttt\{currency\}\\in\\\{\\texttt\{EUR\},\\texttt\{CHF\},\\texttt\{GBP\}\\\}or

gender\_male,\_female,\_nonbinary\\displaystyle\\texttt\{gender\\\_male\},\\texttt\{\\\_female\},\\texttt\{\\\_nonbinary\}∈\{0,1\},\\displaystyle\\in\\\{0,1\\\},gender\_male\+\_female\+\_nonbinary\\displaystyle\\texttt\{gender\\\_male\}\+\\texttt\{\\\_female\}\+\\texttt\{\\\_nonbinary\}=1\.\\displaystyle=1\.
a feasible category is selected uniformly at random from the admissible values observed in the reference data\.

Furthermore, in the implementation, Kernel SHAP internally represents coalitions using masks defined only over varying features, i\.e\., features whose values can differ from the instance under the background distribution\. RelShap follows the same convention by first identifying such varying features and operating on the corresponding varying feature masks before applying relational canonicalization and refinement\. In addition, throughout RelShap, masks are encoded as compact bit masks to support fast canonicalization, memoization, and lookup\.

## Appendix HClosure system and lattice induced by functional dependencies

### H\.1Closure system

### H\.2Lattice induced by functional dependencies

###### Lemma 1\(Structure of𝒞Σ\\mathcal\{C\}\_\{\\Sigma\}\([14](https://arxiv.org/html/2608.11508#bib.bib28), Thm\. 3\.1\)\)\.

𝒞Σ\\mathcal\{C\}\_\{\\Sigma\}can be identified with the family ofΣ\\Sigma\-closed sets as:

𝒞Σ=2F∖\{i\}∖⋃L→R∈ΣFD,r∈R∖L\[L,\(F∖\{i\}\)∖\{r\}\],\\mathcal\{C\}\_\{\\Sigma\}=2^\{F\\setminus\\\{i\\\}\}\\setminus\\bigcup\_\{L\\to R\\in\\Sigma\_\{\\mathrm\{FD\}\},\\,r\\in R\\setminus L\}\[L,\\;\(F\\setminus\\\{i\\\}\)\\setminus\\\{r\\\}\],where​\[L,\(F∖\{i\}\)∖\{r\}\]=\{S⊆F∖\{i\}∣L⊆S⊆\(F∖\{i\}\)∖\{r\}\}\.\\text\{where\}\\;\[L,\\;\(F\\setminus\\\{i\\\}\)\\setminus\\\{r\\\}\]=\\\{\\,S\\subseteq F\\setminus\\\{i\\\}\\mid L\\subseteq S\\subseteq\(F\\setminus\\\{i\\\}\)\\setminus\\\{r\\\}\\,\\\}\.

Intuitively, for each FDL→RL\\to R, any set that containsLLbut omits some attributer∈Rr\\in Rviolates the dependency and therefore cannot be a closed set\. Several representative FD patterns for which closed\-form expressions or simple counting formulas can be derived are given in Demetrovicset al\.\([14](https://arxiv.org/html/2608.11508#bib.bib28)\)\. These include: single FD; unary chains \(derived from Prop\. 6\.1 in\([14](https://arxiv.org/html/2608.11508#bib.bib28)\);Σ=\{L1→L2,L2→L3,…,Lp−1→Lp\}\\Sigma=\\\{L\_\{1\}\\to L\_\{2\},\\;L\_\{2\}\\to L\_\{3\},\\;\\ldots,\\;L\_\{p\-1\}\\to L\_\{p\}\\\}\); disjoint unary chains \(multiple unary chains on pairwise disjoint attribute sets\); and nested left\-hand sides \(derived from Prop\. 6\.10;Σ=\{L1→r1,L2→r2,…,Lp→rp,\},L1⊆L2⊆⋯⊆Lp\\Sigma=\\\{L\_\{1\}\\to r\_\{1\},L\_\{2\}\\to r\_\{2\},\\ldots,L\_\{p\}\\to r\_\{p\},\\\},\\;L\_\{1\}\\subseteq L\_\{2\}\\subseteq\\cdots\\subseteq L\_\{p\}\)\. Here we restrict our analysis to the single FD case, and letUUdenote the coalition universeF∖\{i\}F\\setminus\\\{i\\\}\. Moreover, following\([13](https://arxiv.org/html/2608.11508#bib.bib48)\), whenΣ\\Sigmadecomposes over attribute\-disjoint blocks, both\|𝒞Σ\|\|\\mathcal\{C\}\_\{\\Sigma\}\|andNC​\(k\)N\_\{C\}\(k\)can be computed by combining the corresponding quantities of each block, reducing the counting problem to smaller independent components\. Specifically, if

Σ=⋃j=1pΣj,𝒞Σ≅∏j=1p𝒞Σj,\\Sigma=\\bigcup\_\{j=1\}^\{p\}\\Sigma\_\{j\},\\;\\;\\mathcal\{C\}\_\{\\Sigma\}\\cong\\prod\_\{j=1\}^\{p\}\\mathcal\{C\}\_\{\\Sigma\_\{j\}\},then

\|𝒞Σ\|=∏j=1p\|𝒞Σj\|,NC​\(k\)=∑k1\+⋯\+kp=k∏j=1pNCj\(j\)​\(kj\),\|\\mathcal\{C\}\_\{\\Sigma\}\|=\\prod\_\{j=1\}^\{p\}\|\\mathcal\{C\}\_\{\\Sigma\_\{j\}\}\|,\\;\\;N\_\{C\}\(k\)=\\sum\_\{\\begin\{subarray\}\{c\}k\_\{1\}\+\\cdots\+k\_\{p\}=k\\end\{subarray\}\}\\prod\_\{j=1\}^\{p\}N^\{\(j\)\}\_\{C\_\{j\}\}\(k\_\{j\}\),whereC=\(C1,…,Cp\)C=\(C\_\{1\},\\dots,C\_\{p\}\)withCj∈𝒞ΣjC\_\{j\}\\in\\mathcal\{C\}\_\{\\Sigma\_\{j\}\}\.

###### Proposition 2\(Single FD\([14](https://arxiv.org/html/2608.11508#bib.bib28), Derived from Thm\. 3\.1\)\)\.

SupposeΣ=\{L→R\}\\Sigma=\\\{L\\to R\\\}, whereL,R⊆UL,R\\subseteq UandL∩R=∅L\\cap R=\\varnothing\. Then the number ofΣ\\Sigma\-closed sets is

\|𝒞Σ\|=2\|U\|−2\|U\|−\|L\|\+2\|U\|−\|L\|−\|R\|\.\|\\mathcal\{C\}\_\{\\Sigma\}\|=2^\{\|U\|\}\-2^\{\\,\|U\|\-\|L\|\}\+2^\{\\,\|U\|\-\|L\|\-\|R\|\}\.
Moreover, for eachC∈𝒞ΣC\\in\\mathcal\{C\}\_\{\\Sigma\},

NC​\(k\)=\{𝟏\{k=\|C\|\},L⊈C,\(\|R\|k−\(\|C\|−\|R\|\)\),L⊆C,N\_\{C\}\(k\)=\\begin\{cases\}\\mathbf\{1\}\\\{k=\|C\|\\\},&L\\nsubseteq C,\\\\\[6\.0pt\] \\displaystyle\\binom\{\|R\|\}\{\\,k\-\(\|C\|\-\|R\|\)\\,\},&L\\subseteq C,\\end\{cases\}where\(ab\)=0\\binom\{a\}\{b\}=0ifb<0b<0orb\>ab\>a\.

###### Proof\.

A setS⊆US\\subseteq UisΣ\\Sigma\-closed iffL⊆S→R⊆S\.L\\subseteq S\\rightarrow R\\subseteq S\.A subset violates the dependency if it containsLLbut omits at least one attribute ofRR\. The number of sets containingLLis2\|U\|−\|L\|2^\{\|U\|\-\|L\|\}, and among them those containingRRare2\|U\|−\|L\|−\|R\|2^\{\|U\|\-\|L\|\-\|R\|\}\. Hence the number of violating sets is2\|U\|−\|L\|−2\|U\|−\|L\|−\|R\|2^\{\|U\|\-\|L\|\}\-2^\{\|U\|\-\|L\|\-\|R\|\}, and subtracting these from2\|U\|2^\{\|U\|\}yields the result\.

IfL⊈CL\\nsubseteq C, then no subset ofCCcan trigger the FD, soclΣ⁡\(S\)=S\\operatorname\{cl\}\_\{\\Sigma\}\(S\)=Sfor allS⊆CS\\subseteq C, and thus the only generator ofCCisS=CS=C\. IfL⊆CL\\subseteq C, then necessarilyR⊆CR\\subseteq CsinceCCis closed, andclΣ⁡\(S\)=C\\operatorname\{cl\}\_\{\\Sigma\}\(S\)=Cholds exactly forS=\(C∖R\)∪TS=\(C\\setminus R\)\\cup TwithT⊆RT\\subseteq R, which gives the binomial count\. ∎

### H\.3Proof of Thm\.[1](https://arxiv.org/html/2608.11508#Thmtheorem1)

###### Proof\.

For eachC∈𝒞ΣC\\in\\mathcal\{C\}\_\{\\Sigma\}, define the indicator random variable

IC=𝟏​\{∃m≤M∣\[S\(m\)\]Σ=C\}\.I\_\{C\}=\\mathbf\{1\}\\\{\\exists\\,m\\leq M\\mid\[S^\{\(m\)\}\]\_\{\\Sigma\}=C\\\}\.Then the number of distinct observed classes isKM=∑C∈𝒞ΣIC\.K\_\{M\}=\\sum\_\{C\\in\\mathcal\{C\}\_\{\\Sigma\}\}I\_\{C\}\.By linearity of expectation,

𝔼⁡\[KM\]=∑C∈𝒞Σ𝔼⁡\[IC\]=∑C∈𝒞ΣPr⁡\(IC=1\)\\mathbb\{E\}\[K\_\{M\}\]=\\sum\_\{C\\in\\mathcal\{C\}\_\{\\Sigma\}\}\\mathbb\{E\}\[I\_\{C\}\]=\\sum\_\{C\\in\\mathcal\{C\}\_\{\\Sigma\}\}\\Pr\(I\_\{C\}=1\)=∑C∈𝒞Σ\(1−\(1−q⁡\(C\)\)M\)\.=\\sum\_\{C\\in\\mathcal\{C\}\_\{\\Sigma\}\}\\left\(1\-\(1\-q\(C\)\)^\{M\}\\right\)\.Conditioning on the coalition size,

q⁡\(C\)=∑k=0\|F\|−1Pr⁡\(\[S\]Σ=C∣\|S\|=k\)​pk\.q\(C\)=\\sum\_\{k=0\}^\{\|F\|\-1\}\\Pr\(\[S\]\_\{\\Sigma\}=C\\mid\|S\|=k\)\\,p\_\{k\}\.For everyC∈𝒞ΣC\\in\\mathcal\{C\}\_\{\\Sigma\}, sincer⁡\(C\)r\(C\)is the size of a minimal generator ofCC, we haveNC​\(k\)=0N\_\{C\}\(k\)=0for allk<r⁡\(C\)k<r\(C\)\. Then the support of the sum can be restricted tok≥r⁡\(C\)k\\geq r\(C\),

q⁡\(C\)=∑k=r⁡\(C\)\|F\|−1pk​NC​\(k\)\(\|F\|−1k\)\.q\(C\)=\\sum\_\{k=r\(C\)\}^\{\|F\|\-1\}p\_\{k\}\\,\\frac\{N\_\{C\}\(k\)\}\{\\binom\{\|F\|\-1\}\{k\}\}\.SinceSSis drawn uniformly conditional on\|S\|=k\|S\|=k,

Pr⁡\(\[S\]Σ=C∣\|S\|=k\)=NC​\(k\)\(\|F\|−1k\)\.\\Pr\(\[S\]\_\{\\Sigma\}=C\\mid\|S\|=k\)=\\frac\{N\_\{C\}\(k\)\}\{\\binom\{\|F\|\-1\}\{k\}\}\.
∎

This is a coupon collector\-type proof\([18](https://arxiv.org/html/2608.11508#bib.bib4);[38](https://arxiv.org/html/2608.11508#bib.bib3)\)\.

### H\.4Estimator\-specific expected runtime reduction

###### Corollary 1\(Monte Carlo coalition estimator\)\.

From Section[C\.2](https://arxiv.org/html/2608.11508#A3.SS2),

pk=1\|F\|,q⁡\(C\)=1\|F\|​∑k=r⁡\(C\)\|F\|−1NC​\(k\)\(\|F\|−1k\)\.p\_\{k\}=\\frac\{1\}\{\|F\|\},\\;\\;q\(C\)=\\frac\{1\}\{\|F\|\}\\sum\_\{k=r\(C\)\}^\{\|F\|\-1\}\\frac\{N\_\{C\}\(k\)\}\{\\binom\{\|F\|\-1\}\{k\}\}\.

###### Corollary 2\(Kernel SHAP\)\.

From Section[C\.1](https://arxiv.org/html/2608.11508#A3.SS1),

pk=1Z\|F\|−1​1k⁡\(\|F\|−1−k\),p\_\{k\}=\\frac\{1\}\{Z\_\{\|F\|\-1\}\}\\frac\{1\}\{k\(\|F\|\-1\-k\)\},fork=1,…,\|F\|−2k=1,\\dots,\|F\|\-2where the normalization factor

Z\|F\|−1=1\|F\|−1​∑t=1\|F\|−2\(1t\+1\|F\|−1−t\)Z\_\{\|F\|\-1\}=\\frac\{1\}\{\|F\|\-1\}\\sum\_\{t=1\}^\{\|F\|\-2\}\\left\(\\frac\{1\}\{t\}\+\\frac\{1\}\{\|F\|\-1\-t\}\\right\)=2\|F\|−1​∑t=1\|F\|−21t=2​H\|F\|−2\|F\|−1\.=\\frac\{2\}\{\|F\|\-1\}\\sum\_\{t=1\}^\{\|F\|\-2\}\\frac\{1\}\{t\}=\\frac\{2H\_\{\|F\|\-2\}\}\{\|F\|\-1\}\.andH\|F\|−2H\_\{\|F\|\-2\}is the harmonic number\.

###### Corollary 3\(Leverage SHAP\)\.

Letmkm\_\{k\}denote the number of sampled coalitions of sizekk, with∑k=0\|F\|−1mk=M\\sum\_\{k=0\}^\{\|F\|\-1\}m\_\{k\}=M\. Hence

pk=mkM,q⁡\(C\)=∑k=r⁡\(C\)\|F\|−1mkM​NC​\(k\)\(\|F\|−1k\),p\_\{k\}=\\frac\{m\_\{k\}\}\{M\},\\;\\;q\(C\)=\\sum\_\{k=r\(C\)\}^\{\|F\|\-1\}\\frac\{m\_\{k\}\}\{M\}\\frac\{N\_\{C\}\(k\)\}\{\\binom\{\|F\|\-1\}\{k\}\},

#### Interpretation

SinceMMis fixed, the degree of runtime reduction is determined byq⁡\(C\)q\(C\)\. If many classesCChave smallq⁡\(C\)q\(C\), new classes tend to appear across samples and few repetitions occur, yieldingRM≈0R\_\{M\}\\approx 0and little runtime reduction\. In contrast, if some classes have largeq⁡\(C\)q\(C\), the same classes are repeatedly sampled and the projection merges these repetitions, increasingRMR\_\{M\}\.

The probabilityq⁡\(C\)q\(C\)is structurally determined by the interaction between the coalition\-size distributionpkp\_\{k\}and the collapse countsNC​\(k\)N\_\{C\}\(k\)\. Herepkp\_\{k\}describes how frequently coalitions of sizekkare sampled by the estimator, whileNC​\(k\)N\_\{C\}\(k\)counts how many coalitions of sizekkcollapse to the same closure classCC\. Therefore, ifpkp\_\{k\}concentrates probability mass on coalition sizes whereNC​\(k\)N\_\{C\}\(k\)is large, the resultingq⁡\(C\)q\(C\)becomes large and the same classes are repeatedly sampled, leading to greater runtime reduction\. Conversely, ifpkp\_\{k\}spreads probability mass broadly across sizes orNC​\(k\)N\_\{C\}\(k\)remains small across levels, thenq⁡\(C\)q\(C\)stays small and new classes continue to appear, resulting in little runtime reduction\.

Consider Example[1](https://arxiv.org/html/2608.11508#Thmexample1)with the discovered FD𝚊𝚐𝚎→𝚕𝚒𝚏𝚎​\_​𝚜𝚝𝚊𝚐𝚎\\mathtt\{age\}\\to\\mathtt\{life\\\_stage\}over\{𝚊𝚐𝚎,𝚕𝚒𝚏𝚎​\_​𝚜𝚝𝚊𝚐𝚎,𝚎𝚖𝚙𝚕,𝚝𝚘𝚝𝚊𝚕​\_​𝚊𝚖𝚝\}\\\{\\mathtt\{age\},\\mathtt\{life\\\_stage\},\\allowbreak\\mathtt\{empl\},\\allowbreak\\mathtt\{total\\\_amt\}\\\}\. Without RelShap, the base sampler treats all24=162^\{4\}=16coalitions as distinct\. Under quotient\-space projection, any coalition containing𝚊𝚐𝚎\\mathtt\{age\}is expanded to also include𝚕𝚒𝚏𝚎​\_​𝚜𝚝𝚊𝚐𝚎\\mathtt\{life\\\_stage\}, so\{𝚊𝚐𝚎\}\\\{\\mathtt\{age\}\\\}and\{𝚊𝚐𝚎,𝚕𝚒𝚏𝚎​\_​𝚜𝚝𝚊𝚐𝚎\}\\\{\\mathtt\{age\},\\mathtt\{life\\\_stage\}\\\}collapse to the same equivalence class, as do\{𝚊𝚐𝚎,𝚎𝚖𝚙𝚕\}\\\{\\mathtt\{age\},\\mathtt\{empl\}\\\}and\{𝚊𝚐𝚎,𝚕𝚒𝚏𝚎​\_​𝚜𝚝𝚊𝚐𝚎,𝚎𝚖𝚙𝚕\}\\\{\\mathtt\{age\},\\mathtt\{life\\\_stage\},\\mathtt\{empl\}\\\}, and so on\. The effective number of distinct classes\|𝒞Σ\|\|\\mathcal\{C\}\_\{\\Sigma\}\|drops from1616to1212\(see Appendix Prop\.[2](https://arxiv.org/html/2608.11508#Thmproposition2)\), and any duplicate draw reuses the cached evaluation\. Thm\.[1](https://arxiv.org/html/2608.11508#Thmtheorem1)generalizes this:q⁡\(C\)q\(C\)measures how likely a sampled coalition is to land in classCC, andRMR\_\{M\}quantifies the expected fraction of redundant coalition evaluations eliminated by quotient projection, as a function of the sampler’s size distributionpkp\_\{k\}and the FD\-induced collapse countsNC​\(k\)N\_\{C\}\(k\)\.

The decomposition admits a combinatorial interpretation: for eachC∈𝒞ΣC\\in\\mathcal\{C\}\_\{\\Sigma\},NC​\(k\)N\_\{C\}\(k\)counts the number of size\-kkcoalitions whose closure generatesCC\(i\.e\., size\-kkgenerators ofCC\), andq⁡\(C\)q\(C\)aggregates these counts weighted by the sampler’s size distributionpkp\_\{k\}\. The collapse countsNC​\(k\)N\_\{C\}\(k\)depend on the FD structure ofΣFD\\Sigma\_\{\\mathrm\{FD\}\}; representative cases are given in Appendix[H\.2](https://arxiv.org/html/2608.11508#A8.SS2)\. Intuitively, FDs with small left\-hand sides induce equivalence classes with small rankr⁡\(C\)r\(C\), so that many coalitions collapse to the same class, yielding largeNC​\(k\)N\_\{C\}\(k\)at small sizes\. Runtime reduction therefore emerges from the interaction between the estimator’s size distribution and the FD\-induced collapse structure:

- •*Kernel SHAP*places larger probability mass on extreme \(small and large\) coalition sizes\. Since FDs in practice tend to have small left\-hand sides, the resulting classes have smallr⁡\(C\)r\(C\)and largeNC​\(k\)N\_\{C\}\(k\)for smallkk, precisely the sizes Kernel SHAP oversamples\. The runtime improvement is therefore amplified whenΣFD\\Sigma\_\{\\mathrm\{FD\}\}contains many low\-arity dependencies\.
- •*Monte Carlo and Leverage SHAP*distribute probability more uniformly across coalition sizes and do not strongly favor any particularkk\. The runtime improvement depends mainly on the overall magnitude of the collapse countsNC​\(k\)N\_\{C\}\(k\)across all sizes; that is, on how many coalitions share the same closure\.

## Appendix IDetails of datasets

For each dataset, we summarize the identifiers that are dropped \(used in provenance\-aware mode\), together with a high\-level dataset overview in Table[4](https://arxiv.org/html/2608.11508#A9.T4)\. For the runtime required to extract schema\-, query\-, and data\-level relational constraints, including the refinement step, over the entire dataset \(TextractT\_\{\\mathrm\{extract\}\}\), all datasets complete within 12 seconds except for SpeedDating and MovieLens 20M\. In both cases, the cost is dominated by data\-driven FD extraction—due to the large number of features \(\|F\|\|F\|\) in SpeedDating and the large number of data points in MovieLens 20M—taking 482\.687s and 98\.922s, respectively\. Table[5](https://arxiv.org/html/2608.11508#A9.T5)lists the corresponding machine learning benchmark sources \(OpenML\([52](https://arxiv.org/html/2608.11508#bib.bib36)\), OpenML\-CC18\([5](https://arxiv.org/html/2608.11508#bib.bib35)\), TabZilla\([36](https://arxiv.org/html/2608.11508#bib.bib33)\), and TabRed\([47](https://arxiv.org/html/2608.11508#bib.bib34)\)\)\. Entity\-relationship diagrams \(ERDs\) with detailed queries and the full set of extracted relational constraints are provided in our supplementary material\. As expected, query execution over the normalized schema preserves the full content of the original dataset\.

Amazon employee access\.This dataset addresses a classification task that predicts whether access to a resource is approved or denied \(ACTION\) based on role of employees and resource\-related information\. Since the original data is provided as a single flattened table, role \(job\) types identified byROLE\_CODEare separated into aRoletable, while employee’s resource access request instances are stored in anEmployeetable\. Each instance is assigned an artificial identifierrow\_idto enable row\-level traceability to the original data\.

Churn\.This dataset targets a binary classification task that predicts customer churn from customer account attributes and call usage statistics\. We apply a normalization to createCustomer,Usage, andPeriodtables:Customerstores customer\-level profile information,Periodenumerates call categories \(DAY, EVE, NIGHT, INTL\), andUsagestores per\-customer and per\-period call usage statistics\. In the final flattened table, period\-specific usage records are pivoted into distinct feature columns for each customer \(e\.g\., total\_day\_minutes, total\_eve\_calls, total\_night\_charge\), reflecting the underlying normalized structure and the functional dependencies it induces\.

Churn Modelling\.This dataset addresses a binary classification task that predicts whether a bank customer leaves the bank \(Exited\) from customer attributes\. The provided flattened table includes two identifier\-like columns,RowNumberandCustomerId, which are typically removed in the downstream machine learning task; however, we use them to normalize the data intoCustomerandProfiletables\. TheCustomertable represents customer entities and stores basic personal information, while theProfiletable represents one record per row identified byRowNumber, linked toCustomerthroughCustomerId, and stores customer financial information\.

German Credit \(credit\-g\)\.This dataset is designed for a binary classification task that predicts whether an applicant has a good or bad credit risk based on demographic and financial attributes\. We apply a semantic normalization that separates applicant\-level attributes into theApplicanttable and credit application–specific attributes into theApplicationtable\. Each record is assigned a synthetic identifierapplication\_id, andApplicationreferencesApplicantthrough a one\-to\-one relationship\.

SpeedDating\.This dataset is designed for a binary classification task that predicts whether two participants ultimately select each other \(whether a match occurs\), based on participant profile \(survey\) information and mutual evaluation data collected from experimental speed dating events\. Although the original data is provided as a single flattened table, the semantics naturally separate participant\-level attributes from encounter\-level attributes\. Accordingly, we normalize the data into three tables:Person,Interaction, andBucketRule\. TablePersonstores attributes that are fixed for a participant \(e\.g\., preference criteria\) TableInteractionstores encounter\-level attributes observed when two participants meet \(e\.g\., ratings of the partner\) Since the columnwavedenotes an independent experimental session, participants can interact only with others within the samewave\. Therefore, all identifiers and joins are performed withinwave\. The relational structure of this dataset inherently induces a self\-join on thePersontable, since each interaction links two persons, identified byself\_idandpartner\_id, within the same entity\. Since the dataset contains both continuous variables and their discretized counterparts \(d\_\*\), we construct aBucketRuletable that records the mapping from each base feature to its bucket label\. At the query\-level, we derive composite features such as age difference and same\-race indicators, which also induce FDs\. Participant–partner identities are recovered by enforcing reciprocal consistency within each wave\. Rows without a unique match are removed, yielding 8,364 rows from the original 8,378, with each interaction represented by two directed rows\.

TPC\-H\.We define a binary classification task at the supplier level that predicts whether a supplier is high risk based on operational performance signals derived from transactional data\. A final table used for ML task contains per\-supplier aggregates summarizing transaction volume, financial performance, delivery behavior, and return behavior, together with supplier account balance and geographic attributes \(nation and region\)\. We derive a binary labelsupplier\_riskby thresholding the late delivery rate and return rate at their 75th percentiles; a supplier is labeled positive if either rate exceeds its threshold\.

UW\-CSE\.We study a multi\-class classification problem that predicts a students program phase \(inPhase\), a commonly studied task on the UW\-CSE dataset, using information about advising and course enrollment\. We derive a student\-centric table in which each row summarizes a students academic context via aggregated statistics, such as the number of advisors and counts of courses at different levels, along with the students years in program\. The identifierp\_idis kept only to index instances and is excluded from the feature set\. The relational design further gives rise to a self\-join onperson, since theadvisedByrelation associates one person with another person in different roles \(student or professor\)\.

MovieLens 20M\.This dataset targets a binary classification task that predicts whether a user gives a movie a high rating\. Since the task is defined over user\-movie pairs, the final table retains bothuserIdandmovieId, and includes movie attributes, genre identifiers, and a representative tag feature\. The specific machine learning task and query are defined by the authors\.

Synthetic\.This is a synthetic relational dataset constructed by the authors for a binary classification task that predicts loan approval as an extension of Example[1](https://arxiv.org/html/2608.11508#Thmexample1)\. It consists of three tables:Applicants,Transactions, andItems, and includes FD:age→\\rightarrowlife\_stageas well as conditional domain constraints betweenregionandcurrency, designed to evaluate how RelShap incorporates conditional domain knowledge and denial constraints \(gender\)\. The final learning table is generated by a query with transaction\-level aggregation \(e\.g\., transaction count and total quantity\) and top item selection; these operations induce FDs, and thus identifiersa\_id\(applicant\) andt\_id\(transaction\) are dropped\.

Table 4:ML: flattened datasets with predefined machine learning tasks \(relational structure is normalized by the authors\)\. DB: relational schemas are given and machine learning tasks are defined by the authors via queries\.\|F\|\|F\|: \# of input features excluding the target\. Train/test splits: scikit\-learn’strain\_test\_splitwith an 8:2 ratio\. Due to memory constraints, for model training, we used 2\.5% of the MovieLens 20M training sets\. For background data selection, we used 400,000 samples for MovieLens 20M, and 2,000 for SpeedDating\.MconvM\_\{\\mathrm\{conv\}\},BB: coalition budget and the chosen background size for convergence,TextractT\_\{\\mathrm\{extract\}\}: runtime \(in seconds\) taken to extract relational constraints over the entire dataset\.TypeDataset\|F\|\|F\|\# data points\# train\# testMconvM\_\{\\mathrm\{conv\}\}BBTextract​\(s​e​c\)T\_\{\\mathrm\{extract\}\}\(sec\)MLAmazon932,76926,2156,554272^\{7\}26,21526\{,\}2157\.139Churn205,0004,0001,000292^\{9\}4,0004\{,\}0006\.961Churn Modelling1110,0008,0002,000252^\{5\}8,0008\{,\}0006\.028German Credit201,000800200282^\{8\}8008006\.513SpeedDating1218,3646,6911,673292^\{9\}2,0002\{,\}000482\.687DBTPC\-H2210,0008,0002,000282^\{8\}8,0008\{,\}00011\.533UW\-CSE714011228262^\{6\}1126\.712MovieLens 20M520,000,2641,600,211400,053232^\{3\}10,00010\{,\}00098\.922Synthetic113,0002,400600262^\{6\}2,4002\{,\}4007\.107Table 5:ML benchmark inclusion for the tabular ML datasets used in our experiments\.DatasetOpenML IDOpenML\-CC18TabZillaTabRedAmazon Employee Access43900✓✓Churn40701✓Churn ModelingN/A✓German Credit31✓✓✓SpeedDating40536✓✓
## Appendix JExperiments

### J\.1Detailed experimental setups

Hardware and reproducibility\.All experiments ran on a machine with an Intel Xeon Platinum 8592\+ CPU \(128 cores, 512 GB RAM\) and an NVIDIA A100 GPU \(80 GB VRAM\) for deep learning models\. Implementation details for reproducibility are in our code repository\. Table[6](https://arxiv.org/html/2608.11508#A10.T6)lists the hyperparameter settings for training predictive models; since Shapley values are post\-hoc and model\-agnostic, we do not optimize predictive performance\. For all experiments, we use three random seeds: 2026, 2027, and 2028\. Software versions, environment configuration, and full implementation details for reproducibility are available in our code repository\. Availability and summary of relational constraints per dataset are summarized in Tables[7](https://arxiv.org/html/2608.11508#A10.T7)and[8](https://arxiv.org/html/2608.11508#A10.T8)\.

Convergence protocol\.For each dataset we identify a unified convergence budgetMconvM\_\{\\mathrm\{conv\}\}at which Shapley estimates stabilize, using Top\-33Jaccard distance as the convergence criterion, after verifying qualitatively similar convergence across estimators\([9](https://arxiv.org/html/2608.11508#bib.bib52);[56](https://arxiv.org/html/2608.11508#bib.bib55)\)\.

Table 6:Hyperparameter settings for each model\.ModelHyperparameter spaceLogistic Regressionregularization parameter∈\[10−4,102\]\\in\[10^\{\-4\},10^\{2\}\]Random Forestnumber of trees∈\{300,500,800\}\\in\\\{300,500,800\\\}maximum tree depth∈\{None,6,10,16\}\\in\\\{\\text\{None\},6,10,16\\\}minimum samples per leaf∈\{1,2,5\}\\in\\\{1,2,5\\\}feature subsampling∈\{sqrt,log2,None\}\\in\\\{\\text\{sqrt\},\\text\{log2\},\\text\{None\}\\\}XGBoostnumber of trees∈\{300,500,800\}\\in\\\{300,500,800\\\}maximum tree depth∈\{3,4,6,8\}\\in\\\{3,4,6,8\\\}learning rate∈\{0\.03,0\.05,0\.1\}\\in\\\{0\.03,0\.05,0\.1\\\}row/feature subsampling∈\{0\.7,0\.8,1\.0\}\\in\\\{0\.7,0\.8,1\.0\\\}minimum child weight∈\{1,3,5\}\\in\\\{1,3,5\\\}L2 regularization strength∈\{0\.5,1\.0,2\.0\}\\in\\\{0\.5,1\.0,2\.0\\\}MLP\-PLRembedding dimension∈\{12,24,32\}\\in\\\{12,24,32\\\}\# of frequencies∈\{8,16,32\}\\in\\\{8,16,32\\\}frequency scale∈\[0\.01,0\.2\]\\in\[0\.01,0\.2\]hidden layer sizes∈\{\(128\),\(256\),\(256,128\),\(512,256\)\}\\in\\\{\(128\),\(256\),\(256,128\),\(512,256\)\\\}dropout rate∈\{0\.0,0\.1,0\.2\}\\in\\\{0\.0,0\.1,0\.2\\\}learning rate∈\{×10−4,10−3,×10−3\}\\in\\\{3\\\!\\times\\\!10^\{\-4\},10^\{\-3\},3\\\!\\times\\\!10^\{\-3\}\\\}weight decay∈\{0,10−5,10−4,10−3\}\\in\\\{0,10^\{\-5\},10^\{\-4\},10^\{\-3\}\\\}Table 7:RelShapconfiguration options\. Each option can be combined with any dataset, model, and coalition estimator\. Availability depends on the constraint types present in the dataset \(Table[8](https://arxiv.org/html/2608.11508#A10.T8)\)\. Options above the mid\-rule change the explanation; the option below it affects only running time\.OptionDescriptionBGBackground data filtered to satisfyΣFD\\Sigma\_\{\\mathrm\{FD\}\}\(Def\.[1](https://arxiv.org/html/2608.11508#Thmdefinition1)\)\.DCsDomain and denial constraints \(Σdom∪Σden\\Sigma\_\{\\mathrm\{dom\}\}\\cup\\Sigma\_\{\\mathrm\{den\}\}\) enforced during background filtering\.Prov, StrictIdentifier\-induced FDs applied when the dropped identifier is uniquely determined from the coalition\.Prov, RelaxedIdentifier\-induced FDs applied when attribute values are constant across candidate identifiers \(subsumes Strict\)\.Quotient \(Q\)Coalitions mapped to FD\-closed canonical form;Σ\\Sigma\-equivalent coalitions deduplicated\.Performance optimization, Shapley values unchanged\(Prop\.[1](https://arxiv.org/html/2608.11508#Thmproposition1)\)\.Table 8:Summary of relational constraints per dataset\.\|F\|\|F\|: number of features\. \# FD: total functional dependencies \(breakdown\(\|LHS\|=1/2\)\(\|\\mathrm\{LHS\}\|\{=\}1/2\)\)\. \# DCs: domain and denial constraints \(lower/upper bounds counted separately\)\. \# Prov: FDs associated with provenance\-aware mode\.Dataset\|F\|\|F\|\# FD\# DCs\# ProvAmazon94 \(4/0\)09Churn2029 \(25/4\)020Churn Modelling1145 \(3/42\)024German Credit206 \(0/6\)020SpeedDating12158 \(55/3\)209231TPC\-H22426 \(106/320\)522UW\-CSE76 \(6/0\)67MovieLens 20M53 \(3/0\)00Synthetic1119 \(2/17\)929
### J\.2Detailed experimental results

#### Semantic effects

Table[9](https://arxiv.org/html/2608.11508#A10.T9)summarizes explanation differences and their deviations from the randomized null baseline across datasets, predictive models, estimators, and comparison modes\. Table[10](https://arxiv.org/html/2608.11508#A10.T10)further provides the per\-dataset breakdown for the comparison modes yielding the largest deviations from the null baseline\.

\(a\)By datasetDatasetTop\-3 Jaccard1−RBO1\-\\mathrm\{RBO\}ΔJaccard\\Delta\_\{\\mathrm\{Jaccard\}\}ΔRBO\\Delta\_\{\\mathrm\{RBO\}\}Amazon0\.106±\\pm0\.2250\.046±\\pm0\.100\-0\.294±\\pm0\.225\-0\.129±\\pm0\.100Churn0\.446±\\pm0\.2830\.171±\\pm0\.1090\.044±\\pm0\.2830\.059±\\pm0\.109Churn Modelling0\.123±\\pm0\.2560\.048±\\pm0\.104\-0\.277±\\pm0\.256\-0\.109±\\pm0\.104German Credit0\.520±\\pm0\.2880\.194±\\pm0\.1160\.118±\\pm0\.2880\.082±\\pm0\.116SpeedDating0\.804±\\pm0\.1890\.245±\\pm0\.1230\.403±\\pm0\.1890\.213±\\pm0\.123TPC\-H0\.612±\\pm0\.3650\.245±\\pm0\.1420\.212±\\pm0\.3650\.140±\\pm0\.142UW\-CSE0\.263±\\pm0\.2430\.121±\\pm0\.113\-0\.129±\\pm0\.243\-0\.072±\\pm0\.113MovieLens 20M0\.479±\\pm0\.1780\.265±\\pm0\.0940\.129±\\pm0\.1780\.050±\\pm0\.094Synthetic0\.500±\\pm0\.2290\.222±\\pm0\.1030\.099±\\pm0\.2290\.065±\\pm0\.103
\(b\)By predictive modelModelTop\-3 Jaccard1−RBO1\-\\mathrm\{RBO\}ΔJaccard\\Delta\_\{\\mathrm\{Jaccard\}\}ΔRBO\\Delta\_\{\\mathrm\{RBO\}\}Logistic Regression0\.425±\\pm0\.3610\.168±\\pm0\.1450\.028±\\pm0\.3610\.033±\\pm0\.167Random Forest0\.445±\\pm0\.3310\.173±\\pm0\.1350\.048±\\pm0\.3310\.039±\\pm0\.156XGBoost0\.436±\\pm0\.3370\.173±\\pm0\.1350\.039±\\pm0\.3360\.039±\\pm0\.158MLP\-PLR0\.434±\\pm0\.3350\.170±\\pm0\.1340\.037±\\pm0\.3350\.035±\\pm0\.156
\(c\)By estimatorEstimatorTop\-3 Jaccard1−RBO1\-\\mathrm\{RBO\}ΔJaccard\\Delta\_\{\\mathrm\{Jaccard\}\}ΔRBO\\Delta\_\{\\mathrm\{RBO\}\}Kernel SHAP0\.301±\\pm0\.2830\.101±\\pm0\.097\-0\.096±\\pm0\.282\-0\.033±\\pm0\.124Leverage SHAP0\.518±\\pm0\.3830\.214±\\pm0\.1550\.121±\\pm0\.3830\.079±\\pm0\.178MC0\.488±\\pm0\.3080\.199±\\pm0\.1240\.090±\\pm0\.3090\.065±\\pm0\.148
\(d\)By comparison mode \(Default vs\. Mode\)ModeTop\-3 Jaccard1−RBO1\-\\mathrm\{RBO\}ΔJaccard\\Delta\_\{\\mathrm\{Jaccard\}\}ΔRBO\\Delta\_\{\\mathrm\{RBO\}\}BG0\.452±\\pm0\.3370\.190±\\pm0\.1460\.057±\\pm0\.3370\.050±\\pm0\.156BG \+ DCs0\.566±\\pm0\.3240\.216±\\pm0\.1280\.168±\\pm0\.3220\.094±\\pm0\.151BG \+ Prov, Strict0\.377±\\pm0\.3560\.142±\\pm0\.139\-0\.023±\\pm0\.3550\.011±\\pm0\.171BG \+ Prov, Relaxed0\.415±\\pm0\.3420\.155±\\pm0\.1300\.015±\\pm0\.3420\.024±\\pm0\.158All0\.430±\\pm0\.3210\.172±\\pm0\.1280\.036±\\pm0\.3220\.032±\\pm0\.150

Table 9:Summary of explanation differences \(Top\-3 Jaccard,1−RBO1\-\\mathrm\{RBO\}\) and deviations from the null baseline \(Δ\\Delta\), aggregated by dataset, predictive model, estimator, and comparison mode\.\(a\)Default vs\. BGDatasetTop\-3 Jaccard1−RBO1\-\\mathrm\{RBO\}ΔJaccard\\Delta\_\{\\mathrm\{Jaccard\}\}ΔRBO\\Delta\_\{\\mathrm\{RBO\}\}Amazon0\.265±0\.3810\.265\\pm 0\.3810\.119±0\.1710\.119\\pm 0\.171−0\.136±0\.381\-0\.136\\pm 0\.381−0\.056±0\.171\-0\.056\\pm 0\.171Churn0\.553±0\.1970\.553\\pm 0\.1970\.214±0\.0780\.214\\pm 0\.0780\.151±0\.1970\.151\\pm 0\.1970\.102±0\.0780\.102\\pm 0\.078Churn Modelling0\.297±0\.4270\.297\\pm 0\.4270\.125±0\.1800\.125\\pm 0\.180−0\.104±0\.427\-0\.104\\pm 0\.427−0\.033±0\.180\-0\.033\\pm 0\.180German Credit0\.391±0\.4170\.391\\pm 0\.4170\.161±0\.1770\.161\\pm 0\.177−0\.011±0\.417\-0\.011\\pm 0\.4170\.049±0\.1770\.049\\pm 0\.177SpeedDating0\.644±0\.2580\.644\\pm 0\.2580\.190±0\.1350\.190\\pm 0\.1350\.243±0\.2580\.243\\pm 0\.2580\.158±0\.1350\.158\\pm 0\.135TPC\-H0\.629±0\.2960\.629\\pm 0\.2960\.250±0\.1110\.250\\pm 0\.1110\.229±0\.2960\.229\\pm 0\.2960\.144±0\.1110\.144\\pm 0\.111UW\-CSE0\.335±0\.2400\.335\\pm 0\.2400\.162±0\.1170\.162\\pm 0\.117−0\.057±0\.240\-0\.057\\pm 0\.240−0\.031±0\.117\-0\.031\\pm 0\.117MovieLens 20M0\.479±0\.1790\.479\\pm 0\.1790\.265±0\.0950\.265\\pm 0\.0950\.129±0\.1790\.129\\pm 0\.1790\.050±0\.0950\.050\\pm 0\.095Synthetic0\.474±0\.3200\.474\\pm 0\.3200\.222±0\.1470\.222\\pm 0\.1470\.073±0\.3200\.073\\pm 0\.3200\.065±0\.1470\.065\\pm 0\.147
\(b\)Default vs\. BG \+ DCsDatasetTop\-3 Jaccard1−RBO1\-\\mathrm\{RBO\}ΔJaccard\\Delta\_\{\\mathrm\{Jaccard\}\}ΔRBO\\Delta\_\{\\mathrm\{RBO\}\}SpeedDating0\.845±0\.1390\.845\\pm 0\.1390\.234±0\.1140\.234\\pm 0\.1140\.444±0\.1390\.444\\pm 0\.1390\.202±0\.1140\.202\\pm 0\.114TPC\-H0\.593±0\.3080\.593\\pm 0\.3080\.238±0\.1130\.238\\pm 0\.1130\.192±0\.3080\.192\\pm 0\.3080\.133±0\.1130\.133\\pm 0\.113UW\-CSE0\.335±0\.2400\.335\\pm 0\.2400\.162±0\.1170\.162\\pm 0\.117−0\.057±0\.240\-0\.057\\pm 0\.240−0\.031±0\.117\-0\.031\\pm 0\.117Synthetic0\.494±0\.3380\.494\\pm 0\.3380\.230±0\.1520\.230\\pm 0\.1520\.093±0\.3380\.093\\pm 0\.3380\.072±0\.1520\.072\\pm 0\.152
\(c\)Default vs\. AllDatasetTop\-3 Jaccard1−RBO1\-\\mathrm\{RBO\}ΔJaccard\\Delta\_\{\\mathrm\{Jaccard\}\}ΔRBO\\Delta\_\{\\mathrm\{RBO\}\}SpeedDating0\.883±0\.1220\.883\\pm 0\.1220\.274±0\.1180\.274\\pm 0\.1180\.482±0\.1220\.482\\pm 0\.1220\.242±0\.1180\.242\\pm 0\.118TPC\-H0\.622±0\.4470\.622\\pm 0\.4470\.247±0\.1780\.247\\pm 0\.1780\.222±0\.4470\.222\\pm 0\.4470\.142±0\.1780\.142\\pm 0\.178UW\-CSE0\.372±0\.2700\.372\\pm 0\.2700\.165±0\.1230\.165\\pm 0\.123−0\.020±0\.270\-0\.020\\pm 0\.270−0\.028±0\.123\-0\.028\\pm 0\.123Synthetic0\.471±0\.1850\.471\\pm 0\.1850\.205±0\.0740\.205\\pm 0\.0740\.070±0\.1850\.070\\pm 0\.1850\.047±0\.0740\.047\\pm 0\.074

Table 10:Dataset\-wise explanation differences for Default vs\. BG, Default vs\. BG \+ DCs, and Default vs\. All\. We report per\-dataset results for the two modes with the largestΔJaccard\\Delta\_\{\\mathrm\{Jaccard\}\}andΔRBO\\Delta\_\{\\mathrm\{RBO\}\}\. Values are mean±\\pmstandard deviation; results for BG \+ DCs and All are shown only when applicable\.Figure 5:Top\-33Jaccard distance between default estimators and RelShap configurations on UW\-CSE dataset\. Values above the shaded region indicate that RelShap induces larger changes than expected under the randomized null baseline\.Figure 6:1−RBO1\-\\mathrm\{RBO\}between default estimators andRelShapconfigurations on German Credit\. Values above the shaded region exceed the randomized null baseline\. This dataset has no domain or denial constraints, so those modes are omitted\.Figure 7:1−RBO1\-\\mathrm\{RBO\}between default estimators and RelShap configurations on UW\-CSE dataset\. Values above the shaded region indicate that RelShap induces larger changes than expected under the randomized null baseline\.Figure 8:Top\-3 Jaccard distance between default estimators and RelShap configurations on German Credit dataset\. Values above the shaded region indicate that RelShap induces larger changes than expected under the randomized null baseline\. Note that German Credit dataset does not contain any domain or denial constraints and therefore the results are not provided\.Figures[5](https://arxiv.org/html/2608.11508#A10.F5)and[6](https://arxiv.org/html/2608.11508#A10.F6)illustrate two complementary regimes\. UW\-CSE is a small database \(DB\) dataset \(\|F\|=7\|F\|\{=\}7\) where we can afford full coalition enumeration \(Mconv=2\|F\|−1M\_\{\\mathrm\{conv\}\}=2^\{\|F\|\-1\}\), providing an exact comparison; German Credit is a medium\-scale ML dataset \(\|F\|=20\|F\|\{=\}20\) with sampled coalitions\. In both cases, severalRelShapconfigurations produce distances that exceed the shaded null\-baseline region, indicating shifts beyond what random perturbation can explain\.

Note that distances do not necessarily increase as more constraint types are added: each configuration changes*which*background points are admissible, and the resulting rankings can move in any direction relative to the default\. On UW\-CSE, for instance, all features are functionally determined by the dropped identifierp\_id, so provenance\-aware mode collapses the background to near\-deterministic completions\. In this setting, the resulting explanation differences from the default sampler, which draws from the small training set \(\|𝒟train\|=112\|\\mathcal\{D\}\_\{\\mathrm\{train\}\}\|=112\), remain at or below the null baseline\. In contrast, on TPC\-H,suppkeyinduces richer cross\-table structure over a larger pool \(\|𝒟train\|=8,000\|\\mathcal\{D\}\_\{\\mathrm\{train\}\}\|=8\{,\}000\), and provenance\-aware mode produces consistently large positiveΔ\\Deltavalues \(Appendix Table[11](https://arxiv.org/html/2608.11508#A10.T11)\)\. The complementary metric pairing—1−RBO1\{\-\}\\mathrm\{RBO\}on UW\-CSE and Top\-33Jaccard on German Credit—is in Appendix Figures[7](https://arxiv.org/html/2608.11508#A10.F7)and[8](https://arxiv.org/html/2608.11508#A10.F8)\.

\(a\) Default vs\. BG \+ Prov

DatasetEst\.Top\-3 Jaccard1−RBO1\-\\mathrm\{RBO\}ΔJaccard\\Delta\_\{\\mathrm\{Jaccard\}\}ΔRBO\\Delta\_\{\\mathrm\{RBO\}\}TPC\-HKer0\.922 / 0\.9140\.376 / 0\.3760\.522 / 0\.5140\.271 / 0\.271MC0\.954 / 0\.9590\.388 / 0\.3760\.553 / 0\.5580\.283 / 0\.270Lev0\.000 / 0\.0000\.000 / 0\.000\-0\.401 / \-0\.401\-0\.105 / \-0\.105UW\-CSEKer0\.018 / 0\.2020\.004 / 0\.054\-0\.374 / \-0\.190\-0\.190 / \-0\.139MC0\.012 / 0\.0060\.004 / 0\.048\-0\.380 / \-0\.386\-0\.189 / \-0\.145Lev0\.021 / 0\.3820\.029 / 0\.153\-0\.371 / \-0\.010\-0\.164 / \-0\.040
\(b\) BG vs\. BG \+ Prov

DatasetEst\.Top\-3 Jaccard1−RBO1\-\\mathrm\{RBO\}ΔJaccard\\Delta\_\{\\mathrm\{Jaccard\}\}ΔRBO\\Delta\_\{\\mathrm\{RBO\}\}TPC\-HKer0\.914 / 0\.9240\.356 / 0\.3610\.513 / 0\.5230\.250 / 0\.255Lev0\.965 / 0\.9650\.369 / 0\.3690\.565 / 0\.5650\.263 / 0\.263MC0\.881 / 0\.8830\.316 / 0\.3100\.480 / 0\.4820\.211 / 0\.205UW\-CSEKer\.0\.018 / 0\.2020\.004 / 0\.054\-0\.374 / \-0\.190\-0\.190 / \-0\.139Lev0\.504 / 0\.3260\.233 / 0\.2230\.112 / \-0\.0660\.040 / 0\.030MC0\.504 / 0\.5000\.224 / 0\.2420\.112 / 0\.1080\.031 / 0\.049

Table 11:Explanation differences for provenance\-aware comparisons on TPC\-H and UW\-CSE with XGBoost\. Each entry is reported as Strict / Relaxed mode\. Est\. denotes Estimator and Ker, MC, and Lev denote Kernel SHAP, Monte Carlo, and Leverage SHAP, respectively\.
#### Computational effects

We measure the relative reduction in runtime per explanation sample as\(Tref−Ttarget\)/Tref×100\(%\)\(T\_\{\\text\{ref\}\}\-T\_\{\\text\{target\}\}\)/T\_\{\\text\{ref\}\}\\times 100\\,\(\\%\), whereTrefT\_\{\\text\{ref\}\}denotes the runtime of the reference method \(Default or RelShap \(BG\)\) andTtargetT\_\{\\text\{target\}\}denotes that of RelShap \(BG/Q\)\. Figure[14](https://arxiv.org/html/2608.11508#A10.F14)presents runtime reduction versus the empirical speedup factor\. Figure[7](https://arxiv.org/html/2608.11508#A10.F7)shows1−RBO1\-\\mathrm\{RBO\}results on the UW\-CSE dataset, and Figure[8](https://arxiv.org/html/2608.11508#A10.F8)shows Top\-3 Jaccard distance on the German Credit dataset, complementing the main text with the opposite pairing\. Figure[9](https://arxiv.org/html/2608.11508#A10.F9)shows pairwise runtime comparisons across all datasets, models, and comparison modes\. Overall, runtime reduction is observed in a large fraction of cases, with Monte Carlo and Leverage SHAP showing particularly strong gains, where reduction occurs in 91\.55% and 84\.72% of cases, respectively, while Kernel SHAP shows a lower rate of 43\.06%\. This pattern indicates that the benefit of quotient space coalition projection in RelShap is estimator\-dependent\.

Figure 9:Runtime comparison between the reference method and RelShap \(BG/Quotient\)\. Each point corresponds to a dataset–model–configuration pair\. Points above the diagonal indicate runtime reduction\.Table 12:Percentage of cases with runtime reduction across estimators and models\.Estimator / ModelDefault vs\. BG/QBG vs\. BG/QKernel SHAP47\.22%42\.59%Monte Carlo95\.24%85\.19%Leverage SHAP81\.48%84\.26%Logistic Regression69\.14%64\.20%Random Forest80\.25%80\.25%XGBoost85\.19%75\.31%MLP\-PLR62\.82%62\.96%Table[15](https://arxiv.org/html/2608.11508#A10.T15)summarizes the frequency of runtime reduction across datasets\. The runtime reduction is consistently observed for Monte Carlo and Leverage SHAP across most datasets, often exceeding 90%\. In contrast, Kernel SHAP shows higher variability, with little to no reduction on some datasets \(e\.g\., German Credit and UW\-CSE\) but strong improvements on others \(e\.g\., SpeedDating and TPC\-H\)\. Building on the analysis in Section[3\.3](https://arxiv.org/html/2608.11508#S3.SS3), we observe that, in general, runtime reduction becomes more pronounced as the total number of FDs increases\. In particular, for Kernel SHAP, roughly the benefit tends to emerge only when there is a sufficiently large number of FDs with\|LHS\|=1\|\{\\mathrm\{LHS\}\}\|=1\(as shown in Table[8](https://arxiv.org/html/2608.11508#A10.T8)\), which is more evident for Kernel SHAP than for the other two estimators\.

\(a\)Kernel SHAP\.\(b\)Monte Carlo\.\(c\)Leverage SHAP\.
Figure 10:Average running time \(sec/sample\) across datasets under XGBoost; y\-axis uses a square root scaling\.Figure[10](https://arxiv.org/html/2608.11508#A10.F10)provides a more detailed view of the actual runtime per test sample across datasets\. Table[12](https://arxiv.org/html/2608.11508#A10.T12)summarizes the percentage of cases exhibiting runtime reduction across estimators and models\. Monte Carlo consistently shows the highest reduction rates \(95\.24% and 85\.19%\), followed by Leverage SHAP, while Kernel SHAP exhibits more moderate gains\. These results are expected as described in Section[3\.3](https://arxiv.org/html/2608.11508#S3.SS3)\. Across models, the variation is relatively small compared to differences across estimators, although Random Forest and XGBoost exhibit slightly higher reduction rates\. This pattern indicates that the benefit of quotient space coalition projection in RelShap is estimator\-dependent\.

Table 13:Running time \(sec/sample\) under XGBoost for datasets without denial constraints \(mean over three seeds\)\. These datasets do not admit the full\-featured configuration \(BG/Q \+ Prov, Relaxed \+ DCs\); see Table[14](https://arxiv.org/html/2608.11508#A10.T14)for datasets with DCs\. When provenance is active, quotient projection deduplicates using both global and provenance\-induced FDs; however, provenance lookups add their own overhead, so BG/Q \+ Prov is not guaranteed to be faster than BG/Q alone\. Dashes \(\-\) indicate inapplicable configurations \(Table[8](https://arxiv.org/html/2608.11508#A10.T8)\)\. See Appendix Figure[10](https://arxiv.org/html/2608.11508#A10.F10)for a visual comparison\. Here, Ker, MC, and Lev denote Kernel SHAP, Monte Carlo, and Leverage SHAP, respectively\. Prov, St/Rel denotes Prov, Strict/Relaxed mode\.AmazonChurnChurn ModellingGerman CreditMovieLens 20MModeKerMCLevKerMCLevKerMCLevKerMCLevKerMCLevDefault60\.38916\.6428\.61224\.4257\.0268\.0841\.5230\.4930\.2410\.7930\.5900\.3211\.3620\.3870\.202BG51\.5990\.0097\.58419\.9773\.1813\.6161\.3460\.0080\.3690\.7590\.5540\.3271\.3090\.1570\.264BG/Q56\.6240\.0097\.36212\.0942\.4942\.2161\.5760\.0060\.3051\.5500\.4850\.2181\.3170\.0820\.117BG \+ Prov, Strict52\.4110\.0057\.83222\.4900\.8655\.0151\.2630\.0040\.2880\.7420\.2200\.255\-\-\-BG/Q \+ Prov, Strict52\.72516\.3608\.73917\.2610\.7827\.1461\.2920\.4980\.2450\.9130\.2600\.306\-\-\-BG \+ Prov, Relaxed55\.0190\.0066\.71521\.2320\.7066\.1821\.2860\.0040\.2900\.7140\.1140\.314\-\-\-BG/Q \+ Prov, Relaxed56\.62616\.1607\.70320\.2600\.7975\.7711\.6260\.4700\.2620\.9730\.1570\.342\-\-\-Table 14:Running time \(sec/sample\) under XGBoost for datasets with denial constraints \(mean over three seeds\)\. The last row shows the full\-featuredRelShapconfiguration\.SpeedDatingTPC\-HUW\-CSESyntheticModeKerMCLevKerMCLevKerMCLevKerMCLevDefault45\.98512\.8177\.4476\.5272\.3831\.2440\.0620\.1190\.0840\.5050\.2120\.119BG45\.40811\.0387\.0986\.4640\.3661\.0940\.0540\.1150\.0780\.5580\.1600\.123BG/Q37\.22710\.0685\.7851\.7770\.1921\.1380\.2710\.0540\.0480\.6220\.1060\.082BG \+ DCs225\.20064\.11920\.9329\.1320\.6512\.6580\.0340\.0190\.0152\.2480\.6850\.628BG/Q \+ DCs244\.80073\.63522\.8202\.9880\.3772\.3640\.0640\.0110\.0122\.5870\.5530\.333BG \+ Prov, Strict38\.5820\.6837\.5307\.4780\.3152\.0010\.0070\.0120\.0100\.5190\.0630\.109BG/Q \+ Prov, Strict36\.9761\.0069\.4916\.1670\.1421\.7250\.0660\.1080\.0760\.4830\.0770\.124BG \+ Prov, Relaxed42\.1150\.73110\.2936\.6600\.1711\.9710\.0080\.0100\.0120\.4690\.0730\.125BG/Q \+ Prov, Relaxed40\.6040\.8729\.0327\.5980\.1821\.7340\.0560\.0720\.0940\.4980\.0830\.145All43\.5583\.23210\.6499\.2390\.2973\.5890\.0350\.0140\.0132\.4810\.4420\.606All/Q42\.1174\.0439\.7522\.6820\.0911\.1970\.4740\.0340\.0492\.5210\.2000\.455Tables[13](https://arxiv.org/html/2608.11508#A10.T13)and[14](https://arxiv.org/html/2608.11508#A10.T14)provide a per\-mode breakdown\. Several patterns emerge\. First, BG alone already reduces runtime for Monte Carlo on several datasets \(e\.g\., Amazon drops from16\.64216\.642to0\.0090\.009sec per sample, and TPC\-H from2\.3832\.383to0\.3660\.366\)\. Adding quotient projection \(BG/Q\) yields further gains, particularly for Kernel SHAP on datasets with rich FD structure: on TPC\-H, Kernel SHAP drops from6\.5276\.527\(Default\) to1\.7771\.777\(BG/Q\), and on Churn from24\.42524\.425to12\.09412\.094\. Second, the benefit is estimator\-dependent: Monte Carlo and Leverage SHAP show consistent reductions across datasets, while Kernel SHAP improves primarily on datasets with many FDs having\|LHS\|=1\|\\mathrm\{LHS\}\|\{=\}1\(Table[8](https://arxiv.org/html/2608.11508#A10.T8)\)\. On datasets with predominantly\|LHS\|=2\|\\mathrm\{LHS\}\|\{=\}2FDs \(e\.g\., German Credit\), Kernel SHAP shows little or no improvement, and BG/Q can even incur slight overhead from the canonicalization step without sufficient deduplication to compensate\. Third, provenance\-aware modes \(BG/Q \+ Prov\) exhibit dataset\-dependent behavior: on TPC\-H, Monte Carlo benefits substantially \(0\.1420\.142sec/sample under Prov, Strict vs\.0\.1920\.192under BG/Q\), while on other datasets the additional provenance lookups can offset the gains from deduplication\. The full\-featured mode \(BG/Q \+ Prov, Relaxed \+ DCs\), available on datasets with all constraint types, shows competitive runtimes: on TPC\-H, Monte Carlo achieves0\.0910\.091sec/sample, a26×26\{\\times\}reduction over Default\. Across models, variation is small compared to differences across estimators, confirming that the runtime benefit is primarily estimator\-driven\. It is noteworthy that since DCs may introduce additional lookup costs and filtering costs, DC and All modes have a probability of slowing down the computations, even with or without Q mode\. Therefore, quotient mode provides runtime benefits, but this does not always happen\. Q can reduce runtime with rich FD structures desirable estimators; otherwise, overhead may dominate\.

Table 15:Percentage of cases showing runtime reduction across datasets and estimators, including Default vs\. RelShap \(BG\) and RelShap \(BG\) vs\. RelShap \(BG/Q\)\. The highest value in each dataset \(row\) is highlighted in bold\.DatasetKernelMCLeverageAmazon33\.33%75\.00%50\.00%Churn87\.50%95\.83%100\.0%Churn Modelling16\.67%91\.67%54\.17%German Credit0\.000%75\.00%91\.67%SpeedDating91\.67%76\.19%79\.17%TPC\-H100\.0%100\.0%79\.17%UW\-CSE0\.000%100\.0%91\.67%MovieLens 20M41\.67%100\.0%100\.0%Synthetic33\.33%95\.83%100\.0%##### Scalability

\(a\)Running time as the number of background data points varies for Churn\.\(b\)Running time as the number of background data points varies for TPC\-H\.\(c\)Running time as the number of coalitions varies for Churn\.\(d\)Running time as the number of coalitions varies for TPC\-H\.
Figure 11:Average running time \(sec/sample\) as the number of background data points varies up to the per\-dataset maximumBBand the number of coalitions varies up to the convergence budgetMconvM\_\{\\mathrm\{conv\}\}in Table[4](https://arxiv.org/html/2608.11508#A9.T4), for Churn and TPC\-H \(log scale on the x\-axis\)\.Figure[11](https://arxiv.org/html/2608.11508#A10.F11)shows running time per sample as the number of background data points \(Churn\) and coalitions \(TPC\-H\) increase\. On Churn \(Figure[11\(a\)](https://arxiv.org/html/2608.11508#A10.F11.sf1)\), all three methods grow with background size, but the gap between Default and BG/Q widens asBBincreases: for Kernel SHAP, BG/Q remains roughly flat while Default grows super\-linearly; for Monte Carlo, BG alone already provides a large reduction that BG/Q maintains; for Leverage SHAP, the separation is moderate but consistent\.

On TPC\-H \(Figure[11\(d\)](https://arxiv.org/html/2608.11508#A10.F11.sf4)\), runtime grows with the coalition budgetMMfor all methods, but BG/Q maintains a substantial gap below Default across the full range for Kernel SHAP and Monte Carlo\. For Leverage SHAP, the three curves are closer together, reflecting the smaller number of collapsible coalitions under this estimator’s sampling distribution\. The complementary pairing in the Appendix confirms these patterns: TPC\-H vs\. background data \(Appendix Figure[11\(b\)](https://arxiv.org/html/2608.11508#A10.F11.sf2)\) shows the same widening gap, with BG/Q providing the largest separation for Kernel SHAP and MC; Churn vs\. coalitions \(Appendix Figure[11\(c\)](https://arxiv.org/html/2608.11508#A10.F11.sf3)\) shows all three curves growing together but with BG/Q consistently below Default, and the gap widening at larger coalition budgets\. Overall, the reduction from BG/Q grows with problem size across both axes, indicating thatRelShapbecomes more effective with larger data and coalition budgets\.

\(a\)Running time as the number of background data points varies for MovieLens\-20M with MLP\-PLR\.\(b\)Running time as the number of coalitions varies for SpeedDating with logistic regression\.
Figure 12:Average running time \(sec/sample\) as the number of background data points and coalitions varies for additional model–dataset pairs\.\(a\)Running time as the number of background data points varies for Churn Modelling with XGBoost under richer provenance settings\.\(b\)Running time as the number of coalitions varies for Churn Modelling with XGBoost under richer provenance settings\.
Figure 13:Average running time \(sec/sample\) as the number of background data points and coalitions varies under richer provenance settings for Churn Modelling with XGBoost\.Additional model–dataset pairs and richer constraint settings exhibit the same overall scaling behavior, although the magnitude of the gain depends on the estimator and the available coalition redundancy\. On MovieLens 20M dataset with MLP\-PLR \(Figure[12\(a\)](https://arxiv.org/html/2608.11508#A10.F12.sf1)\), BG/Q increasingly separates from Default as the background size grows, with particularly large reductions for Monte Carlo and Leverage SHAP and a smaller but clear reduction for Kernel SHAP\. On SpeedDating dataset with logistic regression \(Figure[12\(b\)](https://arxiv.org/html/2608.11508#A10.F12.sf2)\), all configurations grow similarly with the coalition budget, although BG/Q remains consistently below Default at largerMM\. Churn Modelling dataset with XGBoost \(Figure[13](https://arxiv.org/html/2608.11508#A10.F13)\) further shows that richer provenance settings preserve the same scaling trends across both axes: running times increase with background size and coalition budget\. This suggests that enriching the relational semantics does not fundamentally alter the scalability profile: runtime is driven primarily by the estimator, evaluation budget, and the quotient mode, allowing richer constraint\-aware explanations to be incorporated without introducing a qualitatively different scaling behavior\.

##### Alignment with combinatorial analysis

We measure this using the empirical counterpart ofRMR\_\{M\}in Thm\.[1](https://arxiv.org/html/2608.11508#Thmtheorem1),R^Mconv=1−1/S^Mconv\\hat\{R\}\_\{M\_\{\\mathrm\{conv\}\}\}=1\-1/\{\\hat\{S\}\_\{M\_\{\\mathrm\{conv\}\}\}\}whereS^Mconv=1nexplain​∑nexplain1B​∑b=1BMconvKbquot\\hat\{S\}\_\{M\_\{\\mathrm\{conv\}\}\}=\\frac\{1\}\{n\_\{\\text\{explain\}\}\}\\sum\_\{n\_\{\\text\{explain\}\}\}\\frac\{1\}\{B\}\\sum\_\{b=1\}^\{B\}\\frac\{M\_\{\\mathrm\{conv\}\}\}\{K^\{\\text\{quot\}\}\_\{b\}\}andKbquotK^\{\\text\{quot\}\}\_\{b\}is the number of distinct equivalence classes after quotient mode\. Figure[14](https://arxiv.org/html/2608.11508#A10.F14)shows an alignment of real runtime reduction and our combinatorial analysis in Thm\.[1](https://arxiv.org/html/2608.11508#Thmtheorem1)\. This confirms that our analysis reliably predicts*when*reduction will occur, although its exact magnitude remains contingent on the dataset and sampling strategy\.

Figure 14:Runtime reduction \(%\) versus the empirical runtime speedup factorR^Mconv\\hat\{R\}\_\{M\_\{\\mathrm\{conv\}\}\}across datasets and models \(Default vs\. RelShap \(BG\)\)\. Each point corresponds to a configuration atMconvM\_\{\\mathrm\{conv\}\}\. Shaded regions indicate variability across seeds\. Ker, MC, and Lev denote Kernel SHAP, Monte Carlo, and Leverage SHAP\.

#### Detailed analysis on provenance\-aware mode

TPC\-H\.Schema: As the primary key of theSuppliertable,suppkeyis referenced byLineitemandPartsupptables, and further connected toOrdersthrough join paths, inducing supplier\-level FDs across related records\. Query: Grouping onsuppkeyproduces one tuple per supplier with aggregate statistics \(e\.g\., counts, sums, and averages\), makingsuppkeyfunctionally determine all features\.suppkeyis removed in the final ML table and utilized in the provenance\-aware mode\.UW\-CSE\.Schema: The identifierp\_idin thePersontable propagates through relational links such asAdvisedByandTaughtBy, capturing FDs at the student level\. Query: Aggregating overp\_idyields one tuple per student with relational statistics \(e\.g\., advisor counts and course\-level features\), so all features are functionally determined byp\_id\.p\_idis finally removed in the ML table and used in the provenance\-aware mode\.

### J\.3Controlled validation ofRelShap

#### Validation under synthetic settings

Figure 15:Attribution and ranking changes under the FDage→life\_stage\\texttt\{age\}\\rightarrow\\texttt\{life\\\_stage\}as the strengthδ\\deltaof relationally invalid perturbations increases\.Figure 16:Attribution and ranking changes when incorporating both the FDage→life\_stage\\texttt\{age\}\\rightarrow\\texttt\{life\\\_stage\}and the provenance constraints from Example[1](https://arxiv.org/html/2608.11508#Thmexample1)\.Expanding on Section[4\.1](https://arxiv.org/html/2608.11508#S4.SS1), we consider two additional settings over four features—age,life\_stage,empl, andtotal\_amt\. The first enforces only the FDage→life\_stage\\texttt\{age\}\\rightarrow\\texttt\{life\\\_stage\}, whereas the second additionally incorporates the provenance constraints from Example[1](https://arxiv.org/html/2608.11508#Thmexample1)\. Unlike Section[4\.1](https://arxiv.org/html/2608.11508#S4.SS1), attribution ordering between a particular feature pair is no longer expected to hold in isolation when additional features are introduced, as their Shapley values now also depend on such newly included features\. We therefore examine how the overall attribution vector and feature ranking change asδ\\deltaincreases \(00to1010in increments of0\.50\.5, averaged across three random seeds\)\. Figures[15](https://arxiv.org/html/2608.11508#A10.F15)and[16](https://arxiv.org/html/2608.11508#A10.F16)report theL1L\_\{1\}distance and ranking changes as the strength of invalid perturbations increases\. Under the FD\-only setting,RelShapremains unchanged across all metrics, while all baselines exhibit increasing attribution and ranking shifts\. With provenance constraints,RelShapusing both FDs and provenance again remains invariant, followed by FD\-onlyRelShapas the most stable alternative\. These results show that excluding relationally impossible states corrects the internal Shapley computation and makesRelShapinsensitive to relationally invalid perturbations that are never observed during training or testing\.

#### Validation with real datasets

Figure 17:Attribution and ranking changes on German Credit as the influence ofδ\\deltaincreases\.\(a\)FD\-only setting\.\(b\)FD \+ Prov setting\.
Figure 18:Attribution and ranking changes on UW\-CSE as the influence ofδ\\deltaincreases\.Figures[17](https://arxiv.org/html/2608.11508#A10.F17)and[18](https://arxiv.org/html/2608.11508#A10.F18)validate the same behavior on two representative real datasets: German Credit, a standard ML dataset with FDs without provenance information, and UW\-CSE, a relational database dataset with both FDs and provenance constraints \(Table[8](https://arxiv.org/html/2608.11508#A10.T8)\)\. For both datasets, the base predictive model is XGBoost with0\.5≤r⁡\(⋅\)<1\.00\.5\\leq r\(\\cdot\)<1\.0\. On German Credit, all baselines exhibit increasing attribution and ranking changes asδ\\deltagrows, whereas FD\-onlyRelShapremains unchanged\. On UW\-CSE, in FD\-only setting,RelShapis the only method that remains stable even with increasingδ\\delta\. In FD \+ Prov setup, onlyRelShapincorporating both FDs and provenance constraint remains unchanged\. These results show that sensitivity to relationally invalid perturbations is eliminated when the corresponding relational structure is incorporated into Shapley computation\.

### J\.4Relational invalidity in Shapley computation

Table 16:Relational invalidity on datasets without DCs\. Each cell reports averaged violation prevalence \(top\) and violation density \(bottom\) over three random seeds, in percentage\.DatasetEstimatorBGBG \+ Prov, StrictBG \+ Prov, RelaxedAmazonKernel55\.95655\.95636\.59836\.59877\.76277\.76234\.50134\.50189\.35989\.35934\.84334\.843MC51\.35051\.35033\.66633\.66670\.21070\.21031\.93831\.93880\.14780\.14732\.64932\.649Leverage55\.09555\.09534\.50834\.50877\.95977\.95933\.24933\.24990\.31790\.31733\.96633\.966ChurnKernel96\.12096\.12023\.64223\.64296\.12296\.12228\.68328\.68396\.12596\.12528\.62728\.627MC93\.46693\.46628\.18828\.18893\.46793\.46732\.36532\.36593\.46993\.46932\.32032\.320Leverage97\.72197\.72129\.56029\.56097\.72297\.72233\.37733\.37797\.72497\.72433\.31333\.313Churn ModellingKernel90\.24090\.24017\.32117\.32190\.47990\.47920\.53720\.53790\.48190\.48120\.32020\.320MC84\.99284\.99217\.72517\.72585\.16085\.16020\.96320\.96385\.16285\.16220\.76220\.762Leverage95\.18795\.18720\.31320\.31395\.39495\.39423\.55623\.55695\.39595\.39523\.27823\.278German CreditKernel18\.91018\.9104\.3954\.39571\.96971\.96916\.56216\.56277\.13277\.13216\.28416\.284MC20\.46920\.4694\.7874\.78775\.19575\.19518\.09618\.09679\.71979\.71917\.82717\.827Leverage21\.61721\.6174\.9674\.96778\.24478\.24418\.56718\.56783\.17683\.17618\.26618\.266MovieLens 20MKernel87\.74887\.74847\.96947\.96987\.74887\.74847\.96947\.96987\.74887\.74847\.96947\.969MC71\.62171\.62139\.70439\.70471\.62171\.62139\.70439\.70471\.62171\.62139\.70439\.704Leverage99\.08199\.08147\.58947\.58999\.08199\.08147\.58947\.58999\.08199\.08147\.58947\.589Table 17:Relational invalidity on datasets with DCs\. Each cell reports averaged violation prevalence \(top\) and violation density \(bottom\) over three random seeds, in percentage\. All denotes BG \+ DCs \+ Prov, Relaxed\.DatasetEstimatorBGBG \+ DCsBG \+ Prov, StrictBG \+ Prov, RelaxedAllSpeedDatingKernel88\.50988\.50912\.21912\.21988\.50988\.5093\.1643\.16491\.29491\.29417\.52417\.52491\.69591\.69517\.61117\.61191\.69591\.69510\.53010\.530MC97\.88997\.88920\.03720\.03797\.88997\.8895\.1885\.18898\.27098\.27023\.74323\.74398\.33698\.33623\.76423\.76498\.33698\.33614\.97614\.976Leverage97\.88997\.88920\.03720\.03797\.88997\.8895\.1885\.18898\.27098\.27023\.74323\.74398\.33698\.33623\.76423\.76498\.33698\.33614\.97614\.976TPC\-HKernel98\.70498\.70416\.32016\.32098\.70498\.70416\.18316\.18398\.70598\.70517\.66417\.66498\.70698\.70617\.66917\.66998\.70698\.70617\.52317\.523MC94\.81694\.81619\.90619\.90694\.81694\.81619\.74219\.74294\.81694\.81621\.10021\.10094\.81694\.81621\.10221\.10294\.81694\.81620\.93220\.932Leverage99\.99999\.99919\.33219\.33299\.99999\.99919\.17019\.17099\.99999\.99920\.68220\.682100\.000100\.00020\.68420\.684100\.000100\.00020\.51520\.515UW\-CSEKernel5\.8065\.8061\.6321\.6326\.6756\.6751\.5851\.5857\.2437\.2431\.8291\.82910\.24410\.2441\.7701\.77010\.81910\.8191\.7301\.730MC4\.6544\.6541\.2871\.2875\.6015\.6011\.2671\.2675\.8245\.8241\.4351\.4358\.2938\.2931\.4341\.4349\.0389\.0381\.4131\.413Leverage5\.4455\.4451\.5351\.5356\.3166\.3161\.4941\.4946\.8446\.8441\.7221\.7229\.9559\.9551\.6841\.68410\.55310\.5531\.6481\.648SyntheticKernel80\.47580\.47514\.20314\.20380\.47580\.47512\.37412\.37491\.89291\.89220\.66120\.66191\.91991\.91920\.46620\.46691\.91991\.91918\.48718\.487MC75\.60775\.60714\.66014\.66075\.60775\.60712\.77212\.77286\.30286\.30221\.38121\.38186\.32286\.32221\.18921\.18986\.32286\.32219\.15419\.154Leverage77\.74277\.74215\.00415\.00477\.74277\.74212\.98212\.98294\.37094\.37022\.64922\.64994\.39094\.39022\.36222\.36294\.39094\.39020\.16720\.167Table 18:Estimator\-level relational invalidity averaged across datasets without DCs\. Each cell reports averaged violation prevalence \(top\) and violation density \(bottom\), in percentage\.EstimatorBGBG \+ Prov, StrictBG \+ Prov, RelaxedKernel69\.79569\.79525\.98525\.98584\.81684\.81629\.65029\.65088\.16988\.16929\.60929\.609MC64\.37964\.37924\.81424\.81479\.13179\.13128\.61328\.61382\.02482\.02428\.65228\.652Leverage73\.74073\.74027\.38827\.38889\.68089\.68031\.26831\.26893\.13993\.13931\.28231\.282Table 19:Estimator\-level relational invalidity averaged across datasets with DCs\. Each cell reports averaged violation prevalence \(top\) and violation density \(bottom\), in percentage\. All denotes BG \+ DCs \+ Prov, Relaxed\.EstimatorBGBG \+ DCsBG \+ Prov, StrictBG \+ Prov, RelaxedAllKernel68\.37368\.37311\.09411\.09468\.59168\.5918\.3278\.32772\.28472\.28414\.42014\.42073\.14173\.14114\.37914\.37973\.28573\.28512\.06812\.068MC68\.24268\.24213\.97213\.97268\.47868\.4789\.7429\.74271\.30371\.30316\.91516\.91571\.94271\.94216\.87216\.87272\.12872\.12814\.11914\.119Leverage70\.26970\.26913\.97713\.97770\.48670\.4869\.7099\.70974\.87174\.87117\.19917\.19975\.67075\.67017\.12417\.12475\.82075\.82014\.32614\.326*Violation density*reports the total number of violations normalized by the number of coalition–constraint pairs\. Tables[16](https://arxiv.org/html/2608.11508#A10.T16)and[17](https://arxiv.org/html/2608.11508#A10.T17)show that relational invalidity is widespread across datasets and estimators, with provenance constraints substantially increasing violation prevalence while affecting density more moderately; the lower normalized density under BG \+ DCs mainly reflects the larger number of coalition–constraint pairs rather than fewer violations\. Leverage SHAP generally yields the highest prevalence and density, whereas MC tends to be the lowest\. Averaged across datasets, Tables[18](https://arxiv.org/html/2608.11508#A10.T18)and[19](https://arxiv.org/html/2608.11508#A10.T19)confirm that these estimator\-level differences are smaller than the increases induced by richer constraints\.

## Appendix KShapley Values in Databases

Shapley values have been studied in the data management literature to quantify the contribution of*tuples to query answers*\([33](https://arxiv.org/html/2608.11508#bib.bib24);[15](https://arxiv.org/html/2608.11508#bib.bib26);[12](https://arxiv.org/html/2608.11508#bib.bib25);[2](https://arxiv.org/html/2608.11508#bib.bib27)\), and, in databases that violate integrity constraints, to the*extent of that inconsistency*\([4](https://arxiv.org/html/2608.11508#bib.bib23)\)\. In this setting, the players of the cooperative game are tuples, the value function is the query output on a subset of the database, and an endogenous/exogenous partition controls which tuples are subject to attribution\. Work in this line has established the computational complexity of exact Shapley computation over conjunctive queries \(CQs\)\([33](https://arxiv.org/html/2608.11508#bib.bib24)\), practical algorithms based on data provenance and knowledge compilation\([15](https://arxiv.org/html/2608.11508#bib.bib26);[12](https://arxiv.org/html/2608.11508#bib.bib25)\), and relation\-aware sampling for efficient estimation\([2](https://arxiv.org/html/2608.11508#bib.bib27)\)\. Where integrity constraints appear, they are themselves the*object of explanation*\(i\.e\., tuples are scored by how much they contribute to inconsistency\), rather than constraints on the coalitional game\. Our work is orthogonal: we explain the predictions of*black\-box ML models*trained on relational data, with*features*as players, and use relational structure as constraints on which coalitions and completions count as valid\.

A growing line of database research adapts the Shapley value to attribute the contribution of*tuples*\(or facts\) to the*results of queries*, and, in a related sub\-line, to the*extent of a database’s inconsistency*with respect to integrity constraints\.[33](https://arxiv.org/html/2608.11508#bib.bib24)initiated the formal study: they model query evaluation as a cooperative game in which endogenous tuples act as players and the query’s truth value \(for Boolean CQs\) or numerical output \(for aggregate queries\) acts as the wealth function\. They establish a fundamental complexity dichotomy—Shapley computation is in polynomial time for hierarchical CQs andFP\#​P\\mathrm\{FP\}^\{\\\#\\mathrm\{P\}\}\-complete otherwise—and give an a fully polynomial\-time randomized approximation scheme \(FPRAS\) for summation queries via Monte Carlo sampling\.

Subsequent work has focused on making these semantics practical\.[15](https://arxiv.org/html/2608.11508#bib.bib26)reduce Shapley computation to probabilistic query evaluation and develop an exact algorithm based on knowledge compilation of Boolean provenance into deterministic and decomposable \(d\-D\) circuits, together with a faster CNF\-Proxy heuristic for ranking; their experiments on TPC\-H and IMDB demonstrate that provenance\-based Shapley computation is feasible for a large fraction of realistic queries\.[12](https://arxiv.org/html/2608.11508#bib.bib25)build ShapGraph that pairs the global provenance\-graph view of query derivations with local Shapley heatmaps over input tuples, letting analysts navigate between a*structural*\(how\) and a*quantitative*\(how much\) account of a given output tuple\.[2](https://arxiv.org/html/2608.11508#bib.bib27)introduces Relation\-Stratified Sampling, a sampling strategy that partitions the Shapley subset space by the number of tuples drawn from each relation and allocates samples adaptively, yielding lower\-variance estimates than generic Monte Carlo and classical stratified sampling on TPC\-H workloads\.[4](https://arxiv.org/html/2608.11508#bib.bib23)study both the query\-answer and the database\-inconsistency applications; in the latter, integrity constraints \(ICs\) are themselves the object being explained, and tuples are scored by how much their presence contributes to violations of the ICs\.

Table[20](https://arxiv.org/html/2608.11508#A11.T20)summarizes these efforts along four axes: what the Shapley game*explains*, who the*players*are, what*technical contribution*is made, and how*integrity constraints*are treated\.RelShapdeparts from all of them along the first two axes: the object of explanation is a black\-box ML model’s prediction on a flattened relational instance, and the players are*features*of that instance rather than tuples of the underlying database\. This shift is not cosmetic: as Example[1](https://arxiv.org/html/2608.11508#Thmexample1)illustrates and Section[4](https://arxiv.org/html/2608.11508#S4)quantifies, applying Shapley to a flattened instance without accounting for the relational structure may produce different explanations\.

Consequently, we use relational structure—schema\-level FDs, query\-induced FDs, discovered FDs, and provenance—as*structural constraints on the Shapley game itself*, rather than as an object to be explained or as a purely computational device for tractability\.

Table 20:Shapley\-value approaches in database \(DB\) research\. All prior work uses DB tuples/facts as players and explains a property of the DB \(query answer or inconsistency w\.r\.t\. integrity constraints\)\.RelShapinstead explains ML model predictions on flattened relational data, with features as players, and uses relational structure as a constraint on the coalitional game\.WorkObject explainedPlayersKey technical contributionRole of ICsLivshits et al\.\([33](https://arxiv.org/html/2608.11508#bib.bib24)\)Query answer \(Boolean / aggregate CQ\)Endogenous tuplesComplexity dichotomy \(hierarchical CQs in polynomial time, elseFP\#​P\\mathrm\{FP\}^\{\\\#\\mathrm\{P\}\}\-complete\); FPRAS for summation via MCNot part of the setupDeutch et al\.\([15](https://arxiv.org/html/2608.11508#bib.bib26)\)Query answerEndogenous tuplesReduction to probabilistic QE; knowledge compilation of provenance into d\-D circuits; CNF\-Proxy heuristicNot part of the setupShapGraph\([12](https://arxiv.org/html/2608.11508#bib.bib25)\)Query answer \(per output tuple\)Input tuplesInteractive system pairing provenance graphs with Shapley heatmaps \(built on ProvSQL\)Not part of the setupAlizad\([2](https://arxiv.org/html/2608.11508#bib.bib27)\)Query answerEndogenous tuplesRelation\-Stratified Sampling \(RSS\) and adaptive variant \(ARSS\) with lower\-variance estimates on TPC\-HNot part of the setupBertossi et al\.\([4](https://arxiv.org/html/2608.11508#bib.bib23)\)Query answer*and*DB inconsistencyEndogenous tuplesSurvey; covers tuple contribution to inconsistency w\.r\.t\. ICs as a second Shapley application in data managementObject of explanation\(tuples scored by contribution to IC violations\)RelShap\(ours\)ML\-model prediction on a flattened relational instanceFeaturesRelationally consistent background and coalition selection, grounded in schema/query/discovered FDs and provenance; Shapley invariance and runtime\-reduction resultsStructural constraint on the coalitional game
## Appendix LLimitations

Human evaluation\.Our controlled validation \(Section 4\.1\) establishes thatRelShapcorrects attributions with respect to relational validity under known ground truth, and Section 4\.2 shows these corrections are large and systematic on real data\. However, we do not evaluate whether the corrected explanations are more useful, trustworthy, or actionable for human decision\-makers\. A user study with practitioners who consume Shapley explanations \(e\.g\., in credit or hiring contexts\) is important future work\.

Constraint quality\.RelShaptreats the selected constraint setΣ\\Sigmaas correct\. Data\-driven FDs are exact dependencies on finite data, so small or unrepresentative samples can yield spurious FDs; conversely, meaningful dependencies that hold only approximately \(e\.g\., with rare exceptions or noise\) are not discovered by exact FD mining\. The user inspection step \(Section 3\.1\) mitigates but does not eliminate this risk, and extendingRelShapto approximate or probabilistic constraints is a natural direction\.