satisfies algorithm

Thread view:

Enable EMail Alerts

Start New Thread

Thread rating:

aarklon@gmail.com - 25 Jul 2008 13:41 GMT

Hi all,

the following is the algorithm which i saw in schaum series
book(fundamentals of relational databases)

satisfies algorithm

this algorithm shown below can be used to determine if a relation r
satisfies or does not satisfies a given functional dependency A -> B.
the input to the algorithm is a given relation r and a functional
dependency A -> B. the output of the algorithm is true if r satisfies
A -> B; otherwise the output is false.

1) sort the tuples of the relation r on the A attribute(s) so that
tuples with equal values under A are next to each other

2) check that tuples with equal values under attribute(s) A also have
equal values under attribute(s) B

3) if any tuples of r meet condition 1 but fail to meet condition 2
the output of the algorithm is false. otherwise, the relation
satisfies the functional dependency and the o/p of the algorithm is
true.

now my question is there any other better method (other than inference
axioms) ?

Reply to this Message

Brian Selzer - 25 Jul 2008 13:54 GMT

> Hi all,
>
[quoted text clipped - 22 lines]
> now my question is there any other better method (other than inference
> axioms) ?

Yes. Normalize. A schema that is in BCNF does not have any nontrivial
functional dependencies where the determinant is not also a key. Where
there is a key, there should also be a unique index of some sort, making it
impossible for there to be two tuples with the same determinant.

Reply to this Message

David Portas - 26 Jul 2008 10:31 GMT

> Yes. Normalize. A schema that is in BCNF does not have any nontrivial
> functional dependencies where the determinant is not also a key. Where
> there is a key, there should also be a unique index of some sort, making
> it impossible for there to be two tuples with the same determinant.

Unique indexes have nothing to do with keys. A key is a logical construct
whereas an index is merely one possible physical structure used by some
DBMSs. A key does not require an index.

Signature

David Portas

Reply to this Message

Brian Selzer - 26 Jul 2008 14:12 GMT

>> Yes. Normalize. A schema that is in BCNF does not have any nontrivial
>> functional dependencies where the determinant is not also a key. Where
[quoted text clipped - 4 lines]
> whereas an index is merely one possible physical structure used by some
> DBMSs. A key does not require an index.

Keys have the uniqueness property. Don't you agree that the uniqueness
property should be enforced by whatever implementation is chosen? I think
you would be hard pressed with today's technology to find a more efficient
implementation method to enforce the uniqueness property than maintaining an
index--especially when a relation has more than one key.

Reply to this Message

David Portas - 26 Jul 2008 19:40 GMT

>>> Yes. Normalize. A schema that is in BCNF does not have any nontrivial
>>> functional dependencies where the determinant is not also a key. Where
[quoted text clipped - 7 lines]
> Keys have the uniqueness property. Don't you agree that the uniqueness
> property should be enforced by whatever implementation is chosen?

Yes of course.

> I think you would be hard pressed with today's technology to find a more
> efficient implementation method to enforce the uniqueness property than
> maintaining an index--especially when a relation has more than one key.

This is a different thing from saying there "should" be a unique index for a
key. Some DBMSs don't even have the concept of indexes (Netezza comes to
mind). Whether a database has indexes or not has nothing to do with whether
keys are enforced.

Signature

David Portas

Reply to this Message

Cimode - 27 Jul 2008 00:28 GMT

On 26 juil, 19:40, "David Portas"
<REMOVE_BEFORE_REPLYING_dpor...@acm.org> wrote:

> >>> Yes. Normalize. A schema that is in BCNF does not have any nontrivial
> >>> functional dependencies where the determinant is not also a key. Where
[quoted text clipped - 18 lines]
> mind). Whether a database has indexes or not has nothing to do with whether
> keys are enforced.

I confirm. The era of SQL dbms's is coming to an end as they simply
can not cope anymore with the incredible amount of *physical*
duplicate data and their unability to perform low level ra operations.

Newcomers and old niche market actors using different physical
encoding schemes than direct image encoding becoming more industry
relevant via the buzz of datawarehousing and business intelligence:
Netezza, Cognitio, Sand Technology, DataAllegro (which was recently
purchased by Microsoft for the next version of SQL Server)...The
success of these actors demonstrate the limits and fragility of the
current SQL based systems by obtaining success only by obtaining the
better response times.

As for myself, I developped a new encoding scheme and computing model
that totally takes away the need for indexes. The model by optimizes
ra operations at physical level in a way I have not observed before.
The subsequent developped db core shows promising results and allows
to perform operations that would be simply IO unthinkable on a direct
image system: After all, on relations representations that contain
2billion tuples and more, I obtain lower response times on a 7200rpm
dual core cpu desktop than on an 15000 rpm octo core monster loaded
with Oracle and/or SQL Server without the need for a single
index.

