问题标签 [canonical-form]

拥有语言的规范表示通常很方便（在我的情况下，它们通常是特定领域的语言）；但是，我相信所涉及的语言的表达能力有严格的限制，这些语言决定了是否可以为该语言的任意程序确定和/或创建规范形式。不幸的是，我一直找不到我（模糊地）记得在其中读过的参考资料。

一方面，创建语言的规范表示与许多硬图问题（例如：图同构）具有相当的复杂性似乎是合理的，但另一方面，iirc、gcc、yhc 和 ghc 等编译器使用中间表示生成各种格式的输出（程序集、javascript 等），所以这至少在某些形式下是一个已解决的问题。

何时可以确定/生成给定语言的规范形式？（该语言的表达能力如何，语言表达能力如何影响规范形式的效用？）如果可能，请提供参考或证明。

编辑：例如，正则语言（例如：正则表达式的“纯”形式）不能表达图灵完备语言所能表达的许多相同的东西。换句话说，您不能用常规语言编写 Web 服务器，但可以使用 lambda 演算）。我的问题是关于理论上的可能性，并且确实有与复杂性理论有关的具体答案。如果我有一个 DSL 需要传输到另一个系统，那么在传输它之前生成该代码的规范形式通常是有益的，因为这将解耦两个不同系统使用的独立表示。 然而，如果将图灵完备语言翻译成规范形式是 P-Space 完备或 NP-Complete，那么您不应该浪费时间尝试构建规范形式——要么找到另一种方法，要么减少可以在多项式时间内规范化的语言复杂性。

假设我想做一个“优化的查询生成器”。基本上是一个 SQL 查询优化器，它比基于时间/空间限制的 SQL 服务器中的优化器要好得多。它将查询和数据库统计信息作为输入，并生成为目标系统量身定制的 SQL 查询，该查询将快速优化为几乎理想的计划。

需要支持多少 SQL？是否有一个 SQL 子集足够灵活，可以轻松描述最有用的查询，但又比完整的 SQL 小，值得将其缩减为？如果您不需要坚持“靠近机器”，还有更好的方法来描述查询吗？

我不是在考虑一个程序来处理现有的 SQL，而是一个用于创建新 SQL 的工具。只要输入语言能够描述查询的要求，实际上不需要将SQL 作为输入。

我想问题的另一种形式是：它们的 SQL 的任何部分是否仅用于性能并且从不提高可读性/可理解性？

正如有人指出的那样，这样做需要“大量特定于产品的知识”，并且（例如嵌套子查询与其他任何东西，应该使用什么样的索引，诸如此类）正是该工具旨在封装的内容这样用户就不需要学习这些知识。

注意：我对生成实际的查询计划不感兴趣，因为那是 DBMS 的工作，无论如何都不能从 SQL 中完成。我对一个系统感兴趣，该系统可以从不需要为该 DBMS 调整的输入中自动为给定 DBMS 生成良好的 SQL 的工作。

这实际上是一个机器学习分类问题，但我想有一个非常好的快速而简单的方法来做到这一点。我想将描述 NFL 球队的字符串（如“San Francisco”或“49ers”或“San Francisco 49ers”或“SF 49ers”）映射到球队的规范名称。（有 32 支 NFL 球队，所以这实际上只是意味着找到 32 个箱中最近的一个来放入给定的字符串。）

传入的字符串实际上并不是完全任意的（它们来自这样的结构化数据源：http ://www.repole.com/sun4cast/stats/nfl2008lines.csv ），因此并不需要像在上面的 49 人示例。

我还应该补充一点，如果有人知道包含拉斯维加斯赔率以及过去几年 NFL 比赛的实际比赛结果的数据来源，那就不需要这样做了。我需要规范化的原因是为了匹配这两个不同的数据集，一个带有赔率，一个带有结果：

• http://www.footballlocks.com/nfl_odds.shtml
• http://www.repole.com/sun4cast/freepick.shtml

非常欢迎关于更好、更可解析的数据源的想法！

补充：子串匹配的想法可能对这个数据就足够了；谢谢！是否可以通过选择距离最近的队名来使其更健壮一些？

我知道尽可能多地利用类非成员非朋友的接口是个好主意，而且我刚刚意识到对于我的 3D 矢量类“Vector3”，我可以移动 +=， -= 等运算符在类之外，只留下构造函数和复制赋值运算符。

问题是：这个操作符应该是什么样的？我见过许多其他运算符的规范形式并遵循了他们的建议，但我还没有看到这些运算符的规范形式。我已经给出了我认为应该在下面的内容。

第二个问题是：这些运算符到底叫什么？算术赋值运算符？

之前的（相关）代码：

到目前为止，我已将其更改为：

