Oracle FAQ Your Portal to the Oracle Knowledge Grid
HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US
 

Home -> Community -> Usenet -> comp.databases.theory -> Re: organizing tables?

Re: organizing tables?

From: Bob Badour <bbadour_at_golden.net>
Date: Thu, 17 Jul 2003 23:25:37 -0400
Message-ID: <FJKRa.969$za.162044036@mantis.golden.net>


"Paul Vernon" <paul.vernon_at_ukk.ibmm.comm> wrote in message news:bf6ppj$1i16$1_at_gazette.almaden.ibm.com...
> "Bob Badour" <bbadour_at_golden.net> wrote in message
> news:3shRa.895$uN3.149846029_at_mantis.golden.net...
> [snip]
> > > By the information principle, (for any given user) nothing can be
hidden
> > > unless it is completely hidden.
> >
> > I don't think I agree with your interpretation of the information
principle.
>
> I do overload it sometimes, but that is partly because it is *the key*
> principle.
>
> > I don't recall seeing the "for any given user" part in any other
statement
> > of the principle.
>
> No indeed, because no-one (to my knowledge & me included) has attempted to
> find a model of *users* and see how that impacts the relational model.
>
> > Ideally, the dbms would express every constraint on a relvar as a
visible
> > predicate rephrasing each constraint as necessary to avoid references to
> > hidden items; however, the dbms would have to solve provably hard or
even
> > unsolvable problems to do so. Compromises to avoid provably hard
problems
> > are pragmatic applications of theory.
>
> If compromises are required in any conceivable application of a theory,
than
> that theory is broken and it needs to add consideration for such
compromises
> and *bring them into the model*.

If you don't want to compromise in the face of the halting problem, more power to you but don't expect me to join you. Your desire to avoid compromises will not make the halting problem go away. Regardless, I don't see what is broken about computability theory.

> I made up a term for that idea. I call it 'Logical Practicality'.

I don't think you understood which theory I applied pragmatically.

> > (I miss Jan. I wonder whatever happened to him. I am sure he could rhyme
a
> > half-dozen relevant references off the top of his head.)
>
> So do I. I'm sure he would respond to a email though.
>
> > > Either 'unseen relations' have zero impact on
> > > a database (or 'database view') or the relations are not unseen at
all...
> >
> > Ideally, every user should see an appropriate representation of every
> > constraint without violating security; however, this will run us into
> > NP-complete and solvability problems.
>
> Yes but that's the problem with narrow theory. Complexity is a problem of
the
> general case. It means you can't guarantee to find the correct answer to
every
> instance of a problem.
> A logically practicable theory does need to recognise such problems, but
it
> should also recognise that in specific cases problems are often solvable,
or
> that users don't care it the solution is perfect, just as long as it is
good
> enough.

Are you arguing in support of hidden constraints and hidden updates as good enough even if not perfect?

> By rights, auto-route should not be possible because you can guarantee to
find
> the shortest route - that's NP complete. Doesn't stop software finding
very
> short (but maybe not shortest) routes however.

I don't see what this has to do with whether the dbms must express to the user every constraint that might affect a user prior to the user encountering it at runtime. (ie. no hidden constraints)

> > > > > 2) everything that is not constrained can be updated (i.e. no
> hidden
> > > > > constraints)
> > > >
> > > > This is impossible in practice without destroying either integrity
or
> > > > security.
> > >
> > > Wrong.
> > >
> > > If you do not wish to include all the referneced relvars in the user's
> view of
> > > the database, then you must not allow users the ability to update any
> parts of
> > > the database that reference the hidden relvars.
> >
> > I disagree with "must not." This is a design issue. If one does not
allow
> > users to update relvars that might have "hidden" constraints, the user
will
> > never encounter any surprising constraints or surprising behaviour.
>
> > However,
> > the restriction may prevent users from many desirable or even necessary
> > interactions. Under the right circumstances, I would happily give users
a
> > small chance to surprise themselves.
>
> I just can't see how you can belive in theory, but say it OK to throw it
away
> when things get 'too difficult'.

I believe in more than one theory. I prefer not to ignore the halting problem.

