recursion - 是否可以在 SPARQL 中表达递归定义？

Question

假设您有一个简单的社交网络，其中人们必须只有一个属性 rdfs:label，值为 "Person"，并且可以有任意数量的 foaf :knows 其值也必须是具有相同结构的人。一些示例数据可能是:

:peter foaf:knows :john; 
       foaf:knows :anna;
       rdfs:label "Person" .

:john  foaf:knows :anna;
       rdfs:label "Person" .

:anna  rdfs:label "Person" .

在逻辑上，定义可能是这样的:

∀x(Person(x) ≡ rdfs:label(x,"Person")∧∀y(rdfs:label(x,y)→y="Person")∧∀y(foaf:knows(x, y)→人(y)))

是否可以在 SPARQL 中表达这些递归定义？

我能够在没有 foaf:knows 递归引用的情况下将部分查询表达为:

PREFIX ex: <http://xmlns.com/foaf/0.1/>
PREFIX foaf: <http://xmlns.com/foaf/0.1/>
PREFIX rdfs:<http://www.w3.org/2000/01/rdf-schema#>

select ?person {

    # Ensure there is only one rdfs:label
    { SELECT ?person {
      ?person rdfs:label ?o .
    } GROUP BY ?person HAVING (COUNT(*)=1)}

    # Ensure the rdfs:label value is "Person"
    { SELECT ?person {
      ?person rdfs:label ?o . 
      FILTER ((?o = "Person"))
    } GROUP BY ?person HAVING (COUNT(*)=1)}

    # Count the number of foaf:knows
    { SELECT ?person (COUNT(*) AS ?p_c0) { 
       ?person foaf:knows [] . 
      } GROUP BY ?person
    }

    # Count the number of foaf:knows with a value that has the structure of a person
    { SELECT ?person (COUNT(*) AS ?p_c1) { 
       ?person foaf:knows ?person1 . # How can I express that person1 has the structure of people?
      } GROUP BY ?person
    }
    FILTER (?p_c0 = ?p_c1)
}

是否可以在 SPARQL 中表达这种递归定义？

Note: I edited the question changing the term "constraint" by "definition" following Joshua's suggestion

Answer 1

这是一个定义，不是一对约束

我们经常根据必要条件和充分条件来考虑定义。充分条件是那些给我们“足够”的信息以得出结论某物是给定集合的元素的条件，而必要条件是那些告诉我们更多关于个体的信息的条件。例如，在 OWL 中，我们可能有公理:

Man ⊑ Person
Person ⊑ ∃hasName

第一个是 Person 的充分条件:知道某物是 Man 就足以确定它也是 Person。第二个是 Persons 的必要条件:如果某物是一个人，那么它必须有一个名字。 (对偶地，我们还可以注意到，第一个公理是 Man 的必要条件:如果某物是 Man，则它必须是 Person。第二个公理是 ∃hasName 的充分条件；如果某物是 Person，则它必须有一个名字。)

约束检查通常是寻找满足类的充分条件但不满足所有必要条件的个体的任务。这不是你在这里要做的。相反，您正在寻找满足人格必要和充分条件的个人:

1. 有准确的标签“Person”
2. 只认识其他人。

在约束验证中，您将编写一个查询来查找有问题的个人(例如，应该是人但不是的东西)，但在您的任务中，您会找到好的个人。

寻找符合您要求的人

通常您不能在 SPARQL 中指定递归定义，但在这种情况下，您可以编写一个将选择所有人的查询。诀窍是首先使用一种模式来标识图中的所有节点。然后在概念上，我们假设每一个都是一个人，然后过滤掉那些不符合条件的。在这种情况下这是可能的，因为条件很简单，就是 foaf:knows 链(包括零长度链)可以到达的所有东西都应该有标签“Person”，别无其他。下面是一些示例数据(包括您回答中的示例)、查询以及最后的结果。

@prefix : <http://stackoverflow.com/q/25256452/1281433/>.
@prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#>.
@prefix foaf: <http://xmlns.com/foaf/0.1/>.

:peter foaf:knows :john; 
       foaf:knows :anna;
       rdfs:label "Person" .

:john  foaf:knows :anna;
       rdfs:label "Person" .

:anna  rdfs:label "Person" .

:mary rdfs:label "Person" .

:tom rdfs:label "Cat" .

:pluto rdfs:label "Dog" ; foaf:knows :tom .

:ben rdfs:label "Wolf"; rdfs:label "Person" .

:mary rdfs:label "Person"; foaf:knows :ben .

:sam rdfs:label "Person"; foaf:knows :mary .

prefix : <http://stackoverflow.com/q/25256452/1281433/>
prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#>
prefix foaf: <http://xmlns.com/foaf/0.1/>

select ?person where { 
  #-- each node in the graph
  ?person :? ?person .

  #-- except those that foaf:know* some ?x
  #-- (and since * includes the zero length
  #-- path, ?x is also bound to ?person)
  #-- that don't meet the labeling condition.
  filter not exists {
    ?person foaf:knows* ?x
    optional { ?x rdfs:label ?label }
    filter ( !bound(?label) || ?label != "Person" )
  }
}

----------
| person |
==========
| :anna  |
| :john  |
| :peter |
----------

约束检查

现在，假设上述条件 1 和条件 2 实际上是人格的必要条件。然后，根据充分条件，我们可以编写不同的查询来查找违规行为。您可能希望图中有非人员节点，因此您可能有一个节点具有 rdf:type :Person 的充分条件。然后你可以使用这样的查询:

prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#>
prefix : <http://stackoverflow.com/q/25256452/1281433/>

#-- There are two way something with type :Person
#-- can be invalid.  (i) it can lack a label, or 
#-- have a label other than "Person";  (ii) it 
#-- can have a value of foaf:knows* that doesn't
#-- have rdf:type :Person.

select ?person where {
  #-- Examine each person in the graph.
  ?person a :Person .

  { #-- Check that ?person has a label, and that
    #-- that it has no label other than "Person"
    optional { ?person rdfs:label ?label } 
    filter ( !bound(?label) || ?label != "Person" )
  } UNION
  { #-- Check that every value of foaf:knows 
    #-- also has type :Person.  If some value
    #-- has type :Person, but violates the constraints,
    #-- we'll catch it separately.
    ?person foaf:knows ?x .
    filter not exists { ?x a :Person }
  }
}