另请参阅 译文.
本页面是依据 W3C《RDF Dataset Canonicalization》制作的非官方中文译文,未经 W3C 认可。翻译可能存在错误;请以 2024 年 5 月 21 日英文推荐标准 为准。原版权及免责声明予以保留。参见 W3C 2023 许可与 NOTICE。
W3C Software and Document License (2023) https://www.w3.org/copyright/software-license-2023/ This work is being provided by the copyright holders under the following license. License By obtaining and/or copying this work, you (the licensee) agree that you have read, understood, and will comply with the following terms and conditions. Permission to copy, modify, and distribute this work, with or without modification, for any purpose and without fee or royalty is hereby granted, provided that you include the following on ALL copies of the work or portions thereof, including modifications: The full text of this NOTICE in a location viewable to users of the redistributed or derivative work. Any pre-existing intellectual property disclaimers, notices, or terms and conditions. If none exist, the W3C software and document short notice should be included. Notice of any changes or modifications, through a copyright statement on the new code or document such as "This software or document includes material copied from or derived from [title and URI of the W3C document]. Copyright © [$year-of-document] World Wide Web Consortium. https://www.w3.org/copyright/software-license-2023/" Disclaimers THIS WORK IS PROVIDED "AS IS," AND COPYRIGHT HOLDERS MAKE NO REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO, WARRANTIES OF MERCHANTABILITY OR FITNESS FOR ANY PARTICULAR PURPOSE OR THAT THE USE OF THE SOFTWARE OR DOCUMENT WILL NOT INFRINGE ANY THIRD PARTY PATENTS, COPYRIGHTS, TRADEMARKS OR OTHER RIGHTS. COPYRIGHT HOLDERS WILL NOT BE LIABLE FOR ANY DIRECT, INDIRECT, SPECIAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF ANY USE OF THE SOFTWARE OR DOCUMENT. The name and trademarks of copyright holders may NOT be used in advertising or publicity pertaining to the work without specific, written prior permission. Title to copyright in this work will at all times remain with copyright holders.
Copyright © 2010-2024 World Wide Web Consortium. W3C® liability, trademark and permissive document license rules apply.
RDF [RDF11-CONCEPTS] 描述一种基于图的数据模型, 用于对世界作出陈述,并为在该信 息图上进行推理奠定基础。有时 需要比较多组图的差异、为其添加 数字签名,或通过哈希算法为图 生成简短标识符。本文概述一种对 RDF 数据集 进行规范化的算法,使 这些操作成为可能。
本节描述本文 发布时的状态。当前 W3C 出版物列表和本技术报告的最新修订版 可在 W3C 技术报告索引 中找到,网址为 https://www.w3.org/TR/。
本文描述用于规范化 RDF 数据集的 RDFC-1.0 算法, 它源自 W3C 凭证社区组 以 [CCG-RDC-FINAL] 发布的输入成果。
发布时,[RDF11-CONCEPTS] 是定义 RDF 数据集 和 [N-QUADS] 的最 新推荐标 准,不过 W3C RDF-star 工作组正在更新规范。本规范以规范性 内容提供了一些来自相关更新规 范的依赖定义,预计在本规范未 来更新时,将它们替换为对更新 后 RDF 规范的规范性引用。
本文由 RDF 数据集规范化与哈希工作组 按 推荐标准轨道作为推荐标准发布。
W3C 建议将本规范作为 Web 标准广泛部署。
W3C 推荐标准是在广泛 建立共识后,得到 W3C 及其成员认可的规范;工作 组成员承诺对其实现提供 免许可费授权 。本推荐标准的未 来更新可能包含 新功能。
本文 由遵循 W3C 专利 政策的工作组制定。 W3C 维护与该组交付成果相关的 专利披露公开列表 ,该页面还说明如 何披露专利。任何 实际知悉某项专利 并认为其中包含 必要权利要求 的个人,必须按照 W3C 专利政策第 6 节披露该信息。
本文受 2023 年 11 月 3 日的 W3C 流程文档约束。
本节为非规范性内容。
数据科学家讨论规范化时, 通常着眼于实现一组特定目 标。同样的信息有时可以用 多种方式表达,因此经常需 要将这些不同表达转换为统 一的标准表示。有了标准表 示,就可以轻松确定两个数 据集之间的差异、为特定数 据集生成具有强密码学性质 的哈希标识符,或为数据集 添加数字签名以供日后验证。
具体而言,本规范处理的是由多个图组成的 RDF 数据集的规范化。有向图可以通过多种 方式表达同样的信息,因此需 要规范化才能实现上述目标,以 及其他可能偶然发现的用途。
就算法时间复杂度而言,大多数 RDF 数据集 可以相当快速地完成规范 化。但包含没有全局唯一 标识符的节点的数据集 更具挑战。其规范化涉及 图同构 问题,人们认为该问题在最坏 情况下难以快速求解。幸运的 是,现有现实数据即使会出现最 坏情况,也极为罕见;新数据 可以通过建模避免这种情况。实 际上,检测到问题数据集(见 7.1 数据集投毒)的软件系统可以将其视 为拒绝服务攻击尝试而非 真实输入,并中止处理。
本文概述 一种生成 RDF 数据集 的规范序列化形式的算法,其输入为一个 RDF 数据集 。它 称为 RDF 规范化算法 1.0 版 ,简称 RDFC-1.0。
RDF 1.1 概念与抽象语法 [RDF11-CONCEPTS] 对
带语言标签的字符串的表示不够
明确,其中 语言标签 的 xx-YY
形式被视为不区分大小写
。实现可能全部采用小写 xx-yy、保留
原形式 xx-YY,或使用
[BCP47] 的 格式惯例,从而产生不同的规范
形式和不同的哈希值。
参见 B. URDNA2015 ,了 解与 RDF 数据集规范化 [CCG-RDC-FINAL] 中发布的算法版本的比较。
图或数据集规范化在不同用例中具有重要作用:
处理许多此类用例需要规范化算法,但仅有它未必足够。RDF 图和数据集使用 空白节点 已有悠久历史,也带来不可避免的复杂性。空白节点有不同用途:
此外,RDF 语义规定,反序列化 RDF 文档会创建唯一的 空白节点,除非 能够确定 每次的 空白节点 都标识同一资 源。这是因为 空白节点标识符 属于具体 RDF 语法, 并不意图持久保存或跨 环境移用。在抽象 RDF 模型中,空白节点没 有标识符(不过某些 RDF 存储实现可能使用稳 定标识符,并选择让其 可移用)。更多信息参见 空白节点 一节([RDF11-CONCEPTS])。
RDF 确实允许通过 Skolem IRI以外部可识别的方式发布空白节点。它使特定 RDF 存储能够在具体语法中用 IRI替代空白节点,从而在该存 储中重复识别同一空白节点 ;但通常无助于在不同 RDF 存储或其他具体表示之间讨 论同一个图。无论如何,为 某一存储或序列化定义的稳定 空白节点标识符 都是任意的,通 常无法关联到 其使用上下文。
本规范定义一种算法,为同一 RDF 图(数据集)的不同序列化重复生成稳定的 空白节点标识符 。即使这些序 列化使用各自的 空白节点标识符 ,也可通过每个 空白节点 所连接的节点 确定其身份。 因此,对所得 规范化数据集的规范序列化进行哈希即可获得图 签名,以支持同构判定和数字签名 用例。本规范不定义这种图签名。
即使图(数据集)其他部分发生变化, 空白节点标识符仍可能稳定,因此某些 情况下可以计算两个图(数据集)的 差异,例如只修改了不含空白节点的三 元组,或引入的新空白节点不会与现 有空白节点造成自同构混淆。如果某些 信息改变了生成的空白节点标识符, 差异结果可能显示比实际更多的变化。 此外,如果起始数据集是 N-Quads 文档 ,可能可以将其原始空白节点标识符与 规范化数据集中分配的标识符关联起来。
虽然本规范可以使用其他 哈希算法 ,应用仍宜仔细 权衡替代哈希 函数的优缺点。 尤其是未标明 相关哈希算法的 规范 N-Quads 形式 或 已分配标识符映射 的表示。需 要重现相同 输出的用例 应明确表达 或传递生成 规范 N-Quads 形式时使用的内部哈希算法。
本文是 RDF 数据集 规范化算法的详细规范 ,主要面向以下读者:
理解本规范的基础内容需要熟悉基本 RDF 概念 [RDF11-CONCEPTS]。也建议具备 图论 和 图同构 的实用知识。
本节为非规范性内容。
本规范采用以下排版惯例:
markupmarkup definition reference markup external definition reference此区域提供有关相应步骤的更多信息。
例如,以下输出片段可以使用 [YAML] 格式描述某个实现的操作。
ca:
ca2:
bn_to_quads:
e0:
- _:e0 <http://example.com/#p1> _:e1 .
e1:
...
ca3:
- identifier: e0
h1dq:
nquads:
- _:a <http://example.com/#p1> _:z .
注释置于浅绿色框中,左侧为绿色边框,并带 有绿色“注”标题。注释始终属于参考性内容。
Examples are in light khaki boxes, with khaki left border, and with a numbered "Example" header in khaki. Examples are always informative. The content of the example is in monospace font and may be syntax colored. Examples may have tabbed navigation buttons to show the results of transforming an example into other representations. Code examples are generally given in a Turtle or TriG format for brevity, where each line represents a single triple or quad. Additionally, have the following implied directives: BASE <http://example.com/> PREFIX : <#> Following the Turtle/TriG syntax rules, blank nodes always appear in the `_:xyz` format.
除明确标为非规范性的章节外,本规范中的所有编写指南、图示、示例和注释也均为非规范性内容。其余内容均为规范性内容。
本文中的关键词 MUST、 MUST NOT和 SHOULD ,当且仅当像这里 一样全部大写时,按 BCP 14 [RFC2119] [RFC8174] 解释。
符合要求的处 理器是能够生成 规范 N-Quads 形式 的系统,该形式由 输入数据集 按照本规范定义的算法生成。
本规范中的算法具有规范 性,因为要一致地重现 相同的规范标识符,实现 MUST (必须)严格遵循算法所列步骤。
实现者可 以通过 RDF 数据集规范化测试套件中的测试用例,部分检查对本规 范的符合程度。但通过所有测试 并不意味着完全符合本规范,只 表示符合测试套件所检查的方面。
LF (换行,码点 U+000A)结尾。
实现 MUST (必须)支持指定 哈希算法的参数, MUST (必须)支持 SHA-256 和 SHA-384 [FIPS-180-4], 并且 SHOULD (应该)支持指定其他哈希算 法。采用其他哈希算法通常会 得到与默认算法不同的输出。
不要求对规范 N-Quads 结果生成哈希摘要的应用也使用默认哈希算法。
_: 开头,用作
空白节点的标识符。 空白节点标识符
通常是实现特有的局部标识符;本文规
定一种以确定性方式指定它们的算法。_: ,以区别于其他图节点
。这影响规范化算法,
因为它基于这种格式的 四元组 表示计算哈希。
true 和 falseA 和 B)的顺序
,使用 Unicode 码点排序确定。该排序由
[XPATH-FUNCTIONS]
定义,通过比较码点定义
全序
,作用于 字符串 。注意,对于 UTF-8
编码的字符串,比较字节序列与 码点顺序的结果相同。
规范化是将 输入数据集 转换为其 序列化规范形式的过程。也就是说,任 何包含相同信息的两个 输入数据集 ,无论如何 排列,都会转 换为相同的 序列化规范形式。这需要将有向图确定性地 排序为节点和边的集合。所 有节点都有全局唯一标识符 时很容易,否则可能很困难。 必须为没有全局唯一标识符 的节点分配确定性的标识符。
本规范定义的 规范化数据集 包含空白节点的稳定标识符;实际使用 时始终会生成该数据集的规范序列化。
将来可能存在多种规范化算法,因此为便于识别,本算法命名为“RDF 规范化算法 1.0 版”(RDFC-1.0)。
图 1 概述 RDFC-1.0,其中步骤 1 至 7 对应 4.4.3 算法中的相应步骤。
此图概述 RDFC-1.0 算法。输入文档被反序列化 为输入数据集和输入空白节 点标识符映射。执行规范化 步骤 1–6,生成包含输 入空白节点标识符映射及已 分配标识符映射的规范化数 据集。步骤 7 创建规范 化数据集的规范 N-Quads 形式。
本节为非规范性内容。
为确定规范标记, RDFC-1.0 考察与各空白节 点相连的信息。 一度信息唯一的节 点可以立即通过 分配标识符算法获得规范标识符。一度 信息不唯一时,需要确 定整个数据集中与其传 递相连的全部信息。 4.6 对一度四元组进行哈希 通过一度哈希定义 节点的一度信息。
根据各空白节点的信息计算哈希。 这些哈希编码与各空白节点关联的 提及 。 哈希 (对于字符串 s), 是将 s 输入密码学哈希函数后所得 结果的小写十六进制表示。 RDFC-1.0 默认使用 SHA-256 [FIPS-180-4]。
执行规范化算 法时,使用名为 规范化状态的数据结构追踪状态很有帮助。 规范化状态 包含的信息如下。
c14n (canonicalization 的缩写)初始化,用于分配规范
空白节点标识符。
规范化算法为 空白节点分配标 识符。 分配标识符算法 使用 标识符发号器 完成此 任务。 标识符发号器 需要追踪的 信息如下。
c14n 是合适的
标识符前缀 初值,可生成
空白节点标识符 ,例如 c14n1。0。规范化算法将 输入数据集 转换为 规范化数据集 ;若判定输 入过于复杂 ,则引发错误 。它为所有 空白节点 分配确定性的标识符,这些节点属于 输入数据集。
本节为非规范性内容。
RDFC-1.0 对 RDF 数据集
进行规范标记,方法是为每个 空白节点 分配规范
标识符。在 RDFC-1.0中,RDF 数据集 D
表示为 四元组 < s, p, o, g >
的集合;图分量 g 为空,当且仅当
三元组 < s, p, o > 位于 默认图。对于两个 RDF
数据集,
RDFC-1.0 应当且仅当它们同构(即忽略空白节点标识符
后相同)时返回相同的规范标记四元组列表。
RDFC-1.0 由多个子算法组 成,下文逐一 介绍。首先给出 RDFC-1.0的总体概要。
本节为非规范性内容。
对于 典型 输入数据集,以下算法每步只需极少迭代。某些 极端情况下表现可能很差,尤其是 步骤 5。实 现 MUST (必须)通过引发适当 异常并提前终止,防御 潜在拒绝服务攻击。详见 7.1 数据集投毒 。
实现可 以限制 4.8 对 N 度四元组进行哈希 的调用次 数,依据是 哈希到空白节点映射中的空白节点数。对 于大多数典型数据 集,每个空白节点在 4.8 对 N 度四元组进行哈希 中迭代超过几次是不常见的。
此操作初始化 空白节点到四元组映射和 哈希到空白节点映射,并实例 化新的 规范发号器。
算法完成 后,可用 输入空白节点标识符映射 状态 和 规范发号器 , 将 输入数据集 中的空白节点同时关联到其 原标识符及规范标识符。
建立 空白节点到四元组映射,通过输入数据集中各节点到 所分配标识符的映射,将每个 空白节点 关联到以其为组成部分的 四元组 集合 。
记录 空白节点到四元组映射的状态:
# Blank node to quads map for unique hashes example
ca:
log point: Entering the canonicalization function (4.4.3).
ca.2:
log point: Extract quads for each bnode (4.4.3 (2)).
Bnode to quads:
e0:
- <http://example.com/#p> <http://example.com/#q> _:e0 .
- _:e0 <http://example.com/#s> <http://example.com/#u> .
e1:
- <http://example.com/#p> <http://example.com/#r> _:e1 .
- _:e1 <http://example.com/#t> <http://example.com/#u> .
...
此步骤为输入文档中的每个空白 节点创建哈希。有些节点产生唯 一哈希,其他节点可能共享哈希。
记录 对一度四元组进行哈希算法的结果。
# First degree hashes for unique hashes example ca: ... ca.3: log point: Calculated first degree hashes (4.4.3 (3)). with: - identifier: e0 h1dq: log point: Hash First Degree Quads function (4.6.3). nquads: - <http://example.com/#p> <http://example.com/#q> _:a . - _:a <http://example.com/#s> <http://example.com/#u> . hash: 21d1dd5ba21f3dee9d76c0c00c260fa6f5d5d65315099e553026f4828d0dc77a - identifier: e1 h1dq: log point: Hash First Degree Quads function (4.6.3). nquads: - <http://example.com/#p> <http://example.com/#r> _:a . - _:a <http://example.com/#t> <http://example.com/#u> . hash: 6fa0b9bdb376852b5743ff39ca4cbf7ea14d34966b2828478fbf222e7c764473 ...
此步骤为哈希唯一的空白节 点确定规范标识符,并记录在 规范发号器中。
记录已分配的规范标识符。
# Assigned canonical identifiers for shared hashes example ca: ... ca.4: log point: Create canonical replacements for hashes mapping to a single node (4.4.3 (4)). with: - identifier: e2 hash: 15973d39de079913dac841ac4fa8c4781c0febfba5e83e5c6e250869587f8659 canonical label: c14n0 - identifier: e3 hash: 7e790a99273eed1dc57e43205d37ce232252c85b26ca4a6ff74ff3b5aea7bccd canonical label: c14n1 ...
此步骤为共享哈希的空白节 点确定规范标识符。按照上 一步哈希的顺序,逐一处理 尚无规范标识符的节点,为 对 N 度四元组进行哈希算法遍历到的全部 空白节点创建 唯一标识符。
记录本轮的 hash 和 identifier list 。
# Hash and Identifier List for each iteration of step 5 using shared hashes example ca: ... ca.5: log point: Calculate hashes for identifiers with shared hashes (4.4.3 (5)). with: - hash: 3b26142829b8887d011d779079a243bd61ab53c3990d550320a17b59ade6ba36 identifier list: [ "e0", "e1"] ... ...
此列表将在步骤 5.2中填充,用于为共享一度哈 希的空白节点确定顺序。
b初始化。包含每次调用 对 N 度四元组进行哈希算法的日志。
# Logs from calls to Hash N-Degree Quads algorithm for shared hashes example ca: ... ca.5: log point: Calculate hashes for identifiers with shared hashes (4.4.3 (5)). with: - hash: 3b26142829b8887d011d779079a243bd61ab53c3990d550320a17b59ade6ba36 identifier list: [ "e0", "e1"] ca.5.2: log point: Calculate hashes for identifiers with shared hashes (4.4.3 (5.2)). with: - identifier: e0 hndq: log point: Hash N-Degree Quads function (4.8.3). identifier: e0 issuer: {e0: b0} ... ... ... ...
上一步为共享一度哈希的空白 节点创建了临时标识符,现 在利用它们生成规范标识符。
记录新分配的规范标识符。
# Newly issued canonical identifiers from step 5.3 for shared hashes example ca: ... ca.5: log point: Calculate hashes for identifiers with shared hashes (4.4.3 (5)). with: - hash: 3b26142829b8887d011d779079a243bd61ab53c3990d550320a17b59ade6ba36 identifier list: [ "e0", "e1"] ... ca.5.3: log point: Canonical identifiers for temporary identifiers (4.4.3 (5.3)). issuer: - blank node: e1 canonical identifier: c14n2 - blank node: e0 canonical identifier: c14n3 ...
记录算法完成时 规范发号器 的状态。
# Canonical issuer state after step 6 for shared hashes example
ca:
...
ca.6:
log point: Issued identifiers map (4.4.3 (6)).
issued identifiers map: {e2: c14n0, e3: c14n1, e1: c14n2, e0: c14n3}
严格来说,不 同实现返回的 规范化数据集 可能将特定空白节点映 射为不同标识符。不 过,这只发生在数据集 存在同构,使两个实 现输出的规范序列化表 示仍相同的情况下。
序列化规范形式 是 N-Quads 文档,其中空白节点标识符取自各节点关联的规范标识符。
规范化数据集 由原始 输入数据集、 输入空白节点标识符映射(包 含 输入数据集中各空白节点 的标识符)以及 规范发号器组成。发 号器包含 已分配标识符映射 ,将 输入空白节点标识符映射 中的标识符关联到规范标识符。
本算法分配新的 空白节点标识符 ,对应给 定的现有 空白节点标识符,并更新 追踪新 空白节点标识符 分配顺序的状态。为数据集中与 其他节点同构的空白节点进行规 范标记时,分配顺序很重要。
算法维护 已分配标识符映射 ,将
现有 空白节点标识符 (来自 输入数据集
)关联到新的 空白节点标识符 ;在给定 标识符前缀
(c14n)后附加递增数字以分
配新标识符。例如,对 e3调用时,
可能分配 c14n1。
输入为 标识符发号器 I 和 existing identifier ,输出为新的 issued identifier。算法步骤如下:
本算法计算 哈希 ,针对给定 空白节点 ,覆盖包含该节点的 四元组 ,这些四元组位于 数据集 中。若哈 希唯一标 识该节点 ,无需进一 步检查。 否则,使用 4.8 对 N 度四元组进行哈希 为其创建哈希,由 4.4 规范化算法调用。
本节为非规范性内容。
为判定节点 n 的一度信息是否 唯一,分配一个 哈希 给其 提及集 Qn。空 白节点 n的一度哈 希记为 hf(n),是 运行 4.6 对一度四元组进行哈希 并传入 n所得结果。一度哈希唯一的 节点具有唯一的一度信息。
为保持一致, 空白节点标识符 在 Qn
中的使用,会在该四元组的 规范 N-Quads 序列化中替换为占位符。
每个空白节点分量替换为 a 或 z,取决于该
分量是否为 n 。
然后将序列化四元组按 码点顺序排序、拼接 并计算哈希 。结果就是 n的一度哈希 hf(n)。
本节为非规范性内容。
本算法以 规范化状态 和 reference blank node identifier 为输入。
记录运行本算法的输入和结果。
# Inputs and hash result for the Hash First Degree Hash algorithm for unique hashes example
h1dq:
log point: Hash First Degree Quads function (4.6.3).
nquads:
- <http://example.com/#p> <http://example.com/#q> _:a .
- _:a <http://example.com/#s> <http://example.com/#u> .
hash: 21d1dd5ba21f3dee9d76c0c00c260fa6f5d5d65315099e553026f4828d0dc77a
本算法计算 哈希 ,针对给定 空白节点 ,覆盖包含该节点的 四元组 (位于 数据集 中),适用于这些四元组 的哈希无法唯一标识该节 点的情况。它将搜索从直 接引用该节点的四元组( 提及集)扩展到其他四元组:这些四 元组包含的节点也是提及集 中某些四元组的分量。这称为 传播路径。过程逐步增加 间接层次,直到 获得唯一哈希。
本节为非规范性内容。
通常,判定图中两个节点是否 等价,只需比较标识符。但节 点没有标识符时,就必须确定 它们在整个图中是否以等价 方式连接到等价节点。这就是 图同构 问题。本算法借助在纸上绘图的 思路处理它。可以将图画两次来 检验节点是否等价:第一次将第 一个节点画在纸中央;若第二次 把第二个节点置于中央,仍能画 出与第一次完全相同的图,则两 节点等价。本算法实质上定义一 种确定性的绘图方式:从特定节 点开始,图总会以同样方式画出 。如果从两个不同节点出发画出 的两个图相同,则节点等价。 哈希 表示某种特定绘图方式 ,可用来比较节点。
当两个空白节点的一 度哈希相同时,需要额 外步骤检测全局,即 N度差异。必须考虑通过其他空白节点,以 任何方式(包括传递方式)连接到空白节点 n 的全部信息。
为考虑所有传递信息,算法 遍历并编码所有可能的关联 提及 路径,它们从 n出发,称为 传播路径,到达 连接到 n的每个未标记空白节点。各未 标记节点按探索路径上的到达 顺序分配临时标识符。为到达 关联空白节点而遍历的提及, 通过相关哈希编码到路径中。 由此,无需依赖输入空白节点 标识符,即可确定性地排序从 n 出发、到达所 有关联空白节 点的全部路径。
本算法与主规范化算法协 作,为特定空白节点生成唯 一、确定性的标识符。此 哈希 包含连接到节点的全部信息 及其连接方式;实现方法是创 建从该节点出发、穿过其他 相邻空白节点的确定性路径。
最终,算法选择最短的 传播路径 (依据其字符串编码) ,按未标记空白节点在 路径中的出现顺序分配 规范标识符。这条最短 编码路径的哈希称为 n的 N 度哈希,用于区分 n 与数据集中的其他空白节点。
为明确起见, 传播路径 以字符串 s 编码,若满足以下条件则认为它最短:
例如, abc 比 bbc短, 而 abcd 比 bcd长。
以下概要说明 n 的 N 度哈希如何沿最短 传播路径计算。注意,完整算法 考虑所有传播路径,最 终返回编码后最短路径的 哈希 。
如上文 步骤 2.3所述, HN 在沿所 探索的 传播路径 首次到达各未标记空白节点时递 归处理它。可将此看作沿路径从 n 移动到正在获得临时标识符的节点 ni 。若递 归处理 ni时发现另一个 未标记节点 nj ,算法再次 递归。这样的 递归描绘了 传播路径 :从 n 到 nj ,途经 ni。
递归哈希 r(i) 是返回的 哈希 ,来源是 在节点 ni 上完成的递归,发生于计算 hN(n)时。 正如 hN(n) 是 Dn的哈希, 将递归处理 ni 时的待哈希数据记为 Di。因 此 r(i) = h(Di)。对于每 个相关哈希 x ∈ Hn, Rn(x) 称为算法对其递归的 递归列表 。
本节为非规范性内容。
此算法输入为 规范化状态、 identifier (待递归计算四元组哈希的 空白节点 的标识符), 以及路径标识符 issuer ;后 者是 标识符发号器 ,发放临时 空白节点标识符。输出 为一个 哈希 及辅助生成该哈希的 标识符发号器 。
记录算法输入。
# Inputs for the Hash N-Degree Quads algorithm for double circle example
hndq:
log point: Hash N-Degree Quads function (4.8.3).
identifier: e0
issuer: {e0: b0}
...
quads 是 提及集合 ,对应于 identifier。
记录 提及集合 (对应于 identifier)中的四元组。
# Inputs for the Hash N-Degree Quads algorithm for double circle example
hndq:
identifier: e0
log point: Hash N-Degree Quads function (4.8.3).
issuer: {e0: b0}
hndq.2:
log point: Quads for identifier (4.8.3 (2)).
quads:
- _:e0 <http://example.org/vocab#next> _:e1 .
- _:e0 <http://example.org/vocab#prev> _:e1 .
- _:e1 <http://example.org/vocab#next> _:e0 .
- _:e1 <http://example.org/vocab#prev> _:e0 .
...
此循环计算相关哈希 Hn ,针对 提及集合 (对应于 identifier)内的其他空白节点。
纳入 相关空白节点哈希算法 每次迭代的日志以及结果 Hn。
# Step 3 of Hash N-Degree Quads using double circle example
hndq:
identifier: e0
log point: Hash N-Degree Quads function (4.8.3).
issuer: {e0: b0}
...
hndq.3:
log point: Hash N-Degree Quads function (4.8.3 (3)).
with:
- quad: _:e0 <http://example.org/vocab#next> _:e1 .
hndq.3.1:
log point: Hash related bnode component (4.8.3 (3.1))
with:
- position: o
related: e1
h1dq:
log point: Hash First Degree Quads function (4.6.3).
nquads:
- _:z <http://example.org/vocab#next> _:a .
- _:z <http://example.org/vocab#prev> _:a .
- _:a <http://example.org/vocab#next> _:z .
- _:a <http://example.org/vocab#prev> _:z .
hash: 60dc8fc7b5481014b6ea38efb05455676d1e93e19b99119ab294941dacc16b3b
input: "o<http://example.org/vocab#next>60dc8fc7b5481014b6ea38efb05455676d1e93e19b99119ab294941dacc16b3b"
hash: 20bb08971220a5382a9a06ba2977c5fb859e63192e0b2015a378af89e453f25e
- quad: _:e0 <http://example.org/vocab#prev> _:e1 .
...
Hash to bnodes:
20bb08971220a5382a9a06ba2977c5fb859e63192e0b2015a378af89e453f25e:
- e1
1e4e55ba02b8b0b527c32e2343fbcfee2e2bd9c1972c67cc01f85fabde7bc42d:
- e1
56d0774755aaf8d9cf4da8af3728e5589f94e5cd7d9aee86f0c5a7bc1d71c7ca:
- e1
2a5dd448b9467a08479008a5350829441868b7f913343cd500fe8619e047cff4:
- e1
...
此循环探索 传播路径 ,针对 相对于 identifier 而具有共同相关哈希的各个相关空白节点,找出其中最短的路径(chosen path)。这决定了如何为 原本哈希相同的空白节 点选择规范标识符。
每条路径由各相关空白 节点标识符的串接表示 :这些标识符或为已发 放的标识符,或为使用 issuer的副本创建的临时标识符 。获发临时标识符的节点 稍后用此算法递归处理。
记录 related hash 的值和 data to hash的状态。
# Log related hash and data to hash in each iteration of step 5 for double circle example.
hndq:
log point: Hash N-Degree Quads function (4.8.3).
identifier: e0
issuer: {e0: b0}
...
hndq.5:
log point: Hash N-Degree Quads function (4.8.3 (5)), entering loop.
with:
- related_hash: 1e4e55ba02b8b0b527c32e2343fbcfee2e2bd9c1972c67cc01f85fabde7bc42d
data_to_hash: ""
...
记录每个 排列 p。
# Log each permutation of step 5.4 using double circle example.
hndq:
log point: Hash N-Degree Quads function (4.8.3).
identifier: e0
issuer: {e0: b0}
...
hndq.5:
log point: Hash N-Degree Quads function (4.8.3 (5)), entering loop.
with:
- related_hash: 1e4e55ba02b8b0b527c32e2343fbcfee2e2bd9c1972c67cc01f85fabde7bc42d
data_to_hash: ""
hndq.5.4:
log point: Hash N-Degree Quads function (4.8.3 (5.4)), entering loop.
with:
- perm: [ "e1"]
...
_:及其
后 related的规范标识符附加到 path。
若规范标识符 由之前调用的 一度四元组哈希算法发放,则在调用此算法前可能已生成。对于已分配规范标识符的任 何相关空白节点,都不必再递归应用此算法。此外,使用规范标识 符还可进一步将其与临时标识符区分,提高查找所选路径的效率。
临时标记节点 的标识符记录在 issuer copy中,稍后用其递归调用 此算法,最终为所有节 点分配规范标识符。
_:及紧随其后的结果附加到 path。若 path 已长 于候选 chosen path,可提前终止 此次迭代。
path 用于在后续步骤生
成哈希;这一点类似 一度四元组哈希算法 ,它
使用 四元组 在 nquads 中的序列化形式来计算哈希。为保持一致,这些步骤使用
nquad 形式的空白节点标识
符,因此使用字符串 _: 。
记录 related 和 path。
# Log related and path of step 5.4.4 using double circle example.
hndq:
log point: Hash N-Degree Quads function (4.8.3).
identifier: e0
issuer: {e0: b0}
...
hndq.5:
log point: Hash N-Degree Quads function (4.8.3 (5)), entering loop.
with:
- related_hash: 1e4e55ba02b8b0b527c32e2343fbcfee2e2bd9c1972c67cc01f85fabde7bc42d
data_to_hash: ""
hndq.5.4:
log point: Hash N-Degree Quads function (4.8.3 (5.4)), entering loop.
with:
- perm: [ "e1"]
hndq.5.4.4:
log point: Hash N-Degree Quads function (4.8.3 (5.4.4)), entering loop.
with:
- related: e1
path: ""
...
用对每个获发临时标识符的相关空白节点递归调用此算法所得的哈希,扩展候选 path 。
记录 recursion list 和 path。
# Log related and path of step 5.4.5 using double circle example.
hndq:
log point: Hash N-Degree Quads function (4.8.3).
identifier: e0
issuer: {e0: b0}
...
hndq.5:
log point: Hash N-Degree Quads function (4.8.3 (5)), entering loop.
with:
- related_hash: 1e4e55ba02b8b0b527c32e2343fbcfee2e2bd9c1972c67cc01f85fabde7bc42d
data_to_hash: ""
hndq.5.4:
log point: Hash N-Degree Quads function (4.8.3 (5.4)), entering loop.
with:
- perm: [ "e1"]
...
hndq.5.4.5:
log point: Hash N-Degree Quads function (4.8.3 (5.4.5)), before possible recursion.
recursion list: [ "e1"]
path: "_:b1"
...
记录 related ,并纳入每 次递归调用 N 度四元组哈希算法的日志。
# Log related and path of step 5.4.5.1 using double circle example.
hndq:
log point: Hash N-Degree Quads function (4.8.3).
identifier: e0
issuer: {e0: b0}
...
hndq.5:
log point: Hash N-Degree Quads function (4.8.3 (5)), entering loop.
with:
- related_hash: 1e4e55ba02b8b0b527c32e2343fbcfee2e2bd9c1972c67cc01f85fabde7bc42d
data_to_hash: ""
hndq.5.4:
log point: Hash N-Degree Quads function (4.8.3 (5.4)), entering loop.
with:
- perm: [ "e1"]
...
hndq.5.4.5:
log point: Hash N-Degree Quads function (4.8.3 (5.4.5)), before possible recursion.
recursion list: [ "e1"]
path: "_:b1"
with:
- related: e1
hndq:
...
_:及紧随其后的
结果附加到 path。<、 hash (位于
result中)以及 > 附加到 path。若 path 已长 于候选 chosen path,可提前终止 此次迭代。
记录 chosen path 和 data to hash。
# Log chosen path and data to hash logs of step 5.5 using double circle example.
hndq:
log point: Hash N-Degree Quads function (4.8.3).
identifier: e0
issuer: {e0: b0}
...
hndq.5:
log point: Hash N-Degree Quads function (4.8.3 (5)), entering loop.
with:
- related_hash: 1e4e55ba02b8b0b527c32e2343fbcfee2e2bd9c1972c67cc01f85fabde7bc42d
data_to_hash: ""
...
hndq.5.5:
log point: Hash N-Degree Quads function (4.8.3 (5.5). End of current loop with Hn hashes.
chosen path: "_:b1_:b1<1ae899f76e760eb7caf6656437aaef845b50887aff7baeb3531add85ec02ed35>"
data to hash: "1e4e55ba02b8b0b527c32e2343fbcfee2e2bd9c1972c67cc01f85fabde7bc42d_:b1_:b1<1ae899f76e760eb7caf6656437aaef845b50887aff7baeb3531add85ec02ed35>"
...
记录 issuer 以及将 data to hash 传入 哈希算法的结果。
# Log issuer and resulting hash of step 6 using double circle example.
hndq:
log point: Hash N-Degree Quads function (4.8.3).
identifier: e0
issuer: {e0: b0}
...
hndq.6:
log point: Leaving Hash N-Degree Quads function (4.8.3).
hash: e332b4b59e1c4794ee72a4df0f63723326ffb6d6a5c0d0cb4d2dd8d8d5ebf5a4
issuer: {e0: b0, e1: b1}
本节说明创建序列化 [N-Quads] 表示的过程,表示对象是 规范化数据集。
序列化规范形式 (对于 规范化数据集
而言)是一个 N-Quads 文档 [N-QUADS]:
将每个 四元组 (来自 规范化数据集
)表示为 规范 N-Quads 形式,
按 码点顺序排序,再将它们串接。(每条
规范 N-Quads 语句都以换行符结
尾,所以串接时无需额外分隔
符。)结果文档的媒体类型为 application/n-quads,详
见 C. N-Quads 互联网媒体类型、文件扩展名与 Macintosh 文件类型
,载于 [N-QUADS]。
以 规范 N-Quads 形式序列化四元 组时,属于 空白节点 的分量MUST (必须)使用关联的规 范标签来序列化;每个 空白节点 的标签取自 已分配标识符映射 ,该映射是 规范化数据集的组成部分。
本节为非规范性内容。
规范化算法的特性使其输出(即规范标 签和四元组排序)与输入数据集固有关 联,尤其在数据集包含个人信息时可能 造成问题。例如,即使为保护隐私而从 规范化数据集 中删除某些信息,第三方仍可能 通过分析该数据集推断被省略的 数据。若必须解除算法输入与输 出的关联,应对规范化输出实施 适当后处理。本规范的设计有助 于简化额外处理,但建立在本规范 之上的其他规范须负责提供具体 细节。有关这类后处理方法,参见 选择性披露 ,载于 可验证凭证数据完整性 1.0 [VC-DATA-INTEGRITY] 。
本节为非规范性内容。
本节为非规范性内容。
规范化算法检查与空白节点相连信息 中的每一处差异,以确保各节点正确 获得自己的规范标识符。攻击者可能 利用此过程构造这样的数据集:已知其 规范化需耗费大量计算时间,但它不 表达有用信息,或以不必要的复杂方式 表达信息。算法实现者应添加缓解措 施,默认中止对有问题输入的规范化。
建议的缓解措施包括但不限于:
此外,使用该算法实现的软件可 采用模式验证的最佳实践,拒绝 不符合应用需求的数据,避免处 理无用的投毒数据集。但这些 措施取决于应用,并不直接适用 于规范化算法本身的实现者。
本节为非规范性内容。
默认 哈希算法 (由 RDFC-1.0 使用)可能在将来某时变得 不安全。为缓解此问题,本算 法及其实现可通过参数使用 不同哈希函数,无需改变规范 化算法本身。但使用不同哈 希算法通常会产生不同结果; 使用本规范的应用应慎重权 衡改用其他哈希函数的利弊。
内部哈希值不被公开,而且规 范化算法已设计为可处理一度 哈希碰撞,这减轻了默认哈希算 法变得不安全时的潜在影响。
本节为非规范性内容。
推动 RDF 数据集规范化算法开发的用例记录在单独的文档中,其中包含所作设计决策的更多背景和解释 [RCH-EXPLAINER]。
本节为非规范性内容。
这是一个更复杂的示例:图中经过空白节 点的相同路径重复出现,但使用不同的 空白节点标识符。
图像表示 以下代码块 描述的图。
_:e0 :p1 _:e1 .
_:e1 :p2 "Foo" .
_:e2 :p1 _:e3 .
_:e3 :p2 "Foo" .
以下 是 此处所载更详细执行日志的摘要。
本例展示另一个复杂示例: 节点沿相反方向双向连接。
图像表示 以下代码块 描述的图。
_:e0 :next _:e1 .
_:e0 :prev _:e1 .
_:e1 :next _:e0 .
_:e1 :prev _:e0 .
这里不详细讨 论该示例,但 此处 的执行日志展示了算法 中更复杂路径的例子。
本例展示一个 数据集,其中一 个图以 空白节点命名,该 节点也是 默认图中一个三元组的宾语。
图像表示 以下代码块 描述的数据集。
_:e0 :p1 _:e1 .
_:e1 :p2 "Foo" .
_:e1 :p3 _:g0 .
_:e0 :p1 _:e1 _:g0 .
_:e1 :p2 "Bar" _:g0 .
以下 是 此处所载更详细执行日志的摘要。
本节定义布局完全确定的 N-Quads 规范形式。语言的语法保持不变。
规范 N-Quads 更新并扩展了
规范 N-Triples ([N-TRIPLES]),
以纳入 graphLabel。
N-Quads 语法 [N-QUADS] 允许选择
RDF
数据的表示和布局,而 N-Quads
的规范形式为任意四元组提供唯一的语法表示。相关产生式允许选择表示方式时,每个码点只能使用
UCHAR、
ECHAR或未编码字符中的一种
方式表示。每个四元
组完全位于单独一行,
并采用指定的空白。
规范 N-Quads 对布局施加以下额外约束:
subject、
predicate、
object和
graphLabel之后;各
处的空白 MUST (必须)为单个空格(码点 U+0020)。http://www.w3.org/2001/XMLSchema#string
,则MUST NOT (不得)使用数据类型 IRI 这一 字面量组成部分
,而只用 STRING_LITERAL_QUOTE表示。
HEX MUST (必须)仅使用数字([0-9])和大写字母([A-F])。BS (退格,码点 U+0008)、
HT (水平制表,码点 U+0009)、
LF (换行,码点 U+000A)、
FF (换页,码点 U+000C)、
CR (回车,码点 U+000D)、
" (引号,码点 U+0022)以及
\ (反斜杠,码点 U+005C)
MUST (必须)使用 ECHAR编码。U+0000 至 U+0007范围内的字符、
VT (垂直制表,码点 U+000B)
、 U+000E 至 U+001F范围内的字符、
DEL (删除,码点 U+007F),以及
不匹配 Char 产生式([XML11])的字符,
MUST (必须)以 UCHAR
表示,采用小写 \u 后接 4 个 HEX。ECHAR 或
UCHAR
表示的所有字符,MUST (必须)使用其原生 [UNICODE] 表示。EOL MUST (必须)是单个 LF (换行,码点 U+000A)。EOL MUST (必须)提供。本节为非规范性内容。
RDF 数据集规范化 [CCG-RDC-FINAL] 描述了“通用
RDF 数据集规范化算法
2015”(URDNA2015)
,它
与 RDFC-1.0基本相同,实现 URDNA2015
的实现通常应与本规范
兼容。细微的变化在于 N-Quads 规范形式 :某些控制
字符原先未经
转义表示。 A. N-Quads 的规范形式
所定义的算法版本明确了 简单字面量 的表示
,以及 STRING_LITERAL_QUOTE
内使用 ECHAR编码的字符。
本节为非规范性内容。
本算法的早期版本已有少量部署。为便于识别,该算法称为“通用 RDF 图规范化算法 2012”(URGNA2012),与所述算 法有以下区别:
g而非 z序列化该值。< 和 >包围;没有任
何分隔符。p表示属性(property)方向,用于相关空白节点为
主语 的情况;值 r表示反向或引用方向,
用于相关空白节点为 宾语的情况。由于 URGNA2012 只规范化图而非数
据集,因此未使用 图名 位置。p 作为 position。
r 作为 position。
map)
map)
本节为非规范性内容。
xyz 格式的空白节点标识符,而非
_:xyz。讨论见 Issue 46
。
simple 标志。算法原
本设计为在
可用时使用已
分配的规范 空白节点标识符,而
非 _:a 或 _:z,类似于相关哈希
算法中的用法;但
在实现推进之前,
这段文字始终未加
入规范。因此哈希
永远不会变化,基于 simple
标志调用该算法的循环
便没有必要。讨论见 Issue 23 。
_: 。算法中仍然需
要它,但明确了
标识符与序列
化形式的区别。本节为非规范性内容。
本节为非规范性内容。
编辑感谢 Jeremy Carroll 对图规范化问题所做的工作,Andy Seaborne 和 Gavin Carothers 为本规范定义的算法提供宝贵反馈和测试输入,Tim Berners-Lee 爵士多年来对图规范化的思考,Jesús Arias Fisteus 对类似算法的研究,以及 Aiden Hogan,其出版物 [Hogan-Canonical-RDF] 对规范化问 题提供了重要的 当代分析,并为 RDFC-1.0的开发提供了独立依据。
编辑还感谢工作组主席 Phil Archer 和 Markus Sabadello,以及积极贡献对完成本工作至关重要的工作组成员:Pierre-Antoine Champin, Ivan Herman, David Lehn, Kazue Sako, Manu Sporny, Ted Thibodeau Jr.
RDF 数据集规范化与哈希工作组的成员包括 Ahamed Azeem, Ahmad Alobaid, Andy Seaborne, Benjamin Goering, Benjamin Young, Brent Zundel, Damien Graux, Dan Brickley, Dan Yamamoto, Daniel Pape, Dave Longley, David Lehn, Duy-Tung Luu, Gregg Kellogg, Ivan Herman, Jean-Yves Rossi, Jennifer Meier, Jesse Wright, Kazue Sako, Leonard Rosenthol, Mahmoud Alkhraishi, Manu Sporny, Markus Sabadello, Michael Prorock, Phil Archer, Pierre-Antoine Champin, Sebastian Crane, Ted Thibodeau Jr, Timothée Haudebourg, and Tobias Kuhn.
本规范基于 W3C 凭证社区组 的工作,以 [CCG-RDC-FINAL] 发布。社区组最终报告的贡献者包括:Blake Regalia, Dave Longley, David Lehn, David Lozano Jarque, Gregg Kellogg, Manu Sporny, Markus Sabadello, Matt Collier, Sebastian Schmittner.
本规范的部分工作由欧盟 StandICT.eu 2023 计划资助,分受助方合同编号为 No. 08/12 和 09/25。本规范内容不一定反映欧盟的立场或政策,不应据此推断其获得官方认可。
本规范的部分工作还由美国国土安 全部硅谷创新计划资助,合同编 号为 70RSAT21T00000020 和 70RSAT23T00000006。本规范内容不 一定反映美国政府的立场或政策 ,不应据此推断其获得官方认可。
工作组认识到,本规范的成功有赖 于学术界和产业界数十年来的长期 工作。我们感谢不断推进相关科学 研究、促成本规范完成的各位人士 。以下尽工作组所能回忆,列出部 分相关论文。无论有意还是无意, 未列入清单均不意味着这些论文对本 工作的开展没有同等重要的意义。
引用位置:
引用位置:
引用位置:
引用位置:
引用位置:
引用位置:
引用位置:
引用位置:
引用位置:
引用位置:
引用位置:
引用位置:
引用位置:
引用位置:
引用位置:
引用位置: