We consider the problem of determining whether organizations facing a new data-transformation task can avoid building a new transformation procedure from scratch by reusing their stored procedures. Because it can be di cult to obtain exact descriptions of what stored procedures do, our framework abstracts data-transforming tools as black-box procedures, in which a procedure description indicates the parts of the database that might be modi ed by the procedure and constraints on the states of the database that must hold before and after the application of this procedure. In this paper we present our framework and study the problem of determining, given a database and a set of procedures, whether there is a sequence of procedures from this set such that their application to the database results in the satisfaction of a boolean query. This data readiness problem is undecidable in general, but we show decidability for a broad and realistic class of procedures.
The databases of many organizations nowadays periodically undergo transformations, due to applications of data-improvement operations, merging of multiple repositories, or management decisions. These transformations are commonly carried out by means of stored procedures or other similar artifacts that are kept together with the database, and may have to be applied periodically, becoming at times part of the normal daily operations of the organizations. For example, it is not uncommon to nd institutions with separate databases for their accountancy and operations divisions, in which the integration is carried out by a stored procedure that runs at the end of every working day.
Whenever a new data-transformation task arises, organizations facing the
cost of assembling a new procedure to solve this task may ask instead whether one
can reuse some of the procedures that are already available. However, to answer
this question we need to be able to reason about the outcomes of procedures,
or even of sequences of applications of procedures. Several lines of research have
been studying these outcomes when procedures are understood as part of the
normal operations of an institution (see excellent surveys [
At the same time, it is not always feasible to obtain an exact description
of the inner workings of a procedure (as in when its creator(s) no longer work
for the company, see, e.g., [
Given an insurance id I, the analyst can capture the desired information
via query SELECT facility FROM LocVisits WHERE insId = I, posed over
LocVisits modi ed by adding attribute insId containing the insurance id's of
patients. It is natural for the analyst to ask: Can I use any available procedures
to transform my data so that this query can be posed on my database? In other
words, is there a way to apply these procedures so that I could guarantee that
my database satis es certain tness-for-use [
We propose a formal framework in which data-transforming tools are abstracted as black-box procedures, described by the following information: { A speci cation of which parts of the database the procedure is modifying; { Conditions to be satis ed for the procedure to be applicable; { Conditions that will be satis ed once the procedure has been applied; and { Any additional guarantees on parts of the data that must not be modi ed.
In this paper we study this framework for procedures that do not alter the schema of databases, such as the procedure that migrates the information of the analyst in the example above. We study basic questions arising in the framework, such as whether a procedure can be applied to the outcome of a given procedure over a given instance, and whether the outcome of a (sequence of) procedures is nonempty. Finally, we consider what we call the data-readiness problem: Given an instance I, a set of procedures, and a boolean query over instances (that intuitively expresses a desired property of the data), is there a way to construct a sequence of procedures from so that each instance in the outcome satis es this property? While undecidable in its general form, we show that this problem is decidable for some broad classes of procedures.
For space reasons we omit proofs from this draft. All of them can be found
in the full version of this paper [
Since we aim to model procedures over real databases, we write the paper using a speci c named assumption over instances and queries.
Schemas and Instances. Assume three disjoint sets: a countably in nite set of attribute names A = fA1; A2; : : :g totally ordered by A, a countably in nite domain of values (or elements) D, and a countably in nite set of relation names R = fR1; R2; : : :g. A relational schema over A and R is a partial function S : R ! 2A, which associates a nite set of attributes with a nite set of relation symbols. We say that R is in S if S(R) is de ned. An instance I of schema S assigns a set RI of tuples to each relation R in S, so that if S(R) = fA1; : : : ; Ang then RI Dn, with the set of tuples structured so that the elements of each tuple (a1; : : : ; an) appear in the assumed attribute order, that is, A1 <A <A An. Queries across Schemas, Total Queries. A named atom is an expression R(A1 : x1; : : : ; Ak : xk), where R is a relation name, each Ai is an attribute name, and each xi is a variable. The variables mentioned by such an atom are x1; : : : ; xk, and the attributes are A1; : : : ; Ak. Such an atom is compatible with schema S if fA1; : : : ; Akg S(R). Given a named atom R(A1 : x1; : : : ; Ak : xk), an instance I of schema S that is compatible with the atom, and an assignment : fx1; : : : ; xkg ! D assigning values to variables, we say that (I; ) satis es R(A1 : x1; : : : ; Ak : xk) if there is a tuple a in RI such that its projection A1;:::;Ak a over A1; : : : ; Ak is the tuple (x1); : : : ; (xk).
A conjunctive query (CQ) is an expression of the form 9z (z; y), where z and y are tuples of variables and (z; y) is a conjunction of named atoms that uses the variables in z and y. A CQ is compatible with S if all its named atoms are compatible. The usual semantics of CQs is obtained from the semantics of named atoms in the usual way. Given a CQ Q compatible with S, the result Q(I) of evaluating Q over I is the set of all the tuples (x1); : : : ; (xk) such that (I; ) satisfy Q. Further, a total query, which we de ne to be an expression of the form R for some relation name R, returns all the tuples of R, regardless of the schema and arity of R, as is done in SQL with SELECT * FROM R. A total query of this form is compatible with schema S if S(R) is de ned; the result of evaluating this query over an instance I over a compatible schema S is the set of all tuples in RI .
Data constraints: We consider data constraints that are (i) tuple-generating dependencies (tgds), i.e., expressions of the form 8x 9y (x; y) ! 9z (x; z) for CQs 9y (x; y) and 9z (x; z), and (ii) equality-generating dependencies (egds), i.e., expressions of the form 8x 9y (x; y) ! x = x0 for a CQ 9y (x; y) and variables x; x0 in x. As usual, for readability we sometimes omit the universal quanti ers of tgds and egds. An instance I satis es a set of tgds and egds, written I j= , if (1) each CQ in each dependency in is compatible with the schema of I, and (2) every assignment : x [ y ! D such that (I; ) j= (x; y) can be extended into a 0 : x [ y [ z ! D such that (I; 0) j= (x; z).
A tgd is full if it does not use existentially quanti ed variables on the righthand side. A set of tgds is full if each tgd in is full. is acyclic if an acyclic graph is formed by representing each relation mentioned in a tgd in as a node and by adding an edge from node R to S if a tgd in mentions R on the left-hand side and S on the right-hand side. 3
In this section we formalize the notion of procedures that transform data. We view procedures as black boxes and assume no knowledge of or control over their inner workings. Our reasoning about procedures is based on the following information: The input conditions, or preconditions, on the state of the data that must hold for a procedure to be applicable; the output conditions, or postconditions, on the state of the data that must hold after an application of the procedure; and the set of relations a ected by the application. To specify that some of the data will not be deleted, we also allow the inclusion of some queries whose answer needs to be preserved during the application of the procedure. Example 1. Recall the procedure Pmigrate outlined in Section 1; its intent is to de ne migration of data from relation EVisits into LocVisits. Pmigrate can be described as follows. First, the scope: Pmigrate only changes relation LocVisits. Next, the precondition: Pmigrate requires a schema with relations LocVisits and EVisits, each with attributes facility , pId , and timestp. Next, the postcondition: after Pmigrate is applied, each tuple of EVisits must be in LocVisits. Finally, we need to guarantee that the tuples in LocVisits are not deleted.
In the following, we present notation for formally de ning these types of procedures. We start by introducing \structure constraints," which we use to de ne the scopes of procedures. 3.1
Structure Constraints A structure constraint is a formula of the form R[s] or R[ ], with R a relation symbol, s a tuple of attribute names from A, and a symbol not in A or R acting as a wildcard. A schema S satis es a structure constraint R[s], denoted S j= R[s], if S(R) is de ned and each attribute in s belongs to S(R). A schema S satis es the constraint R[ ] if S(R) is de ned.
Given a set C of structure constraints and a schema S, we denote by QSnC the conjunctive query formed by the conjunction of the following atoms: { For each relation R such that S(R) = fA1; : : : ; Amg and R is not mentioned in C, QSnC includes an atom R(A1 : z1; : : : ; Am : zm), where z1; : : : ; zm are fresh variables. { For each T mentioned in C such that T [ ] is not in C, QSnC includes an atom T (B1 : z1; : : : ; Bk : zk), where B1; : : : ; Bk are all the attributes in S(T ) that are not mentioned in any constraint of the form T [s] in C, and z1; : : : ; zk are fresh variables.
Intuitively, QSnC is intended to retrieve the projection of the entire database over all the relations and attributes not mentioned in C. QSnC is unique up to the variable renaming and order of conjuncts. As an example, let schema S have relations R, S, and T , with attributes: A1 and A2 in R; B1, B2, and B3 in T ; and A1 and B1 in S. Let set C comprise constraints R[ ] and S[B1]. Then QSnC is the query T (B1 : z1; B2 : z2; B3 : z3) ^ S(A1 : w1). 3.2
Formal De nition of Procedures We de ne procedures w.r.t. a class C of FO constraints and a class Q of queries. We will focus primarily on tgds, egds, structure constraints, and CQ queries. De nition 1. A procedure P over C and Q is a tuple (Scope; Cin; Cout; Qpres), where: { Scope is a set of structure constraints that de nes the scope (i.e., the relations and attributes) within which the procedure operates; { Cin and Cout are constraints in C describing the pre- and postconditions of
P , respectively; { Qpres is a set of queries in Q that serve as a preservation guarantee for the procedure.
Example 2 (Example 1 continued). We de ne the procedure Pmigrate formally as follows: Scope: The scope is the constraint LocVisits[ ].
Cin: We use the structure constraints EVisits[facility; pId; timestp] and LocVisits [facility; pId; timestp], to ensure that the data have the correct attributes. Cout: The postcondition comprises the tgd EVisits(facility : x; pId : y; timestp : z) ! LocVisits(facility : x; pId : y; timestp : z): It says that, once Pmigrate has been applied, the projection of EVisits over facility , pId , and timestp is a subset of the respective projection of LocVisits. Qpres: We use query LocVisits(facility : x; pId : y; timestp : z), whose intent is to state the guarantee that all the answers on LocVisits that are present before Pmigrate is applied will be preserved.
Semantics: A procedure P = (Scope; Cin; Cout; Qpres) is applicable on an instance I over schema S if (1) Each query in Qpres is compatible with S; and (2) I j= Cin. We can now proceed with the semantics of procedures.
De nition 2. Let I be an instance over schema S. An instance I0 over S is a possible outcome of applying procedure P to I if all of the following holds: 1. P is applicable on I; 2. I0 j= Cout; 3. The answers of the query QSnScope do not change: QSnScope(I)
QSnScope(I0); and 4. The answers to each query Q in Qpres over I are preserved: Q(I) = Q(I0).
Example 3 (Example 2 continued). Recall procedure Pmigrate = (Scope; Cin; Cout; Qpres) de ned in Example 2. Consider instance I over schema S with relations EVisits and LocVisits , each with attributes facility , pId , and timestp, as shown in Figure 1 (a). Note rst that Pmigrate is indeed applicable on I. When applying Pmigrate to I, we know from Scope that the only relation whose content can change is LocVisits , while EVisits is the same across all possible outcomes. Further, we know from Cout that in all possible outcomes, the projection of EVisits over the attributes facility , pId , and timestp must be the same as the projection of LocVisits over the same attributes. Finally, from Qpres we know that the projection of LocVisits over these three attributes must be preserved.
Perhaps the most obvious possible outcome of applying Pmigrate to I is that of the instance J1 in Figure 1 (b), corresponding to the outcome where the tuple in EVisits that was not yet in LocVisits is migrated into the latter relation. However, since we assume no control over the actions performed by Pmigrate, it may well be that it is also migrating data from a di erent relation that we are not aware of, producing an outcome whose relation EVisits is the same as in I and J1, but LocVisits has additional tuples, as depicted in Figure 1 (c).
As seen in Example 3, in general the number of possible outcomes that result from applying a procedure is in nite. Thus, we are in general interested in properties shared by all possible outcomes, which motivates the following de nition. De nition 3. The outcome set of applying a procedure P to I is de ned as: outcomesP (I) = fI0 j I0 is a possible outcome of applying P to Ig: The outcome of applying a procedure P to a set of instances I is the union of the outcome sets of applying P to all the instances in I: outcomesP (I) = [ outcomesP (I):
I2I
Finally, to reason about (perhaps repeated) applications of multiple procedures, we extend the de nitions to enable talking about the outcomes of sequences of procedures. The outcome of applying a sequence P1; : : : ; Pn of procedures to instance I is the set outcomesP1;:::;Pn (I) = outcomesPn (outcomesPn 1 ( (outcomesP1 (I)) )): 4
We begin with two decision problems on outcomes of sequences of procedures.
EVisits LocVisits facility pId timestp 1234 33 070916 12:00 1222 33 020715 07:50 2087 91 090916 03:10 (b) Possible outcome J1 of applying P over I
LocVisits facility pId timestp 1234 33 070916 12:00 1222 33 020715 07:50 2087 91 090916 03:10 4561 54 080916 23:45 (c) relation LocVisits in J2 Suppose we wish to apply procedures P1 and P2 to instance I sequentially, rst P1 then P2. To ensure applicability of P2, we need to guarantee that any possible outcome of applying P1 to I will satisfy the preconditions of P2. Hence, we study the following applicability problem: Given schema S and procedures P1 and P2, is it true that P2 can be applied to each instance in outcomesP1 (I), regardless of the choice of I 2 S?
The applicability problem is intimately related to the problem of implication of dependencies (see, e.g., [2{4, 11, 6, 7]). Indeed, consider a class L of constraints for which the implication problem is known to be undecidable. Then if we let P1 be a procedure with a set of postconditions in L, and P2 a procedure with a dependency in L as a precondition, it is not di cult to come up with proper scopes and preservation queries so that the set outcomesP1 (I) satis es for every instance I over schema S if and only if is true in all instances that satisfy .
However, applicability turns out to be undecidable even if we x P1 and P2: Proposition 1. There are xed procedures P1 and P2 that only use tgds for their constraints, and such that the following problem is undecidable: Given an instance I over schema S, is it true that all the instances in outcomesP1 (I) satisfy the preconditions of P2?
The proof of Proposition 1 is by reduction from the embedding problem for
nite semigroups, shown to be undecidable in [
This result suggests that to obtain decidability, it may not be enough to focus on procedures whose pre- and postconditions are speci ed in languages with decidable implication problem | one would need to create stronger restrictions. Consider, e.g., the restriction of disallowing preconditions in procedures, for which we have the following trivial result.
Fact 1 A procedure without preconditions can always be applied to any instance. Nonemptiness: The other important problem is that of determining whether the outcome of a sequence of procedures is nonempty. We remark that even without preconditions, the outcome of a procedure may be empty if it is not possible to transform an instance in a way that would satisfy the postconditions of a procedure, while ensuring that the scope and preservation queries are respected. Perhaps surprisingly, we can show that this problem is undecidable even if we just have one xed procedure.
Proposition 2. There exists a procedure P that does not use preconditions and uses only tgds in its postconditions, such that the following is undecidable: Given an instance I, is the set outcomesP (I) nonempty? The proof of this proposition is similar to that of Proposition 1, but in this case we can get away with one procedure by merging together the postconditions and precondition of the procedures in the reduction for Proposition 1. Procedures with safe scope: Toward obtaining decidability, we could continue restricting the types of constraints we allow in procedures. (For example, nonemptiness is decidable for a broad range of acyclicity conditions.) We choose to adopt a di erent strategy, which restricts the interplay between the postconditions of procedures, their scope, and their preservation queries.
We say that procedure P = (Scope; Cin; Cout; Qpres) has safe scope if the following holds: { Cin is empty, and Cout is an acyclic set of tgds; { The set Scope contains exactly one constraint R[ ] for each relation R that appears on the right-hand side of a tgd in Cout; and { The set Qpres contains one total query R for each constraint R[ ] in Scope.
That is, it binds precisely all the relations in the scope of P .
Note that the procedure Pmigrate of Example 2, while not a procedure with safe scope, can easily be transformed into one. Once again, we have an easy result that makes a case for the good behaviour of procedures with safe scope: Proposition 3. For every instance I and sequence P1; : : : ; Pn of procedures with safe scope, the set outcomesP1;:::;Pn (I), is not empty. 5
We now address the problem of assessing achievability of desired properties of data, which we describe informally as follows. We start with an instance I and have a set of procedures. We are also given a boolean query Q (that intuitively expresses a desired property) that does not hold in I. The question we ask is whether we can apply to I some or all the procedures in so that all the resulting outcomes would satisfy Q: data readiness: Input: An instance I, a set of procedures, and a boolean query Q; Question: Is there a sequence P1; : : : ; Pn of procedures in such that all the instances in outcomesP1;:::;Pn (I) satisfy Q? First negative results: In the previous sections we have seen that most problems in our framework can be solved if we restrict ourselves to procedures with safe scope. Unfortunately, as the following result shows, this is not the case for the data-readiness problem.
Proposition 4. The problem data readiness is undecidable, even if set of procedures with safe scope. is a
The proof is by reduction from the universal halting problem for Turing
machines, along the lines of the proof used in [
Decidability for full tgds: In order to obtain decidability, we further restrict to sequences of procedures with safe scope and given by full tgds only, for which we can show the following result: Proposition 5. The problem of checking whether a boolean query Q holds in all outcomes of an instance I over a sequence P1; : : : ; Pn of procedures with safe scope and given by full tgds only, is decidable and in EXPTIME.
This proposition suggests an algorithm for data readiness: one needs to guess a sequence of procedures, and then check whether the query is entailed in this sequence. Of course, we need a small-model property for the size of the sequence of procedures that we need to guess. Summing up, we have the following result. Theorem 1. For the cases where is a set of procedures with safe scope with output constraints comprising full tgds only, data readiness is in NEXPTIME. 6
In this paper we embark on the development of a framework that allows one to reason about database procedures based only on a high level description of what these procedures do. We have instantiated our framework in a relational setting, and only when procedures are guaranteed not to alter the schema of databases.
The proposed framework presents several opportunities for further research. One line of work would involve understanding how to represent outcomes of sequences of procedures, perhaps by means of knowledge bases or similar artifacts.
We also believe that our framework is general enough to allow reasoning on other data paradigms, or even across various di erent data paradigms. Our black-box abstraction could, for example, o er an e ective way to reason about procedures involving unstructured text data, or even data transformations using machine-learning tools, as long as one can obtain some guarantees on the data outcomes of these tools.