Re: RDF Graphs

Or, restating Carroll (2003)[?], comparing sets of RDF triples *without
blank nodes* is O(n log(n)), but graphs containing certain evil blank node
patterns are harder.

It's not clear from the presentation in this paper the degree to which the
graph metaphor helped inspire the development of the algorithm (the only
graphs in the paper are in the section illustrating isomorphism.  All RDF
is presented as triples or as RDF/XML.

It does seem that all that was required from the Carroll (2001) was a
summary of the  result, and presenting the RDF examples in a graphical form
in the 2003 ISWC paper was not necessary (Figure 1. being an acceptable
layer-cake replacement).

This seems different to situations where you're thinking about hierarchies,
etc, where it is hard to think about problems without drawing some sort of
graph on one's mental whiteboard (though I may be the only person who has
to write DNE).

 Simon

Carroll, J. J. (2001). *Matching RDF graphs*. HP LABORATORIES TECHNICAL
REPORT HPL 293. Available at:
http://www.hpl.hp.com/techreports/2001/HPL-2001-293.pdf

--  (2003).  *Signing RDF graphs*. In The Semantic Web-ISWC 2003 (pp.
369-384). Springer Berlin Heidelberg. Available at:
http://www.hpl.hp.com/techreports/2003/HPL-2003-142.pdf?jumpid=reg_R1002_USEN



On Wed, Oct 29, 2014 at 3:46 PM, Jeremy J Carroll <jjc@syapse.com> wrote:

> Late to the party, my 2c is that an RDF Graph has enough in common with a
> mathematical graph for the name to be useful, and more useful than using a
> term like RDF Set.
>
> As an example of applying the mathematics is my result that comparing RDF
> Graphs for syntactic equivalence is Graph Isomorphism complete (which is a
> weird complexity class between P and NP, strictly between iff P != NP)
>
> Pictures of RDF Graphs and a pictures of mathematical graphs do have quite
> a lot in common, and this reflects an underlying commonality in the
> thinking.
> The labels are perhaps less important than the unlabelled nodes (which
> cannot come in predicate position)
>
> Jeremy
>
>
>
>
> > On Oct 28, 2014, at 8:33 AM, Hugh Glaser <hugh@glasers.org> wrote:
> >
> > Thanks All,
> >
> >
> > So here is where I got to:
> > The term being used is ‘RDF Graph’, not ‘RDF’ ‘graph’, and this makes
> all the difference, because we define ‘RDF Graph’ to be what we say it is.
> >
> > And this is how I think it now goes:
> >
> > When I explain RDF to people, and talk about graphs, I think they
> usually use the graph word, and use the term to visualise something with
> nodes and edges, just like the pictures I draw when I I explain to them.
> > And everyone is happy.
> > Then I tell them (or the wise son realises) that in fact because URIs
> can appear in all the positions, things might be a little different.
> > What I used to say was “Don’t worry, you are right, it isn’t actually
> the sort of graph you thought it was and I showed you, but never mind, most
> of the time it is really helpful to think of it as such a graph, especially
> when you do SPARQL stuff, for example. I hope you don’t feel mislead! And
> when the graph thing doesn’t work, then just think of an RDF graph as a
> bucket of triples”.
> >
> > What I should have been saying is “Ah, yes, you are right. That is
> because the term is ‘RDF Graph’, not ‘RDF’ ‘graph’. And we simply define an
> ‘RDF Graph’ as a bucket of triples. This often has a useful visualisation
> as interconnected nodes and edges, especially when you do SPARQL stuff, for
> example, but that isn’t always best, especially where there are lots of
> URIs that are used in both predicate and subject or object positions. Then
> the general way of thinking of it is as a bucket of triples is probably
> best."
> >
> > The reason I raised this is that I don’t think that was the general
> understanding, and I certainly haven’t seen it stated much; but maybe I was
> the only one with the concern - it wouldn’t be the first time :-)
> >
> > There is a slight awkwardness, because the RDF documents sometimes talk
> about “graph”s, without the RDF qualifier.
> > In fact, now I see something of why I was going the wrong way.
> > Never mind - I’ll just read “graph” to mean “RDF Graph” throughout.
> >
> > I think I’m happy with that - RDF is amazing artefact and achievement,
> and I’ll just consider it one of the slightly fuzzy edges that are always
> around such things.
> >
> >> On 28 Oct 2014, at 08:46, Bernard Vatant <bernard.vatant@mondeca.com>
> wrote:
> >>
> >> Hi all
> >>
> >> Interesting discussion, which reminds me of the good old chinese story
> "A white horse is not a horse”.
> > Very helpful on the graph/directed graph thing.
> >>
> >> To answer Simon's remark, people need metaphors, and visual ones can
> help some people, if not everybody. I don't care either about
> visualizations of RDF graphs, they don't appeal to me, but if they help
> some people to grasp the general RDF idea and somehow buy it (in all senses
> of "buy"), then just take it as a selling argument, no more no less. Think
> about Google Knowledge Graph, which is certainly no more a graph stricto
> sensu than RDF graph are. But it sells, people grasp quite easily the
> notion of a mesh of things connected by meaningful links, and it looks like
> serious knowledge :)
> > So maybe it is about capitalisation.
> > I genuinely think I might have read it differently if it had been “RDF
> Graph” in the documents (like Google Knowledge Graph), rather than “RDF
> graph”.
> >> Once you've sold the broad picture and drill down into the (devilish)
> details, the terms are not that much important. Think about "ontology", for
> example. It is the other way round, people are easily scared by the word
> rather than the thing, and I often tend to call it otherwise depending on
> my interlocutors and the context (model, whatever).
> >>
> >>
> >> 2014-10-28 3:50 GMT+01:00 Simon Spero <sesuncedu@gmail.com>:
> >> I've never seen the real advantage of the graph metaphor for RDF; is it
> any easier to understand than viewing triples as a set of ground binary
> formula, or as a conjunction of binary formula embedded in a mess of
> existential qualifiers (because blank nodes)?
> > When I think about complex matching, the graph metaphor can be helpful -
> but beyond that I go triples.
> >
> > Thanks again for all the help.
> > Hugh
> >>
> >> Simon
> >>
> >>
> >>
> >>
> >> --
> >> Bernard Vatant
> >> Vocabularies & Data Engineering
> >> Tel :  + 33 (0)9 71 48 84 59
> >> Skype : bernard.vatant
> >> http://google.com/+BernardVatant
> >> --------------------------------------------------------
> >> Mondeca
> >> 35 boulevard de Strasbourg 75010 Paris
> >> www.mondeca.com
> >> Follow us on Twitter : @mondecanews
> >> ----------------------------------------------------------
> >
> > --
> > Hugh Glaser
> >   20 Portchester Rise
> >   Eastleigh
> >   SO50 4QS
> > Mobile: +44 75 9533 4155, Home: +44 23 8061 5652
> >
> >
> >
>
>