SPARQL 1.2 RL

다음 명세는 이 문서에서 사용되는 기본 용어를 제공합니다.

• RDF 1.2 개념 및 추상 데이터 모델 [RDF12-CONCEPTS]
• SPARQL 1.2 질의 언어 [SPARQL12-QUERY]

이 문서의 RDF 데이터 예제에서는 RDF 1.2 Turtle [RDF12-TURTLE]을 사용합니다.

이 문서에서는 다음 네임스페이스 접두사 바인딩을 사용합니다.

문서 전체에서 색상으로 구분된 상자는 SPARQL-RL 구문의 규칙을 포함하거나 Turtle 구문의 RDF 그래프를 포함합니다.

# 이 상자는 규칙을 나타냅니다

# 이 상자는 입력 데이터를 나타냅니다

# 이 상자는 추론된 데이터를 나타냅니다

변수

하나의 변수는 가능한 RDF 용어를 트리플 패턴에서 나타냅니다. 변수는 또한 표현식에서도 사용됩니다.

표현식

하나의 표현식은 RDF 용어, 변수, 또는 함수나 함수형 형식을 인수에 적용한 것이며, 각 인수는 그 자체로 하나의 표현식입니다. 표현식은 다음을 기준으로 평가됩니다: 해 매핑. 평가 결과는 하나의 RDF 용어로 주어지거나, 평가 결과 오류가 발생합니다. 표현식은 다음과 호환됩니다: SPARQL 표현식.

데이터 블록

하나의 데이터 블록은 트리플의 집합입니다. 이러한 트리플은 추가 사실로서 추론 그래프에 추가되며 추론 과정에 포함됩니다.

트리플 패턴

하나의 트리플 패턴은 각 요소가 다음 중 하나인 3-튜플입니다: 하나의 변수, 하나의 RDF 용어, 또는 다음에 대한 패턴: 트리플 용어(다음 포함: 변수). 튜플의 두 번째 요소는 IRI 또는 변수입니다. 트리플 패턴은 본문에 나타나며, 해당 규칙에서 다음을 일치시키는 데 사용됩니다: RDF 트리플.

트리플 템플릿

하나의 트리플 템플릿은 각 요소가 다음 중 하나인 3-튜플입니다: 하나의 변수, 하나의 RDF 용어, 또는 다음에 대한 템플릿: 트리플 용어(다음 포함: 변수). 튜플의 두 번째 요소는 IRI 또는 하나의 변수입니다. 트리플 템플릿은 헤드에 나타나며, 해당 규칙에서 다음을 생성하는 데 사용됩니다: RDF 트리플.

참고

다음에 대한 패턴이나 템플릿: 트리플 용어에 어떤 변수도 나타나지 않으면, 이는 트리플 용어이며, 따라서 하나의 RDF 용어이기도 합니다.

트리플 패턴 요소

하나의 트리플 패턴 요소는 트리플 패턴으로, 다음으로 나타납니다: 규칙 요소.

필터 요소

하나의 필터 요소는 하나의 표현식으로, 다음으로 나타납니다: 규칙 요소. 이는 변수의 값을 제한하는 데 사용되며, 패턴 일치 과정에 적용됩니다.

부정 요소

하나의 부정 요소는 하나의 규칙 요소입니다. 여기에는 부정 요소 본문이 있으며, 이는 다음의 시퀀스로 구성됩니다: 트리플 패턴 요소와 필터 요소. 하나의 부정 요소에는 하나의 플래그, .evaldata가 있으며, 일치에 사용할 그래프를 나타냅니다. 그 대상은 부정 요소 본문입니다.

할당 요소

하나의 할당 요소는 하나의 규칙 요소이며, 다음으로 구성된 쌍입니다: 하나의 변수(명칭: 할당 변수), 그리고 하나의 표현식(명칭: 할당 표현식).

그룹 요소

하나의 그룹 요소는 하나의 규칙 요소이며, 다음과 같은 변수 집합(명칭: 그룹 키), 하나의 그룹 패턴, 그리고 다음의 집합을 가집니다: 집계 할당. 각 집계 할당은 다음으로 구성된 쌍입니다: 하나의 변수(명칭: 집계 변수), 그리고 하나의 집계 함수. 이 그룹 패턴은 다음의 시퀀스로 구성됩니다: 트리플 패턴 요소와 필터 요소.

규칙 요소

하나의 규칙 요소는 다음 중 하나입니다: 트리플 패턴 요소, 필터 요소, 부정 요소, 할당 요소, 또는 그룹 요소.

규칙 헤드

하나의 규칙 헤드는 다음의 시퀀스입니다: 트리플 템플릿.

규칙 본문

하나의 규칙 본문는 다음의 시퀀스입니다: 규칙 요소; 즉, 각 시퀀스 요소는 다음 중 하나입니다: 하나의 트리플 패턴 요소, 하나의 필터 요소, 하나의 부정 요소, 하나의 할당 요소, 또는 하나의 그룹 요소.

규칙 집합 가져오기

규칙 집합 가져오기(흔히 간단히 "가져오기")는 URL의 모음입니다. 이는 IMPORTS 문에서 가져온 것으로, 평가 중에 포함될 다른 규칙 집합을 위한 것입니다.

규칙

하나의 규칙은 다음을 포함합니다: 규칙 헤드(흔히 간단히 "헤드"), 하나의 규칙 본문(흔히 간단히 "본문"), 그리고 플래그 .evaldata. 이 플래그는 어떤 그래프를 일치에 사용할지 나타내며, 대상은 트리플 패턴으로, 본문에 있습니다. 규칙을 식별하는 데 도움이 되도록 URI나 빈 노드를 부여할 수 있습니다.

