RelShap: Relationally Consistent Shapley Explanations

RelShap is 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, which RelShap exploits to reduce runtime without changing Shapley values; we provide a combinatorial characterization of the expected speedup. Experiments across multiple datasets, models, and estimators show that RelShap produces 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.

Most machine learning pipelines flatten relational data into single-table representations for model training. 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 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, 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. SHAP, 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. Aas et al. 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 present RelShap—Relationally Consistent Shapley Explanations—the first framework to integrate relational database constraints into Shapley value-based feature attributions. RelShap changes 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, RelShap correctly identifies the dominant feature where Kernel SHAP, Conditional SHAP, and ManifoldShap do not. For instance, in a loan approval scenario, the explanation changes substantially depending on whether relational constraints are respected. 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) and Transactions(t id, a id, amount), linked by applicant identifier a id. Six representative applicants and their transactions are shown in Tables 1a and 1b. A data analyst issues the query:

SELECT a.a id, a.age, a.life stage, a.empl, SUM(t.amount) AS total amt FROM Applicants a, Transactions t WHERE a.a id = t.a id GROUP BY a.a id, a.age, a.life stage, a.empl;

to obtain an applicant-level view, then drops the identifier a id and adds a target loan approved to yield the ML-ready dataset in Table 1c.

ML practitioners computing explanations typically receive only this final flattened representation, with no visibility into the upstream structure. Applicant a27 applied for a loan, was rejected, and sought an explanation. Kernel SHAP, a widely used method, reports life stage as the top driver of the prediction with a positive score. This attribution, however, is an artifact of relationally invalid completions from Kernel SHAP. For instance, fixing age = 35 and filling in the rest from applicant a29 yields the combination (age = 35, life stage = older), which is impossible under the FD age → life stage.

RelShap instead 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: 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 one total amt. RelShap enforces these constraints during Shapley computation: fixing age = 35 forces life stage = middle; the remaining attributes are unconstrained and filled from a chosen background data point (a29). Additionally, RelShap supports a provenance-aware mode that traces each row of the flattened table back to its source tuples in the original tables. Fixing age = 35 narrows the provenance to a27, the sole applicant with that age, at which point the schema determines empl = self emp and total amt = 119. Provenance-based recovery is not always available when it does not resolve to a single tuple: age = 63, for instance, is shared by a12 and a29.

Notably, RelShap computes different Shapley values even without approximation. Under both RelShap variants, life stage receives exactly zero attribution (which does not necessarily generalize), down from +0.2299 under Kernel SHAP, because the discovered FD age → life stage makes life stage redundant when age is present in a coalition, once coalitions are projected to relationally valid completions. Kernel SHAP ignores this redundancy and distributes substantial attribution to life stage. The top-ranked feature consequently changes from life stage to age. 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:

1. RelShap alters both background data and coalition selection under relational constraints, producing attributions that correctly reflect the data-generating structure.

2. RelShap is 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. Computational effects: RelShap achieves orthogonal acceleration by avoiding redundant coalition evaluations while preserving Shapley values. We combinatorially characterize the resulting speedup factor as a function of the coalition estimator and FD structure.

4. We evaluate RelShap on 9 datasets across 4 models and 3 coalition estimators, empirically validating both the semantic effects and the runtime predictions.

Let F be the set of input features, f: RF → R a predictive model trained on Dtrain, and x ∈ Dtest an instance to be explained. To explain the prediction f (x), for any coalition S ⊆ F, xS denotes the projection of x onto S. The Shapley value of feature i ∈ F is defined as ϕi (f) = Σ S⊆F i S!(F − S − 1)! / F ! (f (xS∪ i) − f (xS)).

As discussed in Section 1, computing Eq. (1) in practice requires two design choices: background data selection, which determines how features in F S are filled in when evaluating f, and coalition selection, which subsets S ⊆ F i are evaluated. Since exhaustive enumeration over reference points and over the 2F −1 coalitions is infeasible in practice, both are typically operationalized via sampling. The two dimensions admit a multiplicity of instantiations and are typically treated as orthogonal. RelShap operates 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.

