是否可能在SPARQL中表达递归定义？ [英] Is it possible to express a recursive definition in SPARQL?

问题描述

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

 ：peter foaf：knows：john; 
 foaf：knows：anna; 
 rdfs：labelPerson。 
 
：john foaf：knows：anna; 
 rdfs：labelPerson。 
 
：anna rdfs：labelPerson。 
  

在逻辑术语中，定义可以是：

&＃x2200; x（Person（x）&＃x2261; rdfs：label（x，Person）&＃x2227;&＃x2200; y（rdfs：label（x，y）&＃x2192 ; y =Person）&＃x2227;&＃x2200; y（foaf：knows（x，y）&＃x2192; Person（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 {
 
＃确保只有一个rdfs：label 
 {SELECT？person {
？person rdfs：label？ 
} GROUP BY？person HAVING（COUNT（*）= 1）} 
 
＃确保rdfs：label值为Person
 {SELECT？person {
？person rdfs：label？o。 
 FILTER（（？o =Person））
} GROUP BY？person HAVING（COUNT（*）= 1）} 
 
＃计数foaf：knows 
 {SELECT？person（COUNT（*）AS？p_c0）{
？people foaf：knows []。 
} GROUP BY？person 
} 
 
＃计算foaf的数量：使用具有人的结构的值
 {SELECT？person（COUNT （*）AS？p_c1）{
？person foaf：knows？person1。 ＃我如何表达person1有人的结构？ 
} GROUP BY？person 
} 
 FILTER（？p_c0 =？p_c1）
} 
  

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

注意：在约书亚的建议之后的定义的术语约束

解决方案

不是一对约束。

我们经常想到在必要和充分条件方面的定义。足够的条件是那些给我们足够的信息以得出某事是给定集合的一个元素，并且必要的条件是那些告诉我们更多关于个人的信息。例如，在OWL中，我们可能有公理：

Man⊑人员

人员⊑ &exists; hasName

第一个是Person的充分条件：知道某事是一个Man足以确定它也是一个Person 。第二个是人的必要条件：如果某人是一个人，那么它必须有一个名字。 （Dually，我们还可以注意到，第一个公理是Man的必要条件：如果某个东西是一个Man，那么它必须是一个Person，第二个公理是一个足够的条件用于&exists; hasName;必须有一个名称。）

约束检查通常是找到满足类的足够条件但不满足所有必要条件的个人的任务。这不是你想在这里做的。相反，您要寻找符合必要且足够的人格条件的个人：

1. >
   
2. 只知道其他人。

在约束验证中，您将写一个查找有问题的查询

找到满足你的人的个人（例如，应该是人的东西，但不是人），但在你的任务中，规范

一般来说，您不能在SPARQL中指定递归定义，但在这种情况下，您可以撰写一个查询， 。诀窍是首先使用一个模式来标识图中的所有节点。然后，在概念上，我们假设每个人都是一个人，然后过滤掉那些不符合条件的人。在这种情况下，这是可能的，因为条件是简单的一切可达的foaf：知道（包括零长度链）应该有标签人，没有别的。以下是一些示例数据（包括您的答案中的示例），查询以及结果。

  @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：labelPerson。 
 
：john foaf：knows：anna; 
 rdfs：labelPerson。 
 
：anna rdfs：labelPerson。 
 
：mary rdfs：labelPerson。 
 
：tom rdfs：labelCat。 
 
：pluto rdfs：labelDog; foaf：knows：tom。 
 
：ben rdfs：labelWolf; rdfs：labelPerson。 
 
：mary rdfs：labelPerson; foaf：knows：ben。 
 
：sam rdfs：labelPerson; foaf：knows：mary。 
  

 前缀：< 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其中{
＃ - 图中的每个节点
？person：？ ？人。 
 
＃ - 除了那些foaf：know * some？x 
＃ - （因为*包括零长度
＃ - 路径，？x也绑定to？person）
＃ - 不符合标签条件。 
过滤器不存在{
？person foaf：knows *？x 
可选{？x rdfs：label？label} 
过滤器！=Person）
} 
} 
  

  ---------- 
 |人| 
 ========== 
 | ：anna | 
 | ：john | 
 | ：peter | 
 ---------- 
  

