view update in logic and relational databases

From: Sampo Syreeni <decoy_at_iki.fi>
Date: Sun, 23 Aug 2009 10:04:51 -0700 (PDT)
Message-ID: <f0aa3f81-c79d-4906-95bf-4077ec2a7a2b_at_b15g2000yqd.googlegroups.com>



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! Received on Sun Aug 23 2009 - 12:04:51 CDT

Original text of this message