단일 실행 규칙

하나의 단일 실행 규칙은 정확히 한 번만 실행되는 규칙으로, 규칙 집합 평가의 특정 시점에 실행됩니다. 하나의 규칙은 단일 실행 규칙에 해당합니다. 다음 중 하나라도 성립하는 경우입니다:

• 해당 규칙 본문에 하나의 할당 요소가 있습니다;
• 해당 규칙 본문에 하나의 그룹 요소가 있습니다;
• 하나의 트리플 템플릿이 속한 규칙 헤드에서, 이 템플릿에 빈 노드가 있습니다;
• 하나의 트리플 템플릿이 속한 규칙 헤드에서, 이 템플릿에 다음에 대한 템플릿이 있습니다: 트리플 용어. 이 템플릿에는 하나의 변수가 나타납니다.

일반 규칙

하나의 일반 규칙은 다음에 해당하지 않는 규칙입니다: 단일 실행 규칙. 일반 규칙은 규칙 집합 평가 중에 두 번 이상 실행될 수 있습니다.

규칙 집합

하나의 규칙 집합은 0개 이상의 규칙 모음, 0개 이상의 데이터 블록 모음, 그리고 0개 이상의 규칙 집합 가져오기 모음입니다. 하나의 해결된 규칙 집합은 하나의 규칙 집합으로, 가져오기가 없습니다. 하나의 해결된 규칙 집합은 다른 규칙 집합으로부터 가져오기 과정을 적용하여 생성됩니다.

기본 그래프

하나의 기본 그래프는 RDF 그래프로, 입력으로 주어집니다. 그 대상은 평가 과정입니다.

추론 그래프

하나의 추론 그래프는 하나의 RDF 그래프로, 다음에 의해 생성됩니다: 하나의 규칙 집합 평가. 여기에는 다음에 존재하지 않는 모든 추론된 트리플이 포함됩니다: 기본 그래프. 이러한 트리플은 다음을 적용하여 추론됩니다: 규칙 집합을 기본 그래프에 적용합니다.

규칙 집합 평가

하나의 규칙 집합 평가는 다음을 적용하는 과정입니다: 규칙 집합을 하나의 기본 그래프에 적용하여 하나의 추론 그래프를 생성합니다. 하나의 규칙 평가는 규칙을 한 번 평가하는 과정입니다. 규칙을 평가하면 다음에 의해 주어지는 모든 트리플이 생성됩니다: 규칙 헤드. 이는 다음의 평가에 따른 것입니다: 규칙 본문. 이때 트리플이 기본 그래프에 있는지, 이미 다음 과정에서 추론되었는지: 규칙 집합 평가, 또는 새롭게 추론된 트리플인지와는 관계없습니다. 규칙 집합 평가 중에 규칙은 한 번보다 더 많이 평가될 수 있습니다.

SPARQL-RL은 두 연산을 제공합니다. 추론 및 질의입니다.

추론

추론은 다음을 적용하는 연산입니다. 규칙 집합을 주어진 기본 그래프에 적용하고 추론 그래프를 생성하며, 여기에는 추론된 트리플이 포함됩니다. 이 연산은 전체 규칙 집합 평가를 적용합니다.

질의

질의는 주어진 패턴을 도출할 수 있는지 결정하는 연산이며, 도출의 출발점은 기본 그래프이고, 다음을 사용합니다. 규칙 집합. 또한 하나의 해 시퀀스를 반환하며, 여기서 각 해 매핑은 변수에 대한 RDF 용어를 제공합니다.

질의는 다음을 수행하는 효과를 가집니다. 추론 연산을 수행한 후, 목표 패턴을 다음의 결합 결과와 매칭합니다. 기본 그래프 및 추론 그래프.

해당 질의 연산은 모든 규칙을 평가하지 않을 수 있으며, 대신 질의 목표에 답하는 데 필요한 규칙만 평가할 수 있습니다.

SPARQL-RL 처리기

하나의 SPARQL-RL 처리기는 다음을 구현하는 시스템입니다. SPARQL-RL 명세를 구현하고, 규칙 집합을 평가할 수 있으며, 하나 또는 둘 다를 제공합니다. 해당 연산은 추론 및 질의입니다.

하나의 트리플 패턴 또는 트리플 템플릿에서, 튜플의 위치 1은 비공식적으로 주어라고 부르고, 위치 2는 비공식적으로 술어라고 부르며, 위치 3은 비공식적으로 목적어라고 부릅니다.

규칙 집합과 규칙의 다양한 구성 요소에는 다음 표기법이 사용됩니다.

올바른 형식은 추상 구문에 대한 조건들의 집합으로, 하나의 규칙 집합에 적용됩니다. 이 조건들은 함께 다음을 보장합니다. 하나의 변수가 헤드에 있는 규칙에서는 그 값이 본문에 정의되어 있다는 점; 각 변수가 필터 요소 또는 할당 표현식에 있을 때 평가 시점에 값을 갖는다는 점; 그리고 각 할당 변수 및 집계 변수가 규칙에서 새로 도입되며 규칙 본문에서 앞서 사용되지 않았다는 점입니다.

S를 규칙 요소의 시퀀스라고 합니다.

elt_i를 S의 i번째 요소라고 하고, N을 시퀀스의 길이라고 합니다.

V₀를 변수 집합이라고 하며, 이를 초기 변수라고 부릅니다. 이 변수들은 시퀀스 S의 초기 변수입니다.

