W3C home > Mailing lists > Public > www-rdf-rules@w3.org > November 2003

RE: SeRQL an RDF rule language: scoping Rules vs Query in W3C wor k

From: Seaborne, Andy <Andy_Seaborne@hplb.hpl.hp.com>
Date: Wed, 5 Nov 2003 10:41:25 -0000
Message-ID: <E864E95CB35C1C46B72FEA0626A2E8081ACF9D@0-mail-br1.hpl.hp.com>
To: www-rdf-rules@w3.org

> What do you mean with merging in this context?

Only that if you want a single graph (I don't mind if that graph has
partitions - graphs don't have to be a single connected region) that is the
set of all triples matching the query, not each solution.  That is, merge
the sepoarate solutions together because that gives you a smaller subgraph
of original that has the same query results.

Suppose I have 10 properties p1 (different values!) and 10 properties p2.

The query (<x> <p> ?x) (<x> <p2> ?y) has 100 binding combinations but only
20 triples. 

I wondered if there is a well known faster algorithm for calculating the
matching subgraph (the 20 triples) than finding 100 binding combinations.

	Andy

-------- Original Message --------
> From: Jeen Broekstra <mailto:jeen@aduna.biz>
> Date: 4 November 2003 14:55
> 
> Seaborne, Andy wrote:
> > I'm not quite clear on the query:
> > 
> > Does this query give a sequence of "graphlets", one per soltuion
> > to the FROM clause, or a single graph of all the triples from all
> >  the solutions?
> 
> It returns a single result set, consisting of statements that match
> the from clause. It's not necessarily a single graph because the
> results from different matches may well be disconnected, but there
> is no explicit support for identifying these individual matches, if
> that's what you mean: you get one set of statements that contains
> all answers.
> 
> > Another sort fo related question: in the case where the result of
> >  a query is a subgrapgh of the original, does anyone know of any
> > literature describing algorithms for this subgraph calculation
> > that is faster than simply taking each solution and merging (that
> >  can lead to a lot of unnecessary work)?
> 
> Now I'm confused :) What do you mean with merging in this context?
> Filtering duplicate statements? If so, then I can't help you with
> literature refs from the top of my head, but we have implemented
> this by pushing a DISTINCT modifier down to the SQL engine to filter
> out duplicate variable-binding combinations, and an additional
> triple filter on top of that. We haven't spent too much time on
> optimizing this, but sofar it has not given us any serious
> performance problems. Of course this approach is only used when the
> user specifies a DISTINCT modifier in the SeRQL query, so it might
> just not have come up yet :)
> 
> Cheers,
> 
> Jeen
Received on Wednesday, 5 November 2003 05:45:44 UTC

This archive was generated by hypermail 2.3.1 : Wednesday, 2 March 2016 11:10:14 UTC