当我直接规范化一些 xml 时，我得到同一个 xml 文档的两个不同的哈希值，而不是当我对其执行数字签名时，它还在散列之前对 xml 执行相同的规范化算法？我发现数字签名规范化包括规范化时的换行符 '\n' 和空格字符，而直接算法不包括。

包括新行字符+空格不在规范化规范中吗？我专门看这个版本http://www.w3.org/TR/2001/REC-xml-c14n-20010315

有谁知道发生了什么？我已经包含了 xml 文档和代码的两个实现，所以你可以看到。

这真的让我很困惑，我想知道为什么，我错过了一些明显的东西吗？

直接规范化代码

xml数字签名代码

任何想法都会很棒！顺便说一句，这都是 C# 代码。

提前致谢

乔恩

我正在使用xmlseclibs尝试签署 SOAP 文档，但它似乎并没有以相同的方式规范化事物，具体取决于我是在签名还是验证。

我给你举个例子。这是我要签名的 XML：

我得到了一些在 PHP 中工作的代码，以使用公钥和私钥证书的组合对其进行签名，它似乎可以工作。它为<ds:Signature>元素添加了所有适当的东西，看起来很棒。但后来我在签名后立即尝试验证它，再次使用 xmlseclibs（和公钥证书）对其进行了测试，但验证失败。因此，完全相同的代码库正在执行签名和验证，但是由于某种原因这两个进程不同意。

我向 xmlseclibs 添加了一些调试代码以了解它在做什么，并且我意识到它提供的签名密钥和提供的验证密钥不同的原因是因为它在两种情况下对事物进行了不同的规范化。当我告诉它签署<samlp:Response>元素时，这是它签署的规范形式（为了便于阅读，我在此处添加了换行符）：

但是，当它验证签名时，这是它计算验证的规范形式（再次，我在这里添加了换行符）：

如您所见，这个版本省略了元素中的xmlns:saml属性<samlp:Response>，而第一个版本没有。（请注意，这与xmlns:samlp属性不同，后者包含在两者中。）这看起来很明显就像 xmlseclibs 中的一个错误，但尽管如此，如果我知道哪种规范形式是正确的，我很乐意自己修复它. 是否应该通过排他规范化省略该属性？还是应该包括在内？哪一种是正确的排他规范形式？

我目前在 google 和 yahoo siteexplorer 等中列出了我的网站的两个网址，索引的页面存在一些差异。

我需要两者，还是可以删除开头带有 www 的那个，然后让它使用新的 url 找到所有页面？我已经在 google 中设置了我的首选域，但在 yahoo 中看不到这样做的方法。

这甚至会对他们如何索引我的网站产生差异，还是只是为了让我可以访问统计信息等？

我的 .htaccess 全部设置为删除 www 反正。

非常感谢任何建议。

问题：使用阿姆斯特朗公理确定规范覆盖。给出你用来到达每一步的公理。

R = (A, B, C, D, E, F) F依赖性 = {A -> B, A -> C, CD -> E, CD -> F, B -> E}

我知道阿姆斯特朗的公理：联合、分解、伪及物性、自反性、扩充性和及物性。我也知道规范封面是什么。但是，我不知道如何使用阿姆斯壮公理来回答这个特定问题——我认为您通常会使用阿姆斯壮公理来计算 F+，而不是 cc。谢谢您的帮助。

我正在尝试将以下关系分解为 3NF：

所以我消除了冗余以获得规范的封面：

现在我正在尝试将其分解为 3NF。

我应该分解成r1(A, B, C) r2(B, D), r3(C, D). 那我该怎么办D -> A？

A -> B -> D -> A让我失望的事实。

我正在研究数据库概念，但有 3 个概念我不明白：规范覆盖、无关属性和闭包。我阅读了有关规范封面的定义，但我不了解它与 3NF 和 BCNF 的关系。规范覆盖的定义似乎是没有多余的属性，而多余的属性是不改变函数依赖集的闭包的属性，而闭包是 F 隐含的所有函数依赖的集合，一组函数依赖.

但这一切都有些模糊，我想知道一个直观的定义和如何计算

• 规范封面
• 关闭
• 无关属性

功能依赖性我相信我理解 - 如果我们在表中拥有这些属性，这就像表中的 PK 一样。

在数据库细化中有一个相当广泛的答案- F（无关属性）的最小覆盖，但我发现很难阅读所有集合定义和代数，我宁愿用简单的英语定义。

例如，具有模式 U={A,B,C,D,E,F,G} 和函数依赖

闭包 A+,B+,C+,D+,E+,F+ 是这样计算的吗？

如果我没记错的话，那么 BCDEFG 是 1NF/2NF 中的超级键（“整个键”），但它是最小的（3NF）吗？

在闭包和规范覆盖的帮助下，还应该做些什么来将此示例规范化为 1NF、2NF 和 3NF？规范覆盖与最小覆盖相同吗？