vars(S, i, V₀)를 변수들의 집합으로 정의하며, 이 변수들은 시퀀스 S의 i번째 요소 이후에 유효 범위에 있습니다. 이때 초기 변수 V₀가 주어집니다. vars(S, i, V₀)는 귀납적으로 정의됩니다:

vars(S, V₀), 즉 S에서 유효 범위에 있는 변수들의 집합을 vars(S, N, V₀)로 정의합니다. 이는 유효 범위에 있는 변수들의 집합이며, 시퀀스의 마지막 요소 이후를 기준으로 합니다.

다음 규칙 요소의 시퀀스 S는 올바른 형식의 시퀀스입니다. 변수 집합 V₀가 주어졌을 때, 다음 조건들이 각 i에 대해 충족되는 경우이며, 그 범위는 1부터 N까지입니다:

하나의 규칙은 올바른 형식의 규칙입니다. 다음 조건이 성립하는 경우입니다. 규칙 요소의 시퀀스가 속한 규칙 본문에서, 이 시퀀스가 올바른 형식의 시퀀스이며, 시작 시 V₀가 공집합이고, 각 변수가 트리플 템플릿에 있으며, 이 템플릿이 규칙 헤드에 속할 때, 각 변수가 vars(S, V₀)의 원소인 경우입니다.

하나의 규칙 집합이 올바른 형식의 규칙 집합인 것은 모든 규칙이 해당 규칙 집합에서 올바른 형식의 규칙인 경우와 그 경우에만 해당합니다.

규칙 R1이 규칙 R2에 의존하는 경우는 두 번째 규칙의 출력이 첫 번째 규칙의 본문 평가에 영향을 미칠 때입니다. 즉, R2의 헤드에는 하나의 트리플 템플릿이 있으며, 이는 다음에 일치하는 트리플을 생성할 수 있습니다: 하나의 트리플 패턴으로, R1의 본문에 있으며, 하나의 트리플 패턴 요소로 나타나거나, 하나의 부정 요소 또는 하나의 그룹 패턴 안에 있습니다.

의존성에는 두 종류가 있습니다: 닫힌 의존성 및 열린 의존성. 닫힌 의존성은 규칙 R2가 규칙 R1이 실행되기 전에 가능한 모든 출력을 생성했음을 보장합니다. 규칙 의존성이 닫혀 있지 않으면 열린 의존성입니다. 이는 첫 번째 규칙 R1이 실행될 수 있게 하며, 그동안 규칙 R2는 추가 트리플을 생성하기 위해 다시 실행될 수 있고, 이에 따라 R1이 R2의 새 트리플로 재평가될 수 있습니다.

플래그 .evaldata가 false로 설정된 규칙은 기본 그래프를 사용하여 매칭하며, 해당 규칙에는 의존성이 없습니다.

이 첫 번째 예제에서 첫 번째 규칙은 열린 의존성을 가집니다. 그 대상은 두 번째 규칙입니다.

이 두 번째 예제에서 첫 번째 규칙은 닫힌 의존성을 가집니다. 그 대상은 두 번째 규칙입니다. 트리플 패턴 ?x :status :criticallyExposed는 다음의 내부에 나타납니다. 부정 요소로서 첫 번째 규칙에 속하며, 다음과 매칭됩니다. 트리플 템플릿으로서 두 번째 규칙의 머리부에 있습니다. 첫 번째 규칙은 두 번째 규칙이 가능한 모든 출력을 생성할 때까지 평가할 수 없습니다.

트리플 패턴 매칭

하나의 트리플 패턴은 트리플 템플릿과 매칭되며, 이는 해당 트리플 템플릿이 트리플을 생성할 수 있고, 해당 트리플이 매칭되는 대상이 해당 트리플 패턴인 경우입니다.

트리플 패턴 의존성

하나의 트리플 패턴이 의존하는 대상은 트리플 템플릿이며, 이는 해당 트리플 패턴이 매칭될 수 있는 대상이 해당 트리플 템플릿인 경우입니다.

규칙 의존성

규칙 R1은 의존 관계에 있습니다 규칙 R2에 대해 다음 조건이 성립하는 경우입니다. R1.evaldata가 true이고, 어떤 트리플 패턴이 R1의 본문에 있으며, 그 형태가 트리플 패턴 요소이든, 다음의 내부에 있든: 부정 요소 neg(여기서 neg.evaldata는 true), 또는 그룹 패턴 내부에 있든, 의존하는 트리플 템플릿이 R2의 헤드에 있는 경우입니다.

닫힌 의존성

하나의 규칙 의존성이 규칙 R1에서 규칙 R2로 향할 때, 이는 닫힌 의존성이며, 다음 조건 중 하나라도 성립하는 경우입니다:

• 하나의 트리플 패턴이 부정 요소 내부에 나타나며, R1의 해당 부정 요소의 플래그 .evaldata가 true이고, 매칭되는 트리플 템플릿이 규칙 머리부에 있으며, 이는 R2의 머리부입니다.
• 규칙 R1이 의존하는 대상이 규칙 R2이고 R1이 단일 실행 규칙입니다.

열린 의존성

하나의 규칙 의존성이 규칙 R1에서 규칙 R2로 향할 때, 이는 열린 의존성이며, 해당 의존성이 닫힌 의존성이 아닌 경우입니다.

define mergeLabel(oldLabel, newLabel):
    # 닫힌 의존성이 열린 의존성보다 우선합니다.
    if oldLabel == "open" and newLabel == "open":
        the result is "open"
    else:
        the result is "closed"
    endif
enddefine

