Re: Proving an Upgrade is Possible

From: Jan Hidders <jan.hidders_at_REMOVETHIS.pandora.be>
Date: Tue, 07 Jun 2005 21:36:16 GMT
Message-ID: <krope.113585$0R6.6573102_at_phobos.telenet-ops.be>

Kenneth Downs wrote:
> Jan Hidders wrote:

>>Kenneth Downs wrote:
>>>Jan Hidders wrote:
>>>
>>>>Ok, so I suspect are you asking the following:
>>>>
>>>>"Given the old database schema and a few updates to its constraints (but
>>>>not its structure) is it possible to algorithmically decide (or
>>>>mathematically prove) whether all instances of the old schema are also
>>>>instances of the new schema?"
>>>>
>>>>I leave it to you whether it is "algorithmically decide" or
>>>>"mathematically prove".
>>>
>>>You are on target, except that constraints are included, and also
>>>automation
>>>(columns like price_extended = price * qty).  So while we are at it, this
>>>means things like NULL/NOT NULL rules, DEFAULT values and so forth.
>>
>>What do you mean by "constraints are included"? Those were already
>>included in my formulation. Since you only care about whether instances
>>are valid or not, automation can in this case be regarded as a special
>>case of constraints. Default values are completely irrelevant for your
>>question because they do not change the set of allowed valid instances.

>
> To provide an analytic and deterministic answer to the viability of any db
> change, you must consider constraints, null rules, and defaults.
>
> Consider this case. Add two columns to a table, COL_A and COL_B, with the
> constraint that COL_A < COL_B. One has a default value, the other does
> not, and they may not be null. What on Earth do you do to satisfy these
> requirements in the rows that already exist in the table?

You don't. In this case the specification of the schema update is incomplete because the new instance for the new schema is not completely determined. There are actually two problems that you would like to be able to decide in advance. The first is whether the new instance is actually fully determined or not. The second is (presuming the first is answered positively) whether the new instance always is a valid instance of the new schema.

To what extent these problems are solvable or not depends upon a lot of details such as if you consider each schema update as a sequence of atomic updates or as one big update, but also the nature of the constraints that are allowed or the type of queries that may be used for derived columns/tables. So until you give an idea of what your update language and its semantics are, how the constraint language looks what type of queries you allow for derived data it's hard to give a meaningful answer to your question.

> upgrade will succeed. I did not choose your term "algorithmically decide"
> because it is not a step-by-step code thing, the validity or invalidity of
> the state change should be captured in the state of the meta-data. For the
> same reason I did not choose your term "mathematically prove". Demonstrate
> by Analysis seems closer to the mark because we want to examine (or
> analyze) the meta-data.

I suspect that what I describe as "mathematically prove" is the same as your "analyze". It simply means using some kind of formalism (set theory, logic, calculus, whatever) to derive true statements about the formal object you are studying. Note that for certain problems for which there is no finite axiomatization this is in a certain sense sometimes not possible.

• Jan Hidders

Received on Tue Jun 07 2005 - 23:36:16 CEST