约束检查

现在，假设上面的条件1和条件2实际上是人格的必要条件。然后，根据足够的条件，我们可以编写不同的查询来查找违例。您可能希望在图中具有非人员节点，因此您可能有足够的条件，即节点具有rdf：type：Person。然后你可以使用这样的查询：

 前缀rdfs：< http：// www .w3.org / 2000/01 / rdf-schema＃> 
 prefix：< http：//stackoverflow.com/q/25256452/1281433/> 
 
＃ - 有两种类型的方法：Person 
＃ - 可能无效。 （i）它可以缺少一个标签，或
＃ - 有一个除Person之外的标签; （ii）it 
＃ - 可以有值foaf：knows *不是
＃ - 有rdf：type：Person。 
 
 select？person其中{
＃ - 检查图中的每个人。 
？person a：Person。 
 
 {＃ - 检查个人是否有一个标签，以及
＃ - 没有Person以外的标签
可选{？person rdfs：label ？label} 
 filter（！bound（？label）||？label！=Person）
} UNION 
 {＃ - 检查foaf的每个值：know 
＃ - 也有类型：Person。如果一些值
＃ - 有类型：Person，但违反约束，
＃ - 我们将分别捕获它。 
？person foaf：knows？x。 
过滤器不存在{？x a：Person} 
} 
} 
  

Imagine that you have a simple social network where people must have only one property rdfs:label with value "Person" and can have any number of foaf:knows whose values must also be people with the same structure. Some example data could be:

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

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

:anna  rdfs:label "Person" .

In logic terms, the definition could be something like:

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

Is it possible to express those recursive definitions in SPARQL?

I was able to express part of the query without the recursive reference of foaf:knows as:

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)
}

Is it possible to express such recursive definitions in SPARQL?

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

解决方案

This is a definition, not a pair of constraints

We often think of definitions in terms of necessary and sufficient conditions. Sufficient conditions are those that give us "enough" information to conclude that something is a element of a given set, and necessary conditions are those that tell us a bit more about the individuals. For instance, in OWL, we might have the axioms:

Man ⊑ Person
Person ⊑ ∃hasName

The first is a sufficient condition for Person: knowing that something is a Man is sufficient to determine that it's also a Person. The second is a necessary condition for Persons: if something is a person, then it must have a name. (Dually, we can also note that the first axiom is necessary condition for Man: if something is a Man, then it must be a Person. The second axiom is a sufficient condition for ∃hasName; if something is a Person, then it must have a name.)

Constraint checking is typically the task of finding individuals that meet the sufficient conditions for a class, but don't satisfy all the necessary conditions. That's not what you're trying to do here. Instead, you're looking for individuals that meet the necessary and sufficient conditions of personhood:

1. have exactly the label "Person"
2. know only other persons.

In constraint validation, you'll write a query that that finds problematic individuals (e.g., things that are supposed to be persons, but aren't), but in your task, you'll find good individuals.

Finding individuals that meet your specification

In general you can't specify recursive definitions in SPARQL, but in this case, you can write a query that will select all people. The trick is to first use a pattern that identifies all nodes in the graph. Then, conceptually, we suppose that each one is a person, and then filter out those that don't meet the conditions. That's possible in this case, because the condition is simply that everything reachable by a chain of foaf:knows (including the zero length chain) should have the label "Person" and nothing else. Here's some sample data (including the examples from your answer), the query, and finally the results.

@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 |
----------

Constraint Checking

Now, suppose that conditions 1 and 2 above were actually necessary conditions for personhood. Then, depending on the sufficient conditions, we could write different queries to find violations. You probably want to have non-person nodes in the graph, so you might have a sufficient condition that a node has rdf:type :Person. Then you can use a query like this:

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 }
  }
}

这篇关于是否可能在SPARQL中表达递归定义？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！