# 출력 -- 규칙 정점과 레이블이 지정된 간선이 있는 의존성 그래프.
define buildDependencyGraph(ruleSet):
    # edgeLabelMap은 (R1, R2)를 "open" 또는 "closed"에 매핑합니다
    let edgeLabelMap be a map from pair (rule, rule) to label

    foreach rule R1 in ruleSet.rules:
        let bodyDependencies = {}

        if R1.evaldata then:
            # 규칙의 각 트리플 패턴 TP를 "open" 또는 "closed"가 필요한 것으로 분류합니다
            # 부정 요소나 그룹 패턴 안에 있는지 여부에 따라 분류합니다.
            foreach rule element RBE in R1.body:
                if RBE is a triple pattern element of triple pattern TP:
                    let item be a pair (TP, "open")
                    add item to bodyDependencies
                else if RBE is a filter element:
                    # 아무 작업도 하지 않습니다
                else if RBE is a negation element:
                    if RBE.evaldata then:
                        foreach triple pattern TP in RBE.inner:
                            let item be a pair (TP, "closed")
                            add item to bodyDependencies
                        endfor
                    endif
                else if RBE is an assignment element:
                    # 아무 작업도 하지 않습니다
                else if RBE is a group element:
                    foreach triple pattern TP in RBE.pattern:
                        let item be a pair (TP, "closed")
                        add item to bodyDependencies
                    endfor
                endif
            endfor
        endif

        foreach pair (triple pattern TP, depLabel) in bodyDependencies:
            if R1 is a run-once rule:
                set depLabel to "closed"
            endif
            # 이 트리플 패턴 요소 또는 부정 요소의 의존성을 찾습니다.
            foreach rule R2 in ruleSet.rules:
                foreach triple template TT in R2.head:
                    if triple pattern TP matches triple template TT:
                        let key = (R1, R2)
                        if edgeLabelMap contains key:
                            let oldLabel = edgeLabelMap.get(key)
                            let merged = mergeLabel(oldLabel, depLabel)
                            edgeLabelMap.set(key, merged)
                        else:
                            edgeLabelMap.set(key, depLabel)
                        endif
                    endif
                endfor
            endfor
        endfor
    endfor

    let DP = { }
    foreach entry ((R1, R2), label) in edgeLabelMap:
        add an edge (R1 -> R2) labeled with label to DP
    endfor

    the result is DP
enddefine

층화는 하나의 규칙 집합을 순서 있는 시퀀스로 분할하는 과정이며, 그 구성 요소는 층화 계층입니다(다른 명칭은 "strata"이며, 단수형은 "stratum"입니다). 낮은 계층의 규칙은 더 높은 계층의 규칙보다 먼저 평가됩니다.

층화는 다음 사이의 의존성에 제약을 부과합니다: 규칙. 이를 통해 부정 요소, 그룹 요소, 그리고 단일 실행 규칙이 오직 앞선(더 낮은) 계층과 기본 그래프를 사용하여 계산한 결과에만 의존하도록 보장합니다. 이는 단일하고, 명확히 정의되며, 유한한 평가 결과를 보장합니다. 평가 대상은 규칙 집합이며, 주어진 기본 그래프에 대해 평가합니다.

층화 계층

하나의 층화 계층 SL은 쌍이며, 서로소인 두 집합으로 구성됩니다. 이들은 규칙 집합 (SL.once, SL.general)입니다. SL.once는 정확히 단일 실행 규칙들로 이루어지며, 이 규칙들은 해당 계층에 속합니다; 이 규칙들은 각각 평가되며, 다음의 평가 시작 시 정확히 한 번 평가됩니다: 층화 계층. SL.general은 해당 계층의 나머지 규칙들의 집합이며, 이 규칙들은 새로운 트리플이 더 이상 추론되지 않을 때까지 반복적으로 평가됩니다.

층화

하나의 층화는 하나의 규칙 집합에 대한 것으로, 층화 계층의 시퀀스입니다. 각 규칙은 하나의 규칙 집합에서 정확히 하나의 집합에 속하며, 그 집합은 하나의 층화 계층에 속합니다.

해당 층화 계층들은 하나의 층화에 속하며, 번호가 부여됩니다. 번호는 0부터 시작합니다. 계층 번호는 하나의 규칙에 대해 부여되는 번호이며, 해당 층화 계층, 즉 그 규칙을 포함하는 계층의 번호입니다. 규칙의 계층 번호가 더 작으면, 더 낮은 계층에 있습니다; 규칙의 계층 번호가 더 크면, 더 높은 계층에 있습니다.

규칙 R1에서 규칙 R2로 향하는 모든 간선에 대해, 해당 의존성 그래프가 속한 규칙 집합에서:

• 간선의 레이블이 closed이면, 해당 계층 번호는 R1의 경우 다음보다 엄격히 큽니다: 계층 번호(R2의).
• 간선의 레이블이 open이면, 해당 계층 번호는 R1의 경우 다음보다 크거나 같습니다: 계층 번호(R2의).