Indexes are indeed the direct consequence of industry lazyness to
implement computing models that support adequately ra operations and
*not* consequences of the RM itself which is a different layer. I
would go even further as saying that any direct image system can *not*
be a trdbms, ever since it has fundamental limitations that increase
as the number of tuples represented increases.

Finally the experience of building the model confirmed that a TRDBMS
can simply not exist unless the following equation is finally
resolved:

TRDBMS = RM + RA Computing model + RA optimized encoding scheme + RA
manipulation/definition language

IMHO.

Regards

Reply to this Message

Brian Selzer - 27 Jul 2008 04:22 GMT

>>>> Yes. Normalize. A schema that is in BCNF does not have any nontrivial
>>>> functional dependencies where the determinant is not also a key. Where
[quoted text clipped - 19 lines]
> mind). Whether a database has indexes or not has nothing to do with
> whether keys are enforced.

In nearly all of the commercial implementations and implementations of
systems built with commercial implementations that pervade the industry,
where there is a unique constraint or a primary key constraint that needs to
be enforced, there is also an index. But thank you for pointing out that
there are alternatives to using indexes without also providing the
algorithms for those alternatives for the OP's edification. In other words,
"where's the beef?" Can you back up your claims with more than marketing
hype? I read the white papers Netezza provided on their web site, but I
didn't feel a thrill going up my leg, if you know what I mean. Can you
provide links to academic papers that describe these alteratives in detail.
I'm curious, and I would bet that others here are too.

By the way, how Netezza is implemented internally is anyone's guess. They
may sort active domains--storing them in a particular order. Who knows?
but wouldn't that be similar enough to be considered a facsimilie of an
index?

--Brian

Reply to this Message

David Portas - 27 Jul 2008 11:14 GMT

> In nearly all of the commercial implementations and implementations of
> systems built with commercial implementations that pervade the industry,
[quoted text clipped - 14 lines]
>
> --Brian

I had hoped I wouldn't need to explain that it is possible to validate
uniqueness without an index. For example some DBMSs will allow you to use a
trigger or an assertion to enforce uniqueness. An index is simply a method
for speeding that process up. In any case I don't expect discussions about
fundamental matters to be limited to what "nearly all of the [current]
commercial implementations" can support. The facts are what they are
regardless of what Microsoft, Oracle, et al are selling. A key is a logical
construct and an index is a physical one.

I'm really not sure what "claims" you want me to back up since you've
already agreed that an index isn't always required (quote: "In nearly
all..."). If you mean you want to know about optimisation strategies that
don't involve indexes then you could start here: http://tods.acm.org/. There
is a wealth of material on optimisation. Optimisation has nothing to do with
keys of course, which brings us back to where we started...

Signature

David Portas

Reply to this Message

Brian Selzer - 27 Jul 2008 16:00 GMT

>> In nearly all of the commercial implementations and implementations of
>> systems built with commercial implementations that pervade the industry,
[quoted text clipped - 18 lines]
> I had hoped I wouldn't need to explain that it is possible to validate
> uniqueness without an index.

Of course you can validate uniqueness without an index: you can simply scan
the entire relation every time you do an insert or update (anyone with half
a brain could figure that out), but with a billion rows, that could be both
time and resource intensive.

> For example some DBMSs will allow you to use a trigger or an assertion to
> enforce uniqueness. An index is simply a method for speeding that process
[quoted text clipped - 3 lines]
> Oracle, et al are selling. A key is a logical construct and an index is a
> physical one.

The facts are what the liberal media say they are. I thought you knew that.

A key has the uniqueness property. Enforcing the uniqueness property of a
key without scanning the entire relation every time an insert or update
occurs requires implementing some form of indexing--whether that be a hash
index or table or a b-tree index or storing active domains as ordered sets
(or some facsimilie thereof, such as binary trees) or storing the relation
itself as an ordered set (making it its own index, but that only works if
the relation has only one key).

Prove me wrong.

> I'm really not sure what "claims" you want me to back up since you've
> already agreed that an index isn't always required (quote: "In nearly
> all..."). If you mean you want to know about optimisation strategies that
> don't involve indexes then you could start here: http://tods.acm.org/.
> There is a wealth of material on optimisation. Optimisation has nothing to
> do with keys of course, which brings us back to where we started...

I was hoping for more than a link that I already have in my favorites.

I notice that you didn't find fault with the meat of my original post, which
was to normalize so that there can be no nontrivial functional dependencies
where the determinant is not also a key. Why nitpick over the stupid stuff?
I'll rephrase the last part of my original response: There should already be
a mechanism in the dbms to ensure that keys are unique. Usually, that is
accomplished through the use of unique indexes. Happy? My point was that a
sound design obviates the need for a functional dependency enforcement
algorithm. It should be noted that the least efficient algorithm for
enforcing uniqueness--that is, scanning every row each time that there is an
insert or update--is more efficient than the algorithm that the OP supplied
due to the elimination of the sort.