Let Pbg (zF) denote a background distribution over the absent features indexed by F S, and B be the number of background samples (possibly all reference data points). With a completed input x̃(S, zF) ∈ RF, we define f (xS) = EzF ∼Pbg [f (x̃(S, zF))]. Methods differ in their choice of Pbg. Interventional methods, including default Kernel SHAP, 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 instead estimates the distribution of absent features given the observed ones, aiming to preserve dependencies but potentially introducing estimator error. Causal methods intervene through a causal graph among the features, and ManifoldShap 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. Importantly, RelShap is 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: RelShap can 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, to comply with the no-distributional-assumptions property while removing the structurally infeasible inputs that Frye et al. and Taufiq et al. warn about.

We draw M coalitions from a coalition distribution Pcoal over S ⊆ F i and approximate ϕi (f) ≈ 1/M Σ M m=1 w(S (m))(f (xS (m) ∪ i) − f (xS (m))). Different Shapley value estimators choose different Pcoal and importance weight w. Kernel SHAP 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 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 or Fourier basis reduction. RelShap is estimator-agnostic and provides orthogonal acceleration: it preserves any base estimator's sampling distribution, weights, and accuracy guarantees, canonicalizing sampled coalitions under relational validity. Witter et al. also uses equivalence classes, but derives them from structural causal models. Maafa et al. studies lattice-structured coalition spaces to reduce computations, but not for ML predictions.

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 → B states that the value of attributes in A uniquely determines the value of B; for instance, in Example 1, age → 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., if region = 'North America' then currency ∈ 'USD', 'CAD', '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. RelShap systematically prevents this.

RelShap incorporates two types of relational constraints: global, applied to all test instances, and local, instantiated per test instance. ΣFD is global; provenance-aware constraints, Σdom, and Σden are applied locally. RelShap first prepares relational constraints for downstream modules, either directly from relational inputs or from flattened-only inputs through normalization. We denote a relational schema as S, a query as Q, and the resulting flattened dataset as D. The schema, query, and resulting data together induce a collection of relational constraints, which we denote by Σ S,Q,D = ΣFD ∪Σdom ∪Σden, where ΣFD, Σdom, and Σ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 Σ.

Relational schema. Σ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., CHECK clauses), ignoring unary type constraints already satisfied by the data. Query. We parse Q using SQLGlot to extract query-induced FDs and conditional domain rules. ΣQ FD identifies GROUP BY clauses, window aggregation, top-1 selection patterns, and self-joins. Σdom captures WHERE and JOIN predicates. Flattened data. RelShap discovers exact minimal FDs with bounded left-hand-side size (default 2) and single-attribute right-hand sides; multi-attribute right-hand sides can be derived via Armstrong's axioms. For any L ⊆ F and attribute a ∈/ L, let D/L denote the partition of D induced by equality on L; an FD L → a holds if, for all equivalence classes C ∈ D/L, DISTINCTa (C) ≤ 1. For each discovered FD A → B with dom(B) ≤ 20 (default), we derive conditional domain rules (B = s) ⇒ φ(A): for categorical A, φ(A) is the set of observed values; for continuous A, an interval [ls, us] estimated from the data. We also extract denial constraints by identifying cycles in the FD set (e.g., A → B, B → C, C → 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 D for constraint discovery and Dtrain as the reference distribution.

Definition 1 (Relationally Consistent Background Distribution). Given a feature set F, a coalition S ⊆ F, an instance x, and a set of relational constraints Σ, we define Pbg Rel = (Pbg Marginal, if Σ = ∅, P ZF x̃(S, ZF) = Σ otherwise.

Under Def. 1, any coalitions S and S ′ are Σ-equivalent, i.e., S ∼Σ S ′, if they induce the same set of relationally valid completions under Σ. Accordingly, [S]Σ denotes the equivalence class of S under ∼Σ, and the Σ-coalition space CΣ is the quotient of the original coalition space by ∼Σ, collapsing coalitions indistinguishable under Σ.

Definition 2 (Quotient space coalition projection). Given CΣ, quotient space coalition projection is a post-sampling procedure that maps a coalition S ⊆ F i drawn by any sampler to its Σ-equivalence class [S]Σ (i.e., each coalition value is replaced by its canonical representative under Σ). For example, if Σ contains an FD a → b over a, b, c, then a ∼Σ a, b and a, c ∼Σ a, b, c, and hence each pair belongs to the same Σ-equivalence class. Under Def. 2, once a coalition is evaluated, subsequent samples mapping to the same Σ-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) 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). Together these provide orthogonal acceleration under Σ ̸= ∅.

