GraphMatchingQuery

From W3C Wiki
Jump to: navigation, search


One way to construct an RDF Query is to look for matches in a graph.

For example, suppose you want to look for people that a person with a particular e-mail address knows:

 query-node.png

Your query is something like:

  • find nodes <N>
  • <N> rdf:type foaf:Person
  • rdf:type foaf:Person

  • <P> foaf:knows <N>
  • <P> foaf:mbox (some e-mail address)

Your query software would then look through the graph, searching for nodes that match the description.

Discussion

That picture is hosted on my server, and is of my authoring. You are free to copy and reuse the link, and you are free to copy the image. I release the image into the Public Domain.

-- LionKimbro DateTime(2004-06-14T18:05:39)

There are some cheesy Wiki:BruteForce ways to attack this sort of problem.

The most obvious is perhaps:

  • Check to see if any node is <N>.
    • If the rdf:type is not foaf:Person, start checking the next node.
    • Check to see if any node is <P>.
      • If the rdf:type is not foaf:Person, start checking the next node.
      • If the foaf:knows is not the possible <N>, start checking the next node.
      • If the foaf:mbox is no the e-mail address, start checking the next node.

If you want to optimize it, you can change the order that you check things in.

Or, you could just start making indexes wherever you see a triple:

  • Index for all nodes that meet the pattern "<X> rdf:type foaf:Person"
  • Index for all nodes that meet the pattern "<X> foaf:knows <Y>"
  • Index for all nodes that meet the pattern "<X> foaf:mbox (some e-mail address)"

...and then brute force plow it.

There are so many lovely ways to attack this that require little to no thought at all..!

-- LionKimbro DateTime(2004-06-15T03:20:13)