Re: view update in logic and relational databases

From: paul c <toledobythesea_at_oohay.ac>
Date: Sun, 23 Aug 2009 20:02:05 GMT
Message-ID: <1fhkm.40408$Db2.12669_at_edtnps83>



Sampo Syreeni wrote:
> Like most people around here, I periodically return to the view update
> problem. I also subscribe to the idea that relational databases are
> fundamentally about predicate logic, and that a proper interpretation
> of the update problem probably has to be explained in logic terms. So
> I'd like to offer one purely logical solution to the problem.
>
> As an example, let's take insertion into a view C defined as A union
> B. In predicate logic the view denotes p(A) or p(B), and given the
> precise extensions of p(A) and p(B) we can calculate C. If I was to
> insert a novel tuple into C, that would then amount to asserting a
> disjunction. That does not tell us what the proper extension in terms
> of A and B should be: inserting into one, or the other, or both of the
> relations. So we run into the view update problem.
>
> I believe that is a simple result of keeping to relational databases
> where the set of underlying predicates that comprise the extension of
> the database is fixed at schema design time. If we're forced to
> fundamentally express all data in terms of the extensions of the base
> relations, we're naturally left with a number of update problems once
> we operate directly against logical consequents of those base
> relations. That means that while relational databases are *based* on
> predicate logic, their data model does not *fully* capture the logic
> (only the query language does), which is the basic reason why view
> update is intractable.
>
> Instead in pure predicate logic, and by extension a fully logic
> database, all finite logical expressions are held to be equal and can
> be both asserted and negated independently. We can assert (p(A) or p
> (B)) quite without asserting either of p(A) or p(B) in addition, as
> long as all state inconsistent with the new assertion is purged (i.e.
> integrity constraints/the excluded middle are upheld). The update
> problem vanishes.
>
> Of course, that sort of approach only works in the context of the open
> world assumption, and consequently makes our logic constructive (i.e.
> not everything that could be true can be shown to be such). And it's
> bound to get rather complicated/computationally heavy: there is no
> inherent reason why you shouldn't be able to assert or negate
> arbitrary formulae and expect the database to cope (which is
> equivalent to updating an arbitrary view defined at query time).
>
> But hey, if you're e.g. trying to assert a disjunction or negate a
> conjunction, you're already trying to work according to rules that go
> against the closed world assumption, in the context of which you're
> expected to know precisely what the state of your base relations will
> be!

That's a nice description of the conventional obstacle. Relational logic requires that we must be able to record extensions, not just intensions and unnamed propositions. I'd say the main aspect of the RM that 'goes against' the unaderalted application of predicate logic is that many disjunctions can't even be expressed by a single relation, view nor base. This shows up every time one inserts to a base relation variable. Yet we use disjunction all the time to form such 'base' conjunctions. Seems a little perverse for implementations to allow all those 'base' inserts and not ones to a union view. When operations are restricted to an operand form wihich is a single relation that expresses only conjunctions, we can't have our cake and eat it too. The alternative is that disjunction means one thing when a base is involved and something else when a view is involved, effectively adding another fundamental operator..

I think a more important question is whether a 'relational logic' that deals with views as well as it deals with base variables is somehow inconsistent or leads to contradictory conclusions. Such a logic might not be comparable with traditional logic, but I'd say consistency is the more important quality for interpretation and optimization. I think it is most important to ask what a particular choice of logic buys us and what it doesn't, even if that might lead to a distortion of predicate logic. What it buys us is probably subjective, personally I'd rather have logical independence (I'm not sure if that simply means the limited 'interchangeability' that CJ Date has mentioned).. Received on Sun Aug 23 2009 - 15:02:05 CDT

Original text of this message