Proposition 1 (Shapley value invariance under quotient space coalition projection). Quotient space coalition projection does not change the resulting Shapley value of feature i, 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 ∼Σ is non-trivial, quotient projection strictly reduces the coalition space, CΣ < 2F −1; Section 3.3 quantifies the expected reduction.

Provenance-aware mode incorporates local constraints: identifier-induced FDs (primary and foreign keys; they are part of global ΣFD but applied instance by instance) no longer explicit in the flattened table (e.g., when identifiers are dropped as in Example 1). 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, observing only the age of a29 yields candidates a12, a29; although the exact identifier is ambiguous, life stage (which may already be determined by age) and empl take 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) RelShap is typically sufficient in with-key settings where identifiers are retained (e.g., recommender systems).

Algorithm 1 orchestrates RelShap: it draws M raw 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. CanonicalizeCoal lets Σ-equivalent coalitions share one evaluation based on FDClosure; ProvExpand incorporates 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; and ICRepair extends the coalition with features whose values are forced by domain and denial constraints. RelShap first 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 ≤ M).

The runtime reduction from quotient space coalition projection is the decrease from the sampling budget M to the number of distinct projected coalitions M. Prior works characterize CΣ for representative FD structures, but only under deterministic coalition evaluation. RelShap also supports stochastic sampling from Pcoal, where widely used estimators sample with coalition size-dependent probabilities pk = Pr(S = k). 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). Let q(C) = PrS∼Pcoal ([S]Σ = C) be the probability that a sampled coalition maps to Σ-equivalence class C ∈ CΣ. If the draws are i.i.d., the expected number of distinct classes evaluated after projection mode is E[KM] = Σ C∈CΣ [1 − (1 − q(C))M], where q(C) = Σ F −1 k=r(C) pk NC (k) / (F −1 k) is the probability of a sampled coalition landing in class C. Hence the normalized expected runtime speedup factor relative to the baseline sampler is RM = 1 − E[KM]/M. NC (k) is the number of size-k coalitions whose projection belongs to C, and r(C) = min S [S]Σ = C is the minimum size of any coalition generating C (rank). For the FD a → b over a, b, c from Section 3.2, quotient mode reduces CΣ from 23 = 8 to 6. Intuitively, FDs with small left-hand sides (LHSs) induce classes with small r(C), so many coalitions collapse to the same class, yielding large NC (k) at small sizes. The improvement for Kernel SHAP is therefore amplified when Σ contains 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 across k, so their improvement tracks the overall magnitude of NC (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 provides a proof and Section 4 confirms that observed speedups closely match this analysis.

We evaluate RelShap on 9 datasets: 5 standard ML datasets normalized into relational form — Amazon Employee Access, Churn, Churn Modelling, German Credit, and SpeedDating — and 4 relational datasets: TPC-H, UW-CSE, MovieLens 20M, and a Synthetic dataset extending Example 1 with domain and denial constraints. We train logistic regression, XGBoost, Random Forest, and MLP-PLR, covering linear, tree-based, and neural models, and compute explanations with Kernel SHAP, MC, and Leverage SHAP (means and standard deviations over three seeds) for nexplain = min(200, Dtest) instances per dataset, using a per-dataset convergence budget Mconv at which Shapley estimates stabilize. Relational constraint extraction is a one-time preprocessing step reused across all explanations; it completes within 12 seconds on every dataset except SpeedDating (482.7s) and MovieLens 20M (98.9s), where data-driven FD discovery dominates, and its cost, typically offset by the resulting speedups, is excluded from runtime comparisons.

In summary, our experiments show that standard estimators query impossible worlds constantly; when ground truth is known, RelShap is 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.

We demonstrate that RelShap yields more intuitive explanations than existing methods in a controlled setting, following experiments in Taufiq et al. Building on Example 1, we consider a loan approval scenario restricted to two features (age and life stage), with an FD age → life stage. We define a synthetic predictor g(x) = 1 age > 50 + δ r(life stage) 1 x ̸= Σ, where r(life stage) ∈ 0.3, 0.6, 0.9 assigns an arbitrary constant to each of the three life stages, and δ ranges from 0 to 10 in increments of 0.5. Since every data instance satisfies Σ, 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 on age, and a semantically intuitive explanation should assign greater importance to age than to life stage regardless of δ.

Figure 3 shows how often each feature receives the larger absolute attribution as δ increases. All three baselines rank age first more often than life stage; however, Kernel SHAP increasingly shifts attribution toward life stage as invalid perturbations grow. Conditional SHAP and ManifoldShap are less sensitive to increasing δ, but still rank life stage first for a substantial fraction of instances. In contrast, RelShap consistently assigns the larger attribution to age for all δ. This indicates that the explanation change from RelShap is 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 fills life stage from the marginal distribution, independently of age, so 31.8% of its coalitions violate the FD (e.g., age = 35 with life stage = older); each violation activates the perturbation term δ r(life stage), and the resulting spurious attribution to life stage grows with δ. Conditional SHAP, which estimates the conditional distribution of life stage given age, and ManifoldShap, which restricts completions to an estimated data manifold, suppress most, but not all, violations (4.8% and 5.1%, respectively), explaining their partial yet incomplete robustness. RelShap enforces the FD exactly: its violation prevalence is 0%, the perturbation term never activates, and life stage receives no spurious attribution. Note that violation prevalence itself does not depend on δ: increasing δ makes each violation more costly, not more frequent, which is why misattribution grows with δ while prevalence stays fixed.

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 δ increases. RelShap remains unchanged across all metrics, while all baselines exhibit increasing attribution and ranking shifts; a setting with additional provenance constraints behaves identically. This shows that eliminating impossible worlds makes RelShap insensitive 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. RelShap changes 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.

We compare default estimators against five RelShap configurations 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 from 64–74% under BG to 82–93% under BG + Prov, Relaxed on datasets without DCs, and from 68–70% under BG to 72–76% under All: invalidity becomes more pervasive as richer constraints are incorporated.

Prevalence alone does not establish that explanations change; that also depends on the model's response in the invalid region. We therefore assess how RelShap changes Shapley values relative to default estimators, finding shifts well beyond random ranking perturbation. For each instance, we measure ranking differences using Top-3 Jaccard distance and 1 − RBO (rank-biased overlap), capturing the three most influential features and the full top-weighted ranking, respectively. Against the Mallows null baseline range of Hwang et al., we define ∆ as the signed deviation from the range midpoint; ∆ > 0 indicates a change larger than expected at random, and we report 95% confidence intervals (CIs) on the fraction of such cases.

Figure 4 shows the percentage of cases with ∆ > 0. This percentage exceeds 50% across most RelShap configurations, 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 nearly 100% for SpeedDating—but are not strictly monotonic in the number of constraints. The effects are stable across predictive models, confirming that RelShap is generally model-agnostic. Together with Section 4.1, these results indicate that the observed ranking differences reflect meaningful corrections toward relationally valid explanations.

Table 2 reports the magnitude of these changes by configuration: domain and denial constraints yield the largest corrections, provenance effects depend on the mode, and ∆ > 0 on average in all but one mode–metric pair. On TPC-H, provenance mode replaces the top-3 features almost entirely (Top-3 Jaccard 0.91–0.96 under Kernel SHAP and MC).

Quotient mode (Q) applies the quotient space coalition projection of Def. 2 as an orthogonal acceleration on top of any configuration. 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. 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 of RM in Thm. 1 correlates closely with measured reduction (Pearson: mean 0.806, median 0.875; Kendall τ: mean 0.741, median 0.833), reliably predicting when reduction occurs, though its magnitude depends on the dataset and sampling strategy.

Conventional Shapley value methods treat feature coalitions as unrestricted subsets, in effect querying relationally impossible worlds. RelShap is 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. RelShap also treats the extracted, user-vetted constraints as correct: spurious FDs discovered from small data would propagate to explanations.

Based on the paper, here are the specific improvements you can make to AI systems and what the improved system can do:

• Improvement: Integrate relational database constraints (functional dependencies, domain constraints, denial constraints) into Shapley value computation.

• What the improved system can do: Generate feature attributions that never evaluate the model on impossible feature combinations (e.g., age=35 with life stage=older when an FD says age→life stage). This prevents spurious attributions to redundant features and correctly identifies the true dominant feature in controlled settings where Kernel SHAP, Conditional SHAP, and ManifoldShap fail.

• Improvement: Trace each flattened data row back to its source tuples in the original relational tables, using identifier-induced dependencies.

• What the improved system can do: When a coalition fixes certain features (e.g., age=35), the system narrows provenance to a single source tuple (e.g., applicant a27), then infers all other feature values (empl, total amt) from that tuple, producing fully consistent completions. In relaxed mode, it handles ambiguous provenance by using features constant across candidate tuples.

• Improvement: Exploit functional dependencies to collapse equivalent coalitions into equivalence classes, reusing cached evaluations.

• What the improved system can do: Reduce runtime by up to the theoretically characterized speedup factor (Theorem 1) without changing Shapley values. For example, with FD a→b, coalitions a and a,b are equivalent, so only one model evaluation is needed. The system preserves the base estimator's sampling distribution and accuracy guarantees while deduplicating evaluations.

• Improvement: Apply relational constraints as a plug-in restriction layer on top of any coalition estimator (Kernel SHAP, Monte Carlo, Leverage SHAP).

• What the improved system can do: Enforce relational validity without altering the estimator's sampling or weighting properties. This means users can keep their preferred estimator while gaining correctness, and the system works across linear, tree-based, and neural models.

• Improvement: Automatically extract functional dependencies, domain constraints, and denial constraints from either relational schemas/queries or from flattened data alone.

• What the improved system can do: When given only a flattened table (common in practice), the system discovers exact minimal FDs (e.g., age→life stage) and conditional domain rules, then applies them during explanation. This removes the need for manual constraint specification and works even when the original database structure is unavailable.

• Improvement: Eliminate all relationally invalid perturbations during Shapley computation (violation prevalence = 0%).

• What the improved system can do: In synthetic scenarios with known ground truth (e.g., loan approval where only age matters), the system consistently assigns higher attribution to the true dominant feature (age) across all perturbation strengths δ, while baselines increasingly misattribute to life stage as invalid perturbations grow. This demonstrates robustness to adversarial or accidental invalid feature combinations.

• Improvement: Restrict background data and coalitions to configurations that could actually arise from the underlying relational data.

• What the improved system can do: Produce explanations that reflect the true data-generating structure, leading to large and systematic ranking changes (e.g., Top-3 Jaccard distance up to 0.96 on TPC-H) compared to unconstrained methods. This is particularly important for high-stakes domains like credit approval, where explanations must align with actual data constraints.

• Improvement: Provide a theoretical characterization (Theorem 1) of expected runtime reduction based on FD structure and coalition estimator.

• What the improved system can do: Predict before execution how much speedup to expect (empirically validated with Pearson correlation 0.806 and Kendall τ 0.741), enabling users to decide whether to enable quotient mode based on their data's FD structure and estimator choice.

• Improvement: Extract constraints efficiently as a one-time preprocessing step (under 12 seconds for most datasets, 98.9s for MovieLens 20M, 482.7s for SpeedDating).

• What the improved system can do: Handle large relational datasets without significant overhead, reusing extracted constraints across all explanation queries for multiple instances and models.

• Improvement: Validate across logistic regression, XGBoost, Random Forest, and MLP-PLR models.

• What the improved system can do: Consistently produce relationally valid explanations regardless of the underlying predictive model, making it suitable for diverse ML pipelines in production.