Abstract
In large-scale data management, organizations often rely on a library of legacy stored procedures to transform and integrate data. However, the internal logic of these procedures is frequently opaque, leading to the "Data Readiness Problem": determining if a sequence of such "black-box" procedures can transition a database into a state that satisfies a specific analytical goal. This paper formalizes this problem and investigates its decidability. While the general problem is undecidable, we identify a specific class of procedures—those with "safe scope" and "full" constraints—where the problem becomes decidable, albeit with high computational complexity.
1. Introduction
Modern enterprises manage vast amounts of data using complex sequences of transformations, often implemented as stored procedures. Over time, these procedures become legacy code—their original authors depart, documentation vanishes, and their internal logic becomes a "black-box." When a new data requirement arises, engineers must decide whether to write new transformation scripts or reuse existing ones.
The core challenge is the Data Readiness Problem: Given a set of black-box procedures, is there a sequence that transforms the current database state into one that satisfies a target boolean query? This problem is critical for automating data wrangling and ensuring data provenance in evolving systems.
2. Modeling Black-Box Procedures
To reason about procedures without inspecting their code, the authors propose a formal framework where each procedure $P$ is defined by a "contract" consisting of four components:
- Scope: The specific tables or columns the procedure is authorized to modify.
- Preconditions ($C_{in}$): Logical constraints that must hold for the procedure to execute.
- Postconditions ($C_{out}$): Guarantees about the database state after execution, typically expressed as tuple-generating dependencies (tgds).
- Preservation Guarantees ($Q_{pres}$): A specification of data that the procedure is guaranteed not to alter or delete.
By treating procedures as black boxes governed by these contracts, the framework allows for formal reasoning about the composition of operations. Key questions include Applicability (can procedure B follow A?), Nonemptiness (can the procedure produce any valid output?), and Data Readiness (can a goal state be reached?).
3. Theoretical Results and Decidability
The paper explores the boundaries of decidability for these problems. A significant finding is that even with simple constraints like tuple-generating dependencies (tgds), basic properties like nonemptiness are undecidable because they can simulate complex mathematical structures.
To find a decidable fragment, the authors introduce the concept of "safe scope." A procedure has a safe scope if it only modifies the relations it is explicitly intended to update and preserves existing data within those relations. However, safe scope alone is insufficient for decidability. The problem only becomes solvable when the logic is further restricted to "full tgds," which prevent the introduction of new, existential values (i.e., values not already present in the database or the procedure's parameters).
For the class of procedures with safe scope and full tgds, the Data Readiness Problem is proven to be decidable and is in the NEXPTIME complexity class. This result establishes a theoretical foundation for building automated assistants that can navigate libraries of legacy data transformations.
4. Discussion and Future Work
While the identified decidable class provides a path forward, several limitations remain. The current model assumes a stable database schema, whereas real-world migrations often involve schema changes. Furthermore, the NEXPTIME complexity suggests that practical implementations will require significant optimization and the use of heuristics.
Future research directions include extending the framework to handle unstructured data and machine-learning-based transformations, where the black-box nature is even more inherent. Additionally, integrating these methods with knowledge bases could help track database states more effectively across long sequences of unknown procedures.
Summary updated