> > > I absolutely reject the idea that a user cannot know a-priori that a
given
> > > update will 'work' or not.
> >
> > Until you present a solution for the computationally hard problems you
have
> > given yourself, I suggest you refrain from imposing them on others.
>
> OK, my 'solution' (assuming there is a problem here) is to throw the
problem
> to the DBMS 'safety system'. This would trap any user request "know
a-priori
> that a given update will 'work' or not" that would (or does) break a
safety
> limit, and report back to the user that "sorry, can't actually calculate
that
> in reasonable time".

You have just given your safety system the task of solving the halting problem.

> Then the user can either redesign the database schema to make the question
> possible for the DBMS to calculate, or they could upgrade to a faster box,
or
> to another DBMS etc. At last resort they just accept that the update might
> fail.
> So maybe my rule should be restated slightly:
>
> I absolutely reject the idea that a user cannot classify all their
updates
> into those guaranteed to work and those not guaranteed to work

Your absolute rejection won't change anything or solve the halting problem.

> > > Hidden constraints remove the possibility of giving users such
confidence.
> >
> > Disallowing updates to any relvar that might have a chance of imposing a
> > hidden constraint removes the possibility of giving users adequate
logical
> > independence.
>
> You know or are you just guessing?

I know. While not the exact situation, I believe the following reference deals with a similar problem:
http://citeseer.nj.nec.com/paulley94exploiting.html

One may come up with algorithms that transform some constraints such that they no longer mention hidden relvars, but the general case is a hard problem. In fact, I suspect it is fairly easy to prove that one cannot describe some simple constraints without explicit reference to a specific relvar. Even if the security function prevents one from spelling out the constraint to a user, the dbms can still enforce it.

> [snip]
> >
> > Given that the hidden audit trail was hidden, constrained and updated,
how
> > does it fail to provide a counter example to the rules "no hidden
updates"
> > and "no hidden constraints"?
>
> Simply because these updates and constraints are outside the database that
the
> manager sees as *the* (i.e his) database.

It is wrong to assume it was impossible for the manager to attempt to violate any of the transition constraints on the basis of no attempt. He was not able to see the other audit trail directly. He never tried to violate any of the transition constraints the dbms enforced, which is the equivalent of not looking.

> > > The superset
> > > has the constraint that deletions from the audit trail cause
insertions in
> > the
> > > audit trail trail. This constraint does not need to be made visible
to
> > the
> > > manager because of the mapping rule between his database view and the
> > super
> > > view. That mapping rule is basically a set of triggered actions on
audit
> > > trail.
> >
> > Whether the mapping rule is a set of triggered actions or a view
definition
> > seems irrelevant. The hidden audit trail has transition constraints
> > referencing the relvars the manager directly updated to cause the hidden
> > updates. The arbitrary restrictions you want to impose basically say
that
> > the designer may not declare the transition constraints to the dbms
without
> > either revealing the hidden audit trail or making the visible relvars
> > read-only.
>
> No it doesn't. Read it again and think about which database subset each
user
> (including 'the' designer) considers *the* (i.e. his) database.

I have thought about it. The example involves both hidden updates and hidden constraints. If the manager violated a transition constraint that references the relvars he manipulates and the relvars hidden from view, the dbms would have to balk even though the security function prevents the dbms from mentioning the hidden relvars.

The triggered procedures might force every transition to match the constraint, or they might not. In general, the dbms won't be able to decide whether this is the case; although, it might be able to decide some or even most of the time.

Consider a situation where the dbms is upgraded and where the upgrade includes an additional algorithm that would determine whether a specific triggered procedure will guarantee a constraint.

On the basis of this algorithm, the dbms might conclude it does not need to enforce a specific constraint because it now knows the data can never violate it. (i.e. the dbms has a proof that the constraint always evaluates to true for a specific update.) The dbms might run faster, but there is no change in logical behaviour because the update never could violate the constraint even when the dbms tested for it during the update.

Consider the situation with your 'safety system'. Prior to the upgrade, the dbms lacks the ability to know whether to enforce the constraint and might conclude it is too expensive to decide the matter. (ie. the dbms balks on a specific update) After the upgrade, the dbms allows the update. The addition of a new optimization algorithm should not change the logical behaviour of the dbms.

The 'safety system' approach you propose above will cause the logical behaviour to change even though the logic remains the same. Received on Thu Jul 17 2003 - 22:25:37 CDT

Original text of this message

HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US