转换为RA：双重含义/等同性

问题描述 投票：-1回答：1

（不，这不是那些将SQL转换为RA问题的人之一;-)我在一阶逻辑中有一个我希望在RA中表达的公式。这应该很容易：Codd 1972年在the Relational Completeness paper的方法是显示每个FOL算子可以在RA中等效表达。

给定关系SP：

  • 标题{S# CHAR, P# CHAR, QTY INT}
  • 关键{S#, P#}
  • 特征谓词SP（s，p，q）='供应商的供应量p的数量q'。

快递：'供应商'S1'和供应商'S2'提供完全相同的零件组（忽略数量）。

式：

∀p. (∃q1. SP('S1', p, q1) ) ⇔ (∃q2. SP('S2', p, q2) )

注意，如果S1根本不提供任何部件，这个公式是正确的，以防S2也不提供任何零件。

这是一个是/否问题（公式没有自由变量）;所以 我期待 RA表达式必须导致没有属性的关系，如果两个供应商不提供相同的零件集，则返回空关系（公式计算结果为假）;否则是没有属性的非空关系（公式计算结果为True）。

进一步解释一下：通常查询返回一个东西的列表 - 例如S1提供的部件列表，忽略数量：SP WHERE (S# = 'S1') {P#}（或希腊语π{P#}(σS# = 'S1'(SP))）。对于是/否问题，我们只对查询是否返回某些内容感兴趣，例如：供应商S1供应部分P456？：SP WHERE (S# = 'S1' AND P# ='P456') {}（π{}(σS# = 'S1'(σP# = 'P456'(SP)))）。

您会注意到我正在使用来自Date & Darwen的RA：Tutorial D的变体。这比Codd的原始RA更容易阅读和排版（我还包括希腊字符和下标表格）。我将自己限制在与Codd RA相对应的Tutorial D运算符中。

我可以做我想要的查询的反转：'是否有任何由S1提供的部件，但不是由S2提供，反之亦然？

首先是几个常见子表达式的缩写

WITH S1P := SP WHERE (S# = 'S1'){P#},
     S2P := SP WHERE (S# = 'S2'){P#} :

( S1P MINUS S2P )
UNION
( S2P MINUS S1P );

对于喜欢希腊语的人：

S1P := π{P#}(σS# = 'S1'(SP))
S2P := π{P#}(σS# = 'S2'(SP))
(S1P \ S2P) ∪ (S2P \ S1P)

这将返回一个空结果，以防两个供应商提供完全相同的零件组。所以剩下要做的就是将结果投射到没有属性的项目，并将空结果翻转为非空，反之亦然。但是Codd的RA没有办法表达这种翻转，AFAICT。

将Codd的1972方法应用于公式，最外层的操作是一个forall量词，所以将其转换为存在的否定：

¬∃p. ¬( (∃q1. SP('S1', p, q1) ) ⇔ (∃q2. SP('S2', p, q2) ) )

但现在最外面的操作是否定的。 Codd的方法只允许否定出现嵌套在连词中。

我被卡住了。有任何想法吗？

logic relational-algebra
1个回答
-1
投票

如果我们根据Codd的1972规范限制RA运算符和语义，则没有RA表达式可以回答这个问题。

即使我们最近添加了RA中通常包含的运算符，我们也无法回答所提出的问题。例如，wikipedia涵盖的运算符，例如Rename aka ρ，Extend（用于计算列），Grouping / Aggregation，Outer Joins。

可以说，从讨论来看，Codd并不支持所希望的结果（零度关系）。我说“可以说是”因为Codd从不严格定义“关系”。有Codd 1970脚注1“R是笛卡尔积S1 x S2 x ... x Sn的子集。”;但没有给n下限。显然，它打算包括n的退化'产品'为1，那么为什么不允许零？

例如，SQL不支持零度数表。 SQL确实支持使用虚拟列伪扩展一个可能为零的表：

SELECT 'Yes' AS Dummy FROM SP WHERE...

即使允许这样做，我也认为提出的问题无法在SQL中得到解答。 （考虑SP为空的情况：然后两个供应商提供相同的产品集，即空集;但FROM SP ...只能返回空关系。）

已经提出了各种非标准运算符或原语（参见关于q的评论和其他答案）。 AFAICT没有权威的参考资料“祝福”任何特定的方法。例如，the Alice Book似乎不考虑零度关系。

简要地调查可能的运算符/原语。 （其中任何一个都明显等同于任何其他，在某种意义上，如果我们有一个，我们可以用它来定义其他的 - 除了最后一个。）

那些返回真/假：

  • 关系比较：子集⊆，可用于定义关系==的相等性。 （这些要求操作数为'Union Compatible'。）
  • IS_EMPTY( )（出现在教程D中）。

返回true / false的困难在于RA中没有这样的原语。 （RA运营商通常被描述为“封闭关系”。）或者，这些运营商可以返回零度关系;但那么为什么不直接去那？

返回零度关系的人：

  • 补码操作，仅适用于零度关系。 （这是q中讨论的“翻转”操作。）
  • 使Dee成为一个原始 - 即非空零度关系。然后Dum =df Dee MINUS Dee;和r（必须是零度）的一般补充= df Dee MINUS r
  • 提供基元来表达关系文字/常量值，就像大多数编程语言支持表达数字或字符串文字或更复杂的数据结构一样。然后Dum/Dee只是众多关系常数中的两个。
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.