Clarification of Framing Algorithm step 5.5.1

[kal]

Apologies if this is not the best place to bring up this issue - if you have a preferred mailing list please point me to it.

I'm trying to follow the Framing Algorithm but have a problem with a couple of the unit tests. In particular t0048, t0049 and tp049 and t0050. What these all have in common is @graph in a property frame and no top-level @graph on the frame. As I read step 5.5.1 and its substeps, it would appear that the recurse flag should be false as there is an entry for the graph name in graphMap, and the graphName in state is @merged (because there is no top-level @graph property on the frame).

So it seems like either the spec or the unit tests are in error. Alternatively, I could be missing something in the spec? (If I am can you point me to the correct place please!)

BTW the Playground also fails these particular unit tests.

[gkellogg]

@kal This is a fine place for such a question, and entirely appropriate.

The ability to frame graphs is new to Framing, and likely hasn't been incorporated into jsonld.js. I have it implemented in my Ruby Implementation, and feel free to crib from that and suggest any specific clarifications to the spec text.

I'll take a closer look when time allows.

[gkellogg]

Here's a run through of t0048 based on my implementation:

When we start, graph map looks like the following:

{
  "@default": {
    "urn:id-1": {
      "@id": "urn:id-1",
      "@type": ["urn:Class"],
      "urn:merge": [{"@id": "urn:id-2"}],
      "urn:preserve": [{"@id": "urn:graph-1"}]
    },
    "urn:id-2": {"@id": "urn:id-2"},
    "urn:graph-1": {"@id": "urn:graph-1"}
  },
  "urn:id-2": {
    "urn:id-2": {
      "@id": "urn:id-2",
      "urn:term": [{"@value": "foo"}]
    }
  },
  "urn:graph-1": {
    "urn:id-3": {
      "@id": "urn:id-3",
      "urn:term": [{"@value": "bar"}]
    }
  },
  "@merged": {
    "urn:id-1": {
      "@id": "urn:id-1",
      "@type": ["urn:Class"],
      "urn:merge": [{"@id": "urn:id-2"}],
      "urn:preserve": [{"@id": "urn:graph-1"}]
    },
    "urn:id-2": {
      "@id": "urn:id-2",
      "urn:term": [{"@value": "foo"}]
    },
    "urn:graph-1": {"@id": "urn:graph-1"},
    "urn:id-3": {
      "@id": "urn:id-3",
      "urn:term": [{"@value": "bar"}]
    }
  }
}

Expanded Frame is:

[
  {
    "@type": ["urn:Class"],
    "urn:preserve": [{"@graph": [{}]}]
  }
]

As the frame does not include @graph at the top level, we frame the merge graph.

On First entry, matched subjects is [urn:id-1]. urn:id-1 is not in graph map, so we skip 5.5.1. The sorted properites of this are ["@id", "@type", "urn:merge", "urn:preserve"].

• urn:merge is not in frame, so a new frame is constructed: {"@embed":["@last"],"@explicit":[false],"@requireAll":[true]} and the framing algorithm is called recursively with [{"@id": "urn:id-2"}].
  • matched subjects is [urn:id-2], which is in graph map, but recurse is false.
• urn:preserve is in frame with the value [{"@graph": [{}]}]. The framing algorithm is called recursively with {"@id"=>"urn:graph-1"}.
  • matched subjects is [urn:graph-1], which is in graph map, and recurse is true.
    • The framing algorithm is called with subjects ["urn:id-3"] and subframe {}.
      • matched subjects is ["urn:id-3"], and {"@id":"urn:id-3","urn:term":[{"@value":"bar"}]} is added as the value of @graph in the parent object yielding {"@id":"urn:graph-1","@graph":[{"@id":"urn:id-3","urn:term":[{"@value":"bar"}]}]}.

This results in the final result:

{
  "@id": "urn:id-1",
  "@type": ["urn:Class"],
  "urn:merge": [
    {
      "@id": "urn:id-2",
      "urn:term": [{"@value": "foo"}]
    }
  ],
  "urn:preserve": [
    {
      "@id": "urn:graph-1",
      "@graph": [
        {
          "@id": "urn:id-3",
          "urn:term": [{"@value": "bar"}]
        }
      ]
    }
  ]
}

[kal]

Thanks for the feedback @gkellogg
I've taken a step through the code for rdf-ruby and I think I see where our implementations diverge. It happens in the processing of the urn:preserve property when we process {"@id"=>"urn:graph-1"}

In frame.rb on line 97-99 you implement the filter for recurse as:

  subframe = frame['@graph'].first
  recurse = !%w(@merged @default).include?(subframe)
  subframe = {} unless subframe.is_a?(Hash)

Ruby is not a language I'm too familiar with, but it looks to me like the check here is that subframe is not either "@merged" or "@default". In my code (C#) I'm checking the GraphName property in state :

recurse = !(state.GraphName.Equals("@merged") || state.GraphName.Equals("@default"));

In both our implementations at this stage state[:graph] (my state.GraphName) is "@merged". Your test returns true and continues to the recursion, mine returns false and skips the recursion. If I change your line 98 to:

recurse = !%w(@merged @default).include?(state[:graph])

I get the same output from your implementation as I get from mine.

My implementation is based on my reading of step 5.5.1.2 in the framing algorithm:

Otherwise, set subframe to the first entry for @graph in frame, or a new empty dictionary, if it does not exist, and set recurse to true, unless graph name in state is @merged or @default.

So, unless I've missed the point I suspect that the "unless..." bit of that step is where the bug lies.

BTW my implementation is in dotNetRDF: https://github.com/dotnetrdf/dotnetrdf - so you can take a look at the code on the master branch for the current state.

[gkellogg]

Indeed, my code is in error, however I believe that the expected results are correct, and the algorithm needs to be modified accordingly. I believe that 5.5.1.2 should read as follows:

Otherwise, set subframe to the first entry for @graph in frame, or a new empty dictionary, if it does not exist, and set recurse to true, unless id is @merged or @default.

It is id which contains the name of the current graph that needs to be preserved. Note that graph name is only set in state once we've decided to recurse.

If you agree, I'll update the algorithm accordingly.

[kal]

Thanks Gregg, that all makes sense - we are basically avoiding recursion into unamed graphs. I've changed my implementation and the unit test in question now passes.

One last question on this though, if the test is against the name of the graph you are about to recurse into, then should 5.5.1.1 also refer to id rather than graph name in state ?

[gkellogg]

Actually, no, that doesn't work. If frame does not include @graph, recurse is set only if graph name in state is not @merged. I need to investigate a bit further to see why this is the case.

[gkellogg]

I believe the reason that 5.5.1.1 refers to the graph name in state rather than id, as in this case, we are typically already dealing with the merged graph, and only if we're not in the merged graph already do we need to recurse for a new graph. In 5.5.1.2, @graph is explicit, and we recurse only if the data is coming from something other than the merge or default graphs. So, the only change is to 5.5.1.2.