CODEWITHSUNDEEP
rdfsemantic-webblank-nodes
Norbox
Norbox

Reputation: 127

How to know if an RDF graph is lean?

I just discovered the definition of a lean graph and I don't always know how to define it and if someone can explain to me if this graphs are lean or not .

G1 :
_:X foaf:knows ex:bob
_:X foaf:knows _:Y

I think this is lean !

G2:    
_:X foaf:knows ex:bob
_:X foaf:knows _:X

G2 isn't lean !

G3
_:X foaf:knows ex:bob

I don't know XD

G4
_:X foaf:knows _:X

And I don't know XD

Thanks in advance.

Upvotes: 4

Views: 495

Answers (2)

Nathan Chappell
Nathan Chappell

Reputation: 2446

I'll add a more technical answer, using the definitions and examples from the w3 spec.

Definitions

A name is any IRI or literal.

A (proper) subgraph of an RDF graph is a (proper) subset of the triples in the graph.

Suppose that M is a functional mapping from a set of blank nodes to some set of literals, blank nodes and IRIs. Any graph obtained from a graph G by replacing some or all of the blank nodes N in G by M(N) is an instance of G.

A proper instance of a graph is an instance in which a blank node has been replaced by a name, or two blank nodes in the graph have been mapped into the same node in the instance.

An RDF graph is lean if it has no instance which is a proper subgraph of itself.

Here is graph G1:

ex:a ex:p _:x .
_:y ex:p _:x .

Here is G2:

ex:a ex:p _:x .
_:x ex:p _:x .

Claim 1: G1 is lean

Proof:

Define the mapping M:

  • _:y -> ex:a

Then M(G1) is:

ex:a ex:p _:x .

This is an instance of G1 by the definition of M, and clearly a proper subset of G1, therefore a proper subgraph as well.

Claim 2: G2 is not lean

Proof:

We must show that any instance mapping of G2 results in a graph which is not a proper subgraph of G2. Let M be any such mapping. The M must map _:x to something (other than _:x). Then the following triple will be in M(G2):

ex:a ex:p M(_:x)

This triple was not in G2, and therefore this instance is not a proper subgraph of G2. Since no mapping can create an instance of G2 which is also a proper subgraph of G2, G2 is lean.

Remark it seems like it would be cleaner if the definition of lean were:

An RDF graph is lean if it has no **proper** instance which is a proper subgraph of itself.

This would eliminate any doubt in my mind about what it means when M maps _:x to another arbitrary blank node. The definitions make everything still work okay, but the stronger definition of lean seems nicer to me.

Upvotes: 1

AndyS
AndyS

Reputation: 16700

The example at https://www.w3.org/TR/rdf11-mt/#dfn-lean

For example, the graph

ex:a ex:p _:x .
_:y ex:p _:x .

is not lean, but

ex:a ex:p _:x .
_:x ex:p _:x .

is lean. Ground graphs are lean.

In the question examples subject and object are flipped but otherwise G1 and G2 are the "RDF 1.1 Semantics" examples.

G1 is not lean.

You can remove "_:X foaf:knows _:Y" (or remove "_:y ex:p _:x") - that triple adds no new information. We know "_:X knows something" from the first triple "_:X foaf:knows ex:bob" and that is all the second triple says.

Graphs G3 and G4 are lean.

If we have G5: _:X foaf:knows _:Y then G5 is lean but G3 merge G5 is not lean.

G2 is lean because the triple "_:X foaf:knows _:X" adds the information that there is some resource that knows itself. The first triple does not say that.

Upvotes: 4

Related Questions