提问人：J. Mini 提问时间：12/4/2021 最后编辑：J. Mini 更新时间：12/7/2021 访问量：238
缺口和孤岛问题是否有正式的定义？如果是这样，这个问题是否满足它？
Is there a formal definition of Gaps and Islands problems? If so, does this problem satisfy it?
问：
似乎“间隙和孤岛”这个词在我的工作场所被过度使用。我最近在那个旗帜下基本上遇到了以下问题。
以一组包含许多行的数据为例，每行包含大量数据，但特别是，始终包含开始和停止时间列，并包含许多其他列，如果一个列不是 NULL，则其他列为 NULL。例如：
开始时间 停止时间 醉态 编程能力 01 60 0100 零 10 20 零 0450 40 50 零 0250 （您也可以使用明显的非枢轴等价物，但不要担心）
并将该数据转换为一种形式，其中所有数据都以这样一种方式折叠，这样您只需查看与该时间段相对应的单行，即可在任何给定时间找出真实情况。因此，对于前面的示例，您需要以下方法：
开始时间 停止时间 醉态 编程能力 01 09 0100 零 10 20 0100 0450 21 39 0100 零 40 50 0100 0250 51 60 0100 零 要了解这是否是您真正想要的，请查看原始行中的时间。在时间 10 之前，只给出“Dunkenness=0100”，因此结果中的第一行必须从 01 到 09，并且仅包含醉酒信息。原始表中的下一行从 10 到 20，因此我们在结果中必须有一行表示该时间段，并且它必须包含当时为真的任何信息（即“Drunkenness=0100”始终为真，“Programming Ability = 0450”仅在 10 到 20 次之间为真）。由于“编程能力”在时间 21 到 39 之间未定义，因此我们必须有另一行为 NULL。然后，其他两行由与前几行相同的过程生成，因此我们得到了上面的表格。
这真的是“缺口和孤岛”的问题吗？还是文献给它起了不同的名字？我同意第一个数据集中存在差距，并且最终数据集中的结果被拆分为岛屿，但这似乎不是文献在谈论“差距和岛屿”问题时所指的。文献似乎关心的是寻找差距或寻找岛屿，而不是将差距转化为岛屿并像这样合并数据。
之所以使用 SQL 标记，是因为这是一个关系数据库。我不是在寻求解决方案，我怀疑在您的答案中包含 SQL 解决方案会很有启发性，尽管它们会受到欢迎。因此，我没有在这个问题中包含任何SQL代码。
我不认为这个问题是基于意见的。我已经看到了足够多的关于差距和孤岛问题的报道，相信在某个地方必须对它们有一个正式的定义。强烈建议回答这些问题的正式定义及其来源。如果这不是间隙和孤岛问题，而是实际上是其他问题，那么请给出一个名称和来源定义。
答：
2赞
Igor N.
12/7/2021
#1
如果一个不是 NULL，则其他条件是 意味着您的行只是键、值对的不同表示形式。换句话说，它的非枢轴变体将如下所示
| 钥匙 | 价值 | 开始 | 结束 |
|---|---|---|---|
| 醉态 | 100 | 01 | 60 |
| 编程能力 | 450 | 10 | 20 |
| 编程能力 | 250 | 40 | 50 |
假设它通过了数据完整性检查，即同一键没有不同值的重叠间隔。然后它看起来像一个缓慢变化的 2 型维度，实际上我们可以将 20 到 40（排除）之间的编程能力值缺失解释为 NULL。
但是，也可以将该数据解释为两个单独的表，即按间隔的开始和结束日期合并（通过完全联接）的 Drunkenness 和 Programming Ability。
SELECT coalesce(a.start,b.start) as start, coalesce(a.end,b.end) as end,
a.Value, b.Value
from a full join b on a.start=b.start and a.end = b.end
因此，例如，b 缺少 （10,60） 的数据，并且在第一行中获得了 NULL 的编程能力。如果您正确地连接这两个表，则可以获得第二个表，以考虑时间间隔重叠。
SELECT greatest(a.start,b.start) as start, least(a.end,b.end) as end,
a.Value, b.Value
from a full join b on a.start <= b.end and b.start <= a.end
无论哪种方式，这都不完全是差距和岛屿的问题。在这个问题中，数据有一些重叠的间隔，可能有间隙，人们必须确定由不连续性间隙分隔的不重叠的连续性间隔。
评论