define stratification(ruleSet):

    let DP = Dependency graph for the rule set.
    let stratumMap be a map from rule to integer

    # 의존성 그래프는 층화 조건을 충족해야 합니다.
    # 상한 없는 층화를 검사하는 것은 방어 조치입니다
    # 층화 조건 위반에 대비하기 위한 것입니다.
    let limit = num rules + 1
    let maxStratum = 0

    # stratumMap을 초기화합니다
    foreach rule in ruleSet.rules:
        stratumMap.set(rule, 0)
    endfor

    let changed = true
    while changed:
        changed = false
        foreach edge E in DP:
            # pRule에서 qRule로 향하는 레이블이 있는 간선
            let pRule = source of edge
            let qRule = destination of the edge
            let label = edge label

            if label == "open":
                if stratumMap.get(pRule) < stratumMap.get(qRule):
                    stratumMap.set(pRule, stratumMap.get(qRule))
                    changed = true
                endif
            endif
            if label == "closed":
                if stratumMap.get(pRule) <= stratumMap.get(qRule):
                    let xStratum = 1 + stratumMap.get(qRule)
                    if xStratum > limit:
                        # 층화 요구 사항 위반
                        error "층화 오류"
                    endif
                    stratumMap.set(pRule, xStratum)
                    maxStratum = max(maxStratum, xStratum)
                    changed = true
                endif
            endif
        endfor
    endwhile

    # 결과 맵을 초기화합니다.
    let stratumRules be a map from integer to rules
    foreach i = 0 to maxStratum:
        stratumRules.set(i, {})
    endfor

    # stratumMap에서 계층 번호가 같은 규칙을 모읍니다
    foreach rule R in map stratumMap:
        let stratumNum = stratumMap.get(R)
        add R to stratumRules.get(stratumNum)
    endfor

    # 각 계층을 once와 general로 분할합니다
    let stratumLevels be a sequence of pairs of sets of rules
    foreach i = 0 to maxStratum:
        let rules = stratumRules.get(i)
        let once = { R in rules | R is a run-once rule }
        let general = rules \ once
        stratumLevels.set(i, pair(once, general))
    endfor

    the result is stratumLevels
enddefine

웹에서 문서를 읽는 작업에는 보안상 영향이 있습니다. 규칙 집합 가져오기 지원 여부는 SPARQL-RL 처리기에서 선택 사항입니다. 또한 구현은 부분적으로 지원할 수 있으며, 예를 들어 일부 규칙 집합의 가져오기만 지원하고 다른 규칙 집합은 지원하지 않거나, 검증된 사본에서만 가져오도록 할 수도 있습니다.

가져오기 처리에는 다음 조건이 적용됩니다.

• 규칙 집합 가져오기를 지원하지 않는 구현은 반드시 해당 규칙 집합에 IMPORTS 문이 포함되어 있으면 이를 거부하고 오류를 알려야 합니다.
• 부분적인 지원을 제공하는 구현은 반드시 지원하지 않는 가져오기를 발견하면 오류를 알려야 합니다.
• 구현은 반드시 가져오기 대상 문서를 해석할 수 없거나, 해당 문서가 구문상 유효하지 않은 경우 오류를 알려야 합니다.
• 처리기는 반드시 규칙 집합을 한 번만 가져와야 하며, 이는 무한 루프를 방지하기 위한 것입니다. IMPORTS 문을 처리할 때 적용됩니다.

하나의 해결된 규칙 집합은 다른 규칙 집합에서 가져오기에 언급된 모든 규칙 집합을 재귀적으로 읽어 생성되며, 이 가져오기는 해당 다른 규칙 집합에 속합니다.

알고리즘의 한 예는 B. 가져오기 알고리즘 예제에서 확인할 수 있습니다.

해 매핑

하나의 해 매핑 μ는 부분 함수 μ : V → T이며, 여기서 V는 모든 변수의 집합이고 T는 모든 RDF 용어의 집합입니다. μ의 정의역은 dom(μ)로 나타내며, 이는 V의 부분집합으로, μ가 정의되는 변수들로 이루어집니다. 용어 해는 다음을 의미한다는 것이 명확할 때 사용할 수 있습니다: 해 매핑. 해 매핑을 μ₀로 표기하며, 이때 dom(μ0)는 공집합입니다.

치환 함수

해당 치환 함수, 또는 간단히 치환은, 함수 subst(μ, 트리플 패턴)이며 반환하는 것은 하나의 트리플 패턴입니다. 이때 원래 트리플 패턴에서 변수 var가 다음에 속하면, dom(μ), 해당 변수의 모든 출현은 다음 RDF 용어로 대체되며, 이는 해 매핑이 var에 대해 제공하는 값입니다. 결과 트리플 패턴에 변수가 없으면, 이는 하나의 RDF 트리플입니다.

함수 subst(μ, 트리플 템플릿)도 유사하게 정의됩니다. 변수의 모든 출현은, 해당 트리플 템플릿에서, 다음 RDF 용어로 대체되며, 이는 해 매핑이 var에 대해 제공하는 값입니다.

템플릿 인스턴스 함수

해당 템플릿 인스턴스 함수는 함수 replaceBlankNodes(트리플 템플릿 목록)이며 이 함수는 다음의 목록을 반환합니다: 트리플 템플릿. 이때 각 빈 노드는 인수 내에서 새 빈 노드로 대체됩니다. 동일한 빈 노드가 여러 번 나타나면, 모두 동일한 새 빈 노드로 대체됩니다.

평가 그래프

하나의 평가 그래프는 하나의 RDF 그래프로, 해당 기본 그래프와 규칙 집합 평가 중 생성된 모든 트리플을 결합한 것입니다.

그래프 일치

하나의 그래프 일치가 찾는 것은 트리플 패턴을 다음에 있는 트리플에 매핑하는 방법입니다: RDF 그래프.

G를 하나의 RDF 그래프라고 하고, TP를 하나의 트리플 패턴이라고 합니다. 함수 graphMatch(G, TP)는 가능한 모든 해의 집합을 반환합니다. 이 해들을 트리플 패턴에 적용하면 생성되는 트리플은 그래프 G에 속합니다.

G를 하나의 RDF 그래프, TP를 하나의 트리플 패턴, 그리고 V를 TP에 나타나는 변수들의 집합이라고 합니다.

graphMatch(G, TP) = { μ | dom(μ) = V and subst(μ, TP) is a triple in G }

해 호환성

두 해 S1과 S2는 호환됩니다. 이는 변수의 값이 일치할 때이며, 그 변수들은 두 해가 공통으로 갖는 변수입니다.

S1과 S2를 해라고 합니다.

compatible(μ1, μ2) = true
                      if forall v in dom(μ1) intersection dom(μ2)
                          μ1(v) = μ2(v)
compatible(μ1, μ2) = false otherwise

해 시퀀스

하나의 해 시퀀스는 해들의 다중집합입니다. 시퀀스에 정의된 순서는 없습니다. 이는 순서 없는 목록과 동등하며 중복을 포함할 수 있습니다.

해 병합

두 해가 호환되면, 두 해의 병합 결과는 하나의 해이며, 각 해의 변수를 다음 RDF 용어에 매핑합니다. 해당 용어는 두 해 중 하나에서 가져옵니다.

μ₁, μ₂를 해 매핑이라고 하고, S1과 S2를 해 시퀀스라고 합니다.

merge(μ1, μ2) = μ such that
                    μ(v) = μ1(v) if v in dom(μ1)
                    μ(v) = μ2(v) otherwise

merge(S1, S2) = { μ |
                    μ1 in S1, μ2 in S2
                    and compatible(μ1, μ2)
                    μ = merge(μ1, μ2) }

참고

merge(μ1, μ2)의 정의역은 domain(μ1) ∪ domain(μ2)입니다.

두 해에 공통 변수가 없으면 두 해는 호환되며, 두 해의 병합 결과는 다음의 합집합입니다: μ₁과 μ₂.

유효 불리언 값

함수 EBV(x)는 유효 불리언 값을 반환하며, 그 대상은 하나의 RDF 용어입니다.

규칙 집합 평가에는 가져온 모든 규칙 집합을 수집하고 4.5 가져오기 처리에 설명된 대로 하나의 결합된 규칙 집합을 구성하는 과정이 포함됩니다.

그런 다음 다음 단계에 따라 결합된 규칙 집합을 평가할 수 있도록 준비합니다.

1. 4.2 정형성 조건에 설명된 대로 각 규칙이 정형 규칙인지 확인합니다.
2. 4.3.2 종속성 그래프 알고리즘에 설명된 대로 종속성 그래프를 계산합니다.
3. 4.4 계층화에 설명된 대로 결합된 규칙 집합의 계층화를 계산합니다. 4.4.2 계층화 알고리즘은 계층화를 계산하는 한 가지 방법을 제시합니다.

표현식은 필터 요소에서 사용되든 할당 요소에서 사용되든, 평가에는 하나의 해 매핑이 기준으로 사용됩니다. 해 매핑은 표현식의 각 변수에 대한 RDF 용어 값을 제공합니다. 4.2 올바른 형식 조건의 올바른 형식 요구 사항은 표현식의 모든 변수가 해 매핑에 나타나도록 보장합니다.

define evalFunction(F, μ):
    # F는 표현식이며, RDF 용어, 변수 또는 op(expr1, ..., exprN)입니다.
    #   여기서 op는 함수 또는 함수 형식입니다.
    # μ는 해 매핑입니다.

    # 평가 중 오류가 발생하면 evalFunction은 오류를 반환합니다.
    if F is an error:
        return error
    endif
    if F is an RDF term:
        return F
    endif
    if F is a variable:
        # 올바른 형식 조건에 따라 F ∈ dom(μ)입니다.
        return μ(F)
    endif
    # F는 F = op(expr1, ..., exprN) 형식입니다.
    if op is a functional form (e.g., IF, logical-or):
        # op에 정의된 방식으로 평가합니다. op는 일부 인수만 평가할 수도 있습니다.
        # 예를 들어, IF(c, t, f)는 c를 평가한 다음,
        # t 또는 f 중 정확히 하나만 평가합니다.
        return the value defined for op over expr1, ..., exprN under μ
    endif
    # op는 일반 함수이므로 모든 인수를 먼저 평가합니다.
    return op(evalFunction(expr1, μ), ..., evalFunction(exprN, μ))
enddefine

define evalAggregate(AGGF, SEQ):
@@
    # AGGF는 변수와 해 시퀀스를 인수로 받는
    # 집계 함수입니다. RDF 용어 값을 반환합니다.

    # DISTINCT는 COUNT에만 허용됩니다.
    # COUNT(*)는 특수한 경우입니다.
enddefine

하나의 규칙은 해 시퀀스를 규칙 본문에서 계산한 뒤, 각 해 매핑을 해당 해 시퀀스에서 가져와 트리플을 생성하는 데 규칙 헤드를 사용하는 방식으로 평가됩니다.

규칙 본문에서 빈 노드는 트리플 패턴 내에서 변수처럼 동작합니다. 이는 SPARQL 그래프 패턴 일치와 호환됩니다.

빈 노드를 변수로 취급

빈 노드는 트리플 패턴 내에서 변수로 취급되며, 이는 규칙 본문의 각 빈 노드를 해당 규칙에서 사용하지 않는 변수로 바꾸는 방식으로 이루어집니다. 여기에는 트리플 용어 내부의 빈 노드를 바꾸는 것도 포함됩니다. 동일한 빈 노드가 나타나는 모든 위치에는 동일한 변수를 사용하며, 서로 다른 빈 노드에는 각각 다른 변수를 사용합니다.

# 규칙 본문을 평가합니다.
# 이 함수는 해 시퀀스를 반환합니다.

