[Mulgara-dev] Re: Blank nodes in queries (was: Recent commits to Mulgara.)

Andrew Newman andrewfnewman at gmail.com
Sat Oct 7 09:50:13 UTC 2006


On 10/7/06, Paul Gearon <gearon at ieee.org> wrote:
>
> On Oct 6, 2006, at 9:42 PM, Andrae Muys wrote:
> > * Pattern-Compliement - the exclude() pattern-type.  To be honest I
> > don't know why we need this.  When Paul and Andrew were working on
> > ensuring we could support RDFS/OWL they assured me it was required,
> > so I made sure I provided it.
>
> Just to be clear here... I do NOT see the point in this operation.
> If I once argued for it, then I believe I was in error.  I do recall
> arguing with Andrew over the need for it, and my position then was
> that we do not.
>
> My opinion on this may be different if RDF had negation as failure,
> but I'd have to consider this carefully before committing to that
> point of view.
>
> > * Relational-Difference - the MINUS keyword.  Some of the rules in
> > RDFS are expressed in terms of excluding certain classes of term,
> > and the alternatives we faced were either an O(n) filter - or a O
> > (log n) difference.  Scalability is our top priority, only
> > correctness is more important to us.  So we added another
> > relational operator to our query language.
>
> This is the required operation rather that the complement mentioned
> above.
>

So I'd thought I'd just briefly de-lurk as my names been mentioned a
bit and it'd be good if I could conclusively put to rest the EXCLUDE
operator.  I'm not presenting my own information (as I think I've made
enough attempts previously) this is Date and Darwen, "Databases, Types
and the Relational Model, The 3rd Manifesto", 3rd edition pp
361,363-364:

"We include a relational complement operator, <NOT>.  The availability
of <NOT> allows us to drop the relational difference operation
(MINUS), since that operator can be expressed in terms of <AND> and
<NOT>."

"Let WORKS_IN be a relation with attribute E and D, where E is an
employee and D is a department, and let the corresponding predicate be
"Employee E works in department D."  The the logical complement
(<NOT>) of this relation has a body that consists of all possible
tuples of the form <E,D> such that it is not the case that employee E
works in department D."

"...Let WORKS_ON be a relation with attributes E and J, where J is a
project; and let the predicate corresponding to WORKS_ON be "Employee
E works on project J...we first project WORKS_ON over E and then we
take the <NOT> of that project; the corresponding predicate is "There
does not exist a project such that employee E works on that project."
The relation can then be joined with WORKS_IN, and the projected over
E, to obtain the desired final result."

I don't know if this bit is still in iTQL to do it though.  Paul and I
made a reference to it an age ago [1][2].  There was also some example
queries in the old iTQL docs about potentially useful queries (no idea
if people have really found them useful or not) [3].

This comes in a chapter where he proposes a relationally complete
algebra (A) down to 5 operations (or 3 if NOT, AND and OR are
collapsed into one (NOR or NAND)).  So as far as fundamental
operations go EXCLUDE, <NOT> or complement is one (or part of one) and
I'd say it has use (if for not other reason than that).

AFAIK, this is all assuming normal relational semantics so while it
can't be used for negation as failure in OWL-DL it can be used in
traditional (?) DL (where the instances are countable and discrete)
for example.  I'm wondering if these kinds of operations are useful
for non-OWL systems - Datalog/tableux reasoning and the like built on
RDF [4].

I'm not defending what was implementated (although I do remember when
I was writing it I tested it pretty well [5]) or that the iTQL syntax
was very good.

Tutorial D has (p372):
r1 MINUS r2 which is semantically equivalent to r1 <AND> (<NOT> r2).

JRDF's SPARQL implementation doesn't implement MINUS using <AND> and
<NOT> and the way I'd express it would probably be with MINUS like
syntax too.

[1] http://gearon.blogspot.com/2004/09/documentation-majority-of-today-was.html
[2] http://morenews.blogspot.com/2004/09/not-is-no-more.html
[3] http://www.kowari.org/oldsite/187.htm#o2768
[4] http://www-db.research.bell-labs.com/user/pfps/publications/stack.pdf
[5] https://mulgara.org/svn/mulgara/trunk/src/jar/tuples/java/org/mulgara/store/tuples/ConstrainedNegationTuplesUnitTest.java



More information about the Mulgara-dev mailing list