Re: Transitive Closure with XDb1

From: Paul <paul_at_test.com>
Date: Wed, 12 May 2004 11:34:41 +0100
Message-ID: <%4noc.3394$NK4.266295@stones.force9.net>

Neo wrote:

>>Leandro said: You are 30 years late. Relational is declarative.

>
>
> XDb1's interface allows data to be entered via three methods: API, GUI
> and "Natural Language Interface" (NLI). The below statements enter the
> equivalent data "declaratively":
>
> ------------------------
> person isA thing.
> john isA person.
> mary isA person.
>
> planet isA thing.
> mars isA planet.
> venus isA planet.
>
> universe isa thing.
>
> mars isPartOf universe.
> john isPartOf mars.
>
> venus isPartOf universe.
> mary isPartOf venus.
> ------------------------
>
> Could you show RDM's "declarative" equivalent?
> Could you show RDM's transitive closure equivalent?

create table Contains (

whole char
part char
)

insert into Contains values ('mars', 'john')
insert into Contains values ('venus', 'mary')
insert into Contains values ('universe', 'mars')
insert into Contains values ('universe', 'venus')

Now the standard relation model can't do transitive closure because it requires more than first order logic.

But we can extend our DBMS by explicity including a "TClose" operator that takes a (two-columned) relation as its argument and returns a relation that is the transitive closure.

I'm not certain here (maybe someone can correct me if I'm wrong) but I think first-order logic + transitive closure operator lies somewhere inbetween first and second order logic.

Then TClose(Contains) is:

whole part
===== ====
universe john
universe mary
universe mars
universe venus
mars john
venus mary

You might say this is cheating, but one of the rationales behind the relational model is to make the user queries declarative, and push the technical implementation details inside the DBMS.

I'm not sure which existing DBMSs have a transitive closure operator. You'd think it would be more common because it would seem to be a popular requirement to deal with hierarchies like this.

Paul. Received on Wed May 12 2004 - 05:34:41 CDT