define evalRuleElements(B, SEQ, G, GD):
    where
        B is a sequence of rule elements
        SEQ is a solution sequence
        G and GD are RDF graphs

    foreach rule element rElt in B:

        if rElt is a triple pattern element TP:
            X = graphMatch(G, TP)
            SEQ1 = {}
            foreach μ1 in X:
                foreach μ2 in SEQ:
                    if compatible(μ1, μ2):
                        μ3 = merge(μ1, μ2)
                        add μ3 to SEQ1
                    endif
                endfor
            endfor
        endif

        if rElt is a filter element F:
            SEQ1 = {}
            foreach solution μ in SEQ:
                let x = evalFunction(F.expr, μ)
                if x is not an error and EBV(x) is true:
                    add μ to SEQ1
                endif
            endfor
        endif

        if rElt is a negation element N:
            SEQ1 = {}
            foreach solution μ in SEQ:
                S = sequence{ μ }
                if N.evaldata:
                    NEG = evalRuleElements(N.inner, S, G, GD)
                else:
                    NEG = evalRuleElements(N.inner, S, GD, GD)
                endif
                if NEG is empty:
                    add μ to SEQ1
                endif
            endfor
        endif

        if rElt is an assignment element A:
            SEQ1 = {}
            foreach solution μ in SEQ:
                let x = evalFunction(A.expr, μ)
                if x is not an error:
                    # 매핑 A.var -> x를 해 μ에 추가합니다.
                    let μ2 be a solution mapping μ ∪ { (A.var, x) }
                    add μ2 to SEQ1
                else:
                    # 오류: 해 μ를 제외합니다.
                endif
            endfor
        endif

        ## COUNT(*)는 어떻게 처리하나요?
        if rElt is a group element GRP:
            SEQ1 = {}
            foreach solution μ in SEQ:
                let μp be the restriction of μ to GRP.keys
                let SEQX = evalRuleElements(GRP.pattern, { μp }, G, GD)
                # 해 매핑을 그룹에 배정합니다.
                let KGRP = empty map of solution mappings to solution sequences
                foreach solution μx in SEQX:
                    let μk be the restriction of μx to GRP.keys
                    if KGRP[μk] is defined:
                        add μx to the solution sequence KGRP[μk]
                    else:
                        KGRP[μk] = solution sequence of one element μx
                    endif
                endfor
                # 각 그룹에 대해 집계 함수를 계산하고,
                # 현재 해 매핑 μ를 그룹 키와
                # 집계 할당 결과로 확장합니다.
                foreach key K of map KGRP:
                    let X be the solution sequence of KGRP[K]
                    let Z be an empty solution mapping
                    foreach aggregation function F in GRP.aggregations:
                        let V = calculate F.function(X)
                        add solution mapping (F.var, V) to Z
                    endfor
                    Z = merge(Z, K)
                    Z = merge(Z, μ)
                    add Z to SEQ1
                endfor
            endfor
        endif
        SEQ = SEQ1
    endfor

    return SEQ
enddefine

define evalRule(R, G, GD):
    where
        R is a well-formed rule
        G and GD are RDF graphs
    let B be R.body
        treating 빈 노드를 변수로.

    # 어떤 변수도 매핑하지 않는 해 하나로 이루어진 해 시퀀스입니다.
    let SEQ0 be the solution sequence { μ0 }

    if R.evaldata:
        let SEQ = evalRuleElements(B, SEQ0, G, GD)
    else:
        let SEQ = evalRuleElements(B, SEQ0, GD, GD)
    endif

    # 규칙 헤드를 평가합니다.
    let OUT = empty set
    foreach μ in SEQ:
        let S = {}
        # 각 빈 노드를 새 빈 노드로 바꾼 규칙 헤드입니다.
        let HT = replaceBlankNodes(R.head)
        foreach triple template TT in HT:
            let triple = subst(μ, TT)
            add triple to S
        endfor
        OUT = OUT ∪ S
    endfor
    return OUT
enddefine

하나의 규칙 집합을 평가하는 것은 해당 규칙 집합의 각 계층을 실행하는 것으로 정의되며, 각 계층은 해당 규칙 집합의 계층화에 속하고, 다음 계층으로 이동하기 전에 순서대로 완전히 실행되어야 합니다. 계층은 이러한 순서에 따라 실행됩니다. 하나의 계층은 먼저 해당 계층의 각 일회 실행 규칙을 평가한 다음, 해당 계층의 일반 규칙을 새로운 트리플이 더 이상 생성되지 않을 때까지 반복해서 평가합니다.

let G0 be the input base graph
let RS be the rule set
let D be the graph of all DATA triples in RS

Apply stratification to RS

let LS be the sequence of layers after stratification

# 추론 그래프
let GI = { t ∈ D | t ∉ G0 }

# 평가 그래프: 기본 그래프와 데이터 블록
let GE = G0 ∪ D

foreach stratum ST in LS:
    foreach rule R in ST.once:
        let X = evalRule(R, GE, G0)
        let Y = { t ∈ X | t ∉ GE }
        GI = GI ∪ Y
        GE = GE ∪ Y
    endfor

    let finished = false
    while ! finished:
        finished = true
        foreach rule R in ST.general:
            let X = evalRule(R, GE, G0)
            let Y = { t ∈ X | t ∉ GE }
            if Y is not empty:
                finished = false
                GI = GI ∪ Y
                GE = GE ∪ Y
            endif
        endfor
    endwhile
endfor
the result is GI

버전 레이블은 SPARQL-RL의 구문 및 의미론에 대한 적합성을 식별하는 문자열입니다.

버전 선언은 힌트입니다. 이 선언은 문서의 앞부분에, 해당 버전에 의존하는 모든 기능보다 먼저 제시하는 것이 좋습니다.

여러 VERSION 지시문이 하나의 SPARQL-RL 문서에 나타날 수 있습니다. 각 지시문은 해당 지시문 다음에 나오는 문서 부분에 적용되며, 다른 지시문을 만나거나 문서의 끝에 도달할 때까지 적용됩니다.

버전 레이블은 version 매개변수로도 지정할 수 있으며, 이 매개변수는 미디어 유형에 속합니다. 현재 적용되는 VERSION 지시문이 없으면, 미디어 유형의 일부로 지정된 버전을 고려합니다.

공백 (생성 규칙 WS)은 그렇지 않으면 하나의 터미널로 잘못 인식될 두 터미널을 구분하는 데 사용됩니다. 아래에서 대문자로 표기된 규칙 이름은 공백이 중요한 위치를 나타내며, 이러한 규칙들은 SPARQL-RL 파서를 구성하기 위한 터미널의 한 가지 선택이 됩니다.

생성 규칙 String에서는 공백이 중요합니다.

주석은 IRIREF, STRING_LITERAL1, STRING_LITERAL2, STRING_LITERAL_LONG1 또는 STRING_LITERAL_LONG2 외부에 있는 #로 시작하며, 줄의 끝( LF 또는 CR로 표시됨)까지 계속됩니다. 주석 마커 뒤에 줄의 끝이 없으면 파일의 끝까지 계속됩니다. 주석은 공백으로 취급됩니다.

상대 IRI 참조는 통합 자원 식별자(URI): 일반 구문 [RFC3986]에 따라 기준 IRI를 사용하여 제5.2절의 기본 알고리즘만으로 해석됩니다. 구문 기반 정규화나 스킴 기반 정규화 (RFC3986의 제6.2.2절 및 제6.2.3절에 설명됨)는 수행되지 않습니다. IRI 참조에서 추가로 허용되는 문자는 국제화 자원 식별자 (IRI) [RFC3987] 제6.5절에 따라 URI 참조에서 예약되지 않은 문자를 처리하는 것과 동일한 방식으로 처리됩니다.

BASE 지시문은 [RFC3986] 제5.1.1절, "콘텐츠에 포함된 기준 URI"에 따라 상대 IRI 참조를 해석하는 데 사용되는 기준 IRI를 정의합니다. 제5.1.2절, "캡슐화 엔티티의 기준 URI"는 범위 내 기준 IRI가 xml:base 지시문이 있는 SOAP 봉투 또는 Content-Location 헤더가 있는 MIME 멀티파트 문서와 같은 캡슐화 문서에서 유래할 수 있는 방법을 정의합니다. 5.1.3, 검색 URI의 기준 "URI"에서 식별되는 "검색 URI"는 특정 SPARQL-RL 문서를 가져온 URL입니다. 위의 어느 것도 기준 URI를 지정하지 않으면 기본 기준 URI(제5.1.4절, "기본 기준 URI")가 사용됩니다. 각 BASE 지시문은 이전 기준 URI를 기준으로 새로운 범위 내 기준 URI를 설정합니다.

SPARQL-RL 문서에서는 세 가지 형태의 이스케이프가 사용됩니다.

• 숫자 이스케이프 시퀀스는 유니코드 코드 포인트의 값을 나타냅니다.

  숫자 이스케이프 시퀀스는 유니코드 서로게이트의 범위인 U+D800에서 U+DFFF까지의 코드 포인트 값을 생성해서는 MUST NOT 됩니다.

  이스케이프 시퀀스	유니코드 코드 포인트
  \u hex hex hex hex	네 개의 16진수 숫자를 최상위 자릿수에서 최하위 자릿수 순으로 해석하여 인코딩된 값에 해당하는, U+0000에서 U+D7FF까지 및 U+E000에서 U+FFFF까지의 범위에 있는 유니코드 코드 포인트입니다.
  \U hex hex hex hex hex hex hex hex	여덟 개의 16진수 숫자를 최상위 자릿수에서 최하위 자릿수 순으로 해석하여 인코딩된 값에 해당하는, U+0000에서 U+D7FF까지 및 U+E000에서 U+10FFFF까지의 범위에 있는 유니코드 코드 포인트입니다.

  여기서 hex는 16진수 문자입니다.

  HEX ::= [0-9] | [A-F] | [a-f]

• 문자열 이스케이프 시퀀스는 문자열 리터럴에서 전통적으로 이스케이프되는 문자를 나타냅니다.

  이스케이프 시퀀스	유니코드 코드 포인트
  \t	U+0009
  \b	U+0008
  \n	U+000A
  \r	U+000D
  \f	U+000C
  \"	U+0022
  \'	U+0027
  \\	U+005C

• 예약 문자 이스케이프 시퀀스는 \ 뒤에 ~.-!$&'()*+,;=/?#@%_ 문자 중 하나가 오는 형식이며, \의 오른쪽에 있는 문자를 나타냅니다.

여기에서 사용되는 EBNF는 XML 1.0 [EBNF-NOTATION]에 정의되어 있습니다.

이 문법의 텍스트 버전은 다음 파일에서 확인할 수 있습니다: sparql-rl-grammar.bnf.

이 문서에서는 일부 터미널 리터럴 문자열을 사용합니다. [EBNF-NOTATION]. 이러한 문자열에 사용된 유니코드 코드 포인트를 명확히 하기 위해 다음 표에서는 해당 터미널 리터럴 문자열에 사용된 구체적인 문자를 설명합니다.