view update in logic and relational databases
Sampo Syreeni
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!
paul c
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)..
rpost
>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.
This has been studied extensively ...
[...]
>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.
Another is performance - answering queries must be feasible.
>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.
It doesn't, but you have to go beyond predicate logic because
it isn't powerful enough.
See e.g.
http://infolab.stanford.edu/~ullman/cs345-notes.html
(not that I have read all of those)
--
Reinier