Reply to this Message

David Portas - 27 Jul 2008 16:57 GMT

> I'll rephrase the last part of my original response: There should already
> be a mechanism in the dbms to ensure that keys are unique. Usually, that
> is accomplished through the use of unique indexes. Happy?

Perfectly happy. Same point I was trying to make.

Signature

David Portas

Reply to this Message

Cimode - 27 Jul 2008 11:35 GMT

[Snipped]

> In nearly all of the commercial implementations and implementations of
> systems built with commercial implementations that pervade the industry,
[quoted text clipped - 4 lines]
> "where's the beef?" Can you back up your claims with more than marketing
> hype?

There is really *no beef* but simply the application of sound
relational concepts onto determining a computing model and encoding
scheme that preserves physical logical independence. The fact that
there is no need for indexes is just one of many good side effects of
the underlying research effort that started many years ago.

I would like to point out that I brought up the example of the db core
I am working simply in good faith to support David's underlying claim
that physical data independence (and therefore index independence) is
anything but utopia. I am not planning making money out of it since
it will be open source once the core is completed and relationally
sound. I plan on documenting and making available to public the
computing model, encoding scheme and algorhythmics only at that
point. I am still working out the issues of temporal data and missing
information without use of NULLS.

> I read the white papers Netezza provided on their web site, but I
> didn't feel a thrill going up my leg, if you know what I mean. Can you
> provide links to academic papers that describe these alteratives in detail.
> I'm curious, and I would bet that others here are too.

Products such as Netezza are simply an old idea rediscovered. Google
up *column store*. For more information about Netezza, contact Netezza
people.

> By the way, how Netezza is implemented internally is anyone's guess. They
> may sort active domains--storing them in a particular order. Who knows?
> but wouldn't that be similar enough to be considered a facsimilie of an
> index?

Depends how you define an index. `Direct image indexing schemes are
primarily based on the concepts of address pointers associated with
some kind of querying scheme(bitmap, b-tree) to allow the system to
determine as fast as possible (as little logical operations) where the
data is on disk.

> --Brian

Reply to this Message

Cimode - 26 Jul 2008 15:28 GMT

On 26 juil, 10:31, "David Portas"
<REMOVE_BEFORE_REPLYING_dpor...@acm.org> wrote:

> > Yes. Normalize. A schema that is in BCNF does not have any nontrivial
> > functional dependencies where the determinant is not also a key. Where
[quoted text clipped - 4 lines]
> whereas an index is merely one possible physical structure used by some
> DBMSs. A key does not require an index.

Typical confusion between logical layer and physical layer.
Algorhythmics has more to do with physical encoding scheme and
implementation computing model. Direct image systems do create that
kind of confusion as well as the normative ignorance of RM.

> David Portas

Reply to this Message

David Cressey - 28 Jul 2008 17:58 GMT

> > Yes. Normalize. A schema that is in BCNF does not have any nontrivial
> > functional dependencies where the determinant is not also a key. Where
[quoted text clipped - 4 lines]
> whereas an index is merely one possible physical structure used by some
> DBMSs. A key does not require an index.

True in theory, but very misleading to any newbies who may read it.

A declared primary key with no index to back it up is generally a
performance nightmare.
Enforcing uniqueness of keys without an index requires a full table scan.
For this reason most DBMS builders provide an automatic index when a primary
key is declared.

To be sure, the concept of "key" and "primary key" are different concepts.
Also a key would be a key, even if it were undeclared.

Relying on a key that is not declared either via a PRIMARY KEY constraint or
UNIQUE and NOT NULL constraints, is an invitation to database damage done
by a rogue process, possibly as the result of carelees programming coupled
with data.

Newbies need to understand all this.

Having said this, I repeat that you original comment is correct in theory.
And this is, after all, the database theory newsgroup.

Reply to this Message

Bob Badour - 28 Jul 2008 18:58 GMT

>>>Yes. Normalize. A schema that is in BCNF does not have any nontrivial
>>>functional dependencies where the determinant is not also a key. Where
[quoted text clipped - 9 lines]
> A declared primary key with no index to back it up is generally a
> performance nightmare.

The problem with generalizations is they are invariably wrong. Indexing
a relation that fits on a single database page is almost always a
performance nightmare. Relatively speaking.

> Enforcing uniqueness of keys without an index requires a full table scan.

Which is very fast for small tables.

> For this reason most DBMS builders provide an automatic index when a primary
> key is declared.

Sadly, true.

> To be sure, the concept of "key" and "primary key" are different concepts.
> Also a key would be a key, even if it were undeclared.
[quoted text clipped - 8 lines]
> Having said this, I repeat that you original comment is correct in theory.
> And this is, after all, the database theory newsgroup.

His original comment was correct in all respects.

Reply to this Message