更新密集型数据集中天际线查询的优化算法

Journalof King Saud University沙特国王大学沙特国王大学学报www.ksu.edu.sawww.sciencedirect.com更新密集环境R.D. Kulkarni*，B.F. 某敏印度马哈拉施特拉邦Sangli Walchand工程学院计算机科学与工程系接收日期：2014年3月27日;修订日期：2015年3月7日;接受日期：2015年4月14日2015年12月2日在线发布摘要天际线查询产生的元组是“有前途的”用户的兴趣的维度。流行的数据集经常被用户查询，其中用户查询的维度经常重叠。对于这种频繁的、重叠的skyline查询，在大型数据集上重复计算会导致不可接受的响应时间。在查询维度中存在比流行维度的那些维度小的偏差的情况下，或者当数据集被更新时，先前结果的重用可以帮助避免或减少进一步的计算成本。在本文中，我们专注于这个问题，旨在优化响应时间的frequent或接近频繁的skyline查询提出的静态和更新密集型数据集。我们提出了两个新的，简单而有效的算法，即QPSkyline和QPUpdateSkyline算法，它利用所提出的数据结构，称为“查询Pro-文件”，其目的是保留天际线查询的元数据。 QPSkyline 算 法 工 作 在 静 态 环 境 中 ，QPUpdateSkyline算法适用于频繁更新的数据集在真实数据集上的实验表明了该算法的有效性和可扩展性。©2015作者。制作和主办由爱思唯尔B.V.代表沙特国王大学。这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍计算几何突出了*通讯作者。沙特国王大学负责同行审查数据的某些维度skyline查询的概念天际线查询有助于识别多属性数据集中的“最佳”对象。 为了理解skyline查询的概念，考虑一个人去Goa度假并寻找既便宜又靠近海滩的酒店的示例。这意味着这个人对所有这样的酒店感兴趣，这些酒店在两个方面都不比其他酒店差。这一组有趣的旅馆是“天际线”。 从地平线上看，人们可以在权衡个人偏好或强加偏好后做出决定。天际线的概念是第一个被提出来的http://dx.doi.org/10.1016/j.jksuci.2015.04.0031319-1578© 2015作者。制作和主办由爱思唯尔B.V.代表沙特国王大学。这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。制作和主办：Elsevier关键词Skyline查询;频繁查询;查询探查器448R.D. Kulkarni，B.F. 某敏Borzsonyi et al.（2001）的时间。他们将天际线定义为一组不受数据集中任何其他点支配的点。这一定义使用了“支配地位”的概念。当一个点在至少一个维度上优于其他点时，就说它支配其他点。例如，考虑图1（a）中所示的酒店样本数据集，其中包括酒店名称奖励和到海滩的距离等维度。元组h3在距离维度上支配所有其他元组，元组h1在奖品维度上支配所有其他元组。然而，由于查询中给出了多个首选项，元组h1和h3都用公式表示天空线。每一个其他的点都被说成是“出了天”！ 图 1（b）说明了这一概念。一个常见的观察是，数据集经常在流行的维度上被查询！用户可以生成仅特定于某些维度的查询，或者观察到与流行维度的查询略有偏差。在这种情况下，数据集特有的是存在一组频繁查询和一组接近频繁查询。 通过接近频繁的查询，我们指的是用户查询经常重叠的维度的所有那些查询。也就是说，要么涉及新的维度，要么从流行的维度集中跳过一些维度。在这种情况下，通过以某种方式维护频繁查询的简档，可以节省或最小化重新计算天际线查询的成本。如果我们以某种方式保存频繁查询的结果，并利用它们来优化未来频繁或接近频繁查询的响应时间，就可以做到这一点。数据集也会进行更新，如添加新记录，删除记录或更新字段值。在对数据集进行这样的更新时，针对先前处理的天际线查询重复天际线计算是无用的任务，因为更新可能并不总是影响现有的天际线。因此，问题是避免或减少重新计算的努力，只要对数据集进行的更新不影响各种查询的现有天际线。这就是我们研究背后的动机。我们的目标是在更新密集的环境中，通过保留查询的统计信息来优化频繁和接近频繁的skyline查询的响应时间。为了达到这个目的，我们提出了一种新的数据结构，称为“查询分析器”。我们还提出了算法然而，它在更新密集型环境中工作。通过本文，我们贡献如下：(1) 我们引入了“Query Profiler”的概念，(2) 我们提出了一个简单而有效的算法QPSkyline，它利用查询配置程序来优化频繁和接近频繁的skyline查询的响应时间。(3) 我们还提出了QPUpdateSkyline算法，旨在优化更新密集型环境中此类天际线查询的响应时间。(4) 我们提出的实验结果断言所提出的算法本文的其余部分组织如下。第二节简要回顾了与天际线计算相关的先前技术。在第3节中，我们讨论了Query Profiler（QP）的概念，以及QPSky- line算法 、 相关 实 验和 对 所 得结 果 的分 析 第 4节 介绍 了QPUpdateSkyline算法以及实验结果和相关讨论。第五节是论文的结论。2. 背景和相关工作给定n维关系R，元组ti（vi1，vi2，.. . ，v_in）支配其它元组t_j（v_j1，v_j2，.. . ..两个元组之间的优势由ti>tj表示。尺寸的首选项在天际线查询中指定。(for例如最小奖励、最小距离）。一个元组t被称为在关系的skyline中，如果在R中不存在任何其他元组，它支配t。Borzsonyi等人提出了skyline算子的概念（Borzsonyi等人，2001年）。他们提出了两种基本算法，即&BNL（由QPSkyline和QPUpdateSkyline使用）在主内存中维护一个不可比元组的窗口当从输入中读取元组p时，将其与窗口中的所有元组进行比较，如果发现它是支配元组，则将其从查询中删除。在另一种情况下（当它被发现是一个主导(a)酒店样本数据集（b）酒店图1示例数据集及其天际线。用于频繁查询的449tuple）它或者替换窗口中的一个元组（它所支配的那个），或者与窗口中的所有其他元组不可比，被添加到窗口中。 如果窗口在此过程中变满，则p被写入一个临时文件，该文件将在下一次迭代中进行处理。另一种算法DC对数据空间进行划分，迭代地计算每个数据空间的子轮廓线，直到数据空间非常小。子天际线的合并和消除恰好产生了最终的天际线。“排序过滤器天际线”（SFS Chomicki等人，2003），也是一个多通道算法BNL;然而，输入数据首先在拓扑上排序的尺寸兼容的天际线标准，算法进行之前。 这有助于减少优势测试的数量和skyline查询的初始响应时间。“线性消除排序的天际线”（LESS Godfrey等人，2005 ） 和 “ 排 序 和 限 制 天 际 线 ” （ S a L S aB a r t o l i n i 等 人 ， 2006年，在SFS之后发展。这两种算法也像在SFS中那样对输入数据进行预排序，并且还保留其所有优点，如限制要读取的输入元组的数量、渐进地返回结果、简化窗口的管理以及过滤阶段的最佳通过次数。在Kossmann et al. （2002），使用了一种完全不同的方法，称为位图。在位图算法中，每条记录都映射到一个m位向量，其中m是所有维度上不同属性值的总和。因为按位运算速度很快，所以在位向量上执行一系列简单的运算，如“与”或“，结果以位的形式反映记录的”优势强度“。对于各种数据集和高维查询，需要对数据集进行索引。 在Sheng和Tao（2012）中，研究工作集中在Skyline计算的最坏情况时间复杂度的改进上。利用基于索引的技术，避免了读取整个数据集，因为仅扫描索引的一部分以过滤可能的skyline候选元组。这就是使用索引结构的美妙之处和最终目标。研究人员使用各种索引结构来提高计算效率。一些流行的索引结构是B树、B+树、R树、R*树等。最简单的算法BBS（Papadias等人，2005）使用R树来索引数据，并使用最近邻布尔（NN）搜索来计算天际线。由于有效地利用了R树索引，BBS的性能优于以往的所有算法.另一种算法SUBSKY（Tao等人，2006）通过将多维数据集转换为1D值来对多维数据集使用单个B树索引，并通过启发式技术进行修剪。使用索引结构的其他算法是ZSearch（Lee等人，2007）、SSPL（Han等人，2013年）。现代硬件技术的出现鼓励研究人员利用机器的特殊性，如高速缓存，核心等，用于计算密集型算法。缓存用户查询的结果一直有助于提高以数据为中心的算法的响应时间和I/O性能 。 Dar 等 人 （ 1996 年 ） 、 Ren 和 Kumar （ 2001 年 ） 、Bhattacharya 等 人 （ 2011 年 ） 对 此 进 行 了 广 泛 研 究 。 在Bhattacharya et al. （2011），作者提出了缓存用户查询的语义 段 以 及 缓 存 替 换 策 略 的 想 法 。 一 些 智 能 结 构 ， 如SkyCube （ Xia 和 Zhang， 2005; Yuan等 人 ， 2005; Zhang等人，2014），天际线图（Zheng et al.， 2014年）也提出了。他们利用查询之间的相关计算依赖性，然而具有有限的高速缓存大小;该技术可能无法与所有SkyCube大小一起很 好 地 工 作 。 聚 类 的 概 念 已 被 用 于 阮 等 人 。（2013），其中基于skyline查询的预聚类已经应用于数据集以用于查询的并行计算。在这一领域的研究工作特有的移动自组网，概率数据，模糊数据，并行和分布式计算（Papapetrou和Garofalakis，2014）和其他技术也确实存在。然而，我们在这里不讨论它，因为它超出了当前研究工作的范围。在本文中，我们利用的概念，重用的skyline结果计算早期查询服务后续，frequent skyline查询和接近频繁的skyline查询与适当的管理和索引结构的帮助下：“查询分析器”（QP）。在Ren和Kumar（2001）、Bhattacharyaet al.（2011）、Xia et al. （2012）、Siddique和Morimoto（2010）、Siddique等人（2012年）。我们的研究工作与Bhattacharya 等 人 （ 2011 ） 的 研 究 工 作 不 同 ， 在Bhattacharya等人（2011）中，作者没有考虑数据集频繁更新的情况，这是显而易见的情况。此外，在我们提出的QP概念的帮助下，关于天际线查询的元数据被保留，因此可以在以后每次使用，无论何时将来针对数据集生成查询。这就是Bhattacharya中使用的缓存内存的好处等（2011年）。在Xia等人（2012）中使用的方法使用压缩SkyCube（CSC）的概念来返回任何子空间的天际线，而无需咨询基表。然而，我们的方法的好处是它的空间效率和简单性对所提出的立方体结构和相关的计算复杂性的内存需求。Siddique和Morimoto（2010）、Siddique等人（2012）中的研究工作涉及所有k-支配天际线查询结果的有效维护。作者利用数据集的性质来处理skyline查询，这对于更新密集的大型数据集来说是一项繁琐的工作。与此相反，我们专注于利用元数据的查询，这是更有效的，当查询重复或重叠。3. 查询分析器在本节中，我们将讨论与所提出的算法相关的术语，并对其效率进行评论。不失一般性，我们假设所有的skyline查询都是针对单个关系提出的。在接下来的讨论中，术语“查询”也指“天际线查询”。3.1. 处理后续skyline查询让我们首先讨论如何处理各种后续查询为此，让我们重温Bhattacharya et al.（2011）中讨论的查询分类。在关系R上生成的后续查询可以类似于以下之一：（1）它携带与某个先前查询完全相同的维度（精确查询），（2）它携带恰好是某个先前查询的维度的子集的所有那些维度（子集查询），(3)它承载着一些维度，这些维度恰好是一个子-450R.D. Kulkarni，B.F. 某敏几个先前查询的集合，并且还可以携带附加维度（部分查询），或者（4）其维度与任何先前查询的维度不匹配的查询（新查询）。用户触发的每个查询都可以在考虑之前按照上述顺序和方式进行分类for computation计算.现在让我们讨论如何处理后续查询。为了简化讨论，请考虑下面的样本数据集，并假设用户首选项是找到最小的可用维度。3.1.1. 精确查询对于每个新的查询，通过使用任何先前的算法计算天际线如果后续查询恰好是精确查询，则可以通过立即返回先前保存的那些结果来避免重新例如，在上面的图2（b）中，具有Qid=6的查询是精确查询，并且其天际线只不过是为具有Qid= 1的查询保存的天际线。3.1.2. 子集查询如果后续查询恰好是子集查询，则其天际线完全包含在其恰好是子集查询的先前查询的天际线例如，在上面的图2（b）中，Qid= 4的查询是Qid= 2的查询的子集查询。然而，注意，对于Qid= 2的查询，存在不在Qid= 4的查询的skyline中的元组还要注意，Qid= 4的查询也是Qid= 3的查询的子集查询在这种情况下，具有Qid= 2和Qid= 3的查询的天际线的相交可以用作用于计算具有Qid= 4的查询的天际线的初始集合只需要检查初始集合中的元组因此，可以在不再次引用数据集的情况下提供被分类为精确查询或子集查询的后续查询的天际线3.1.3. 部分查询如果后续查询恰好是部分查询，则其天际线可以如下计算当前查询恰好是查询的一部分的查询的天际线例如，Qid= 5的查询是Qid= 3的查询然而，部分查询的天际线可能包含不是其所部分的任何先前查询的天际线的一部分的元组。(The Qid= 5的skyline包含元组t0，其不是具有Qid= 3的查询的skyline的一部分）。请注意，一个查询可能是多个先前查询的一部分。（Qid= 5的查询也偏向于Qid= 1和2的查询）。在这种情况下，当前查询似乎是部分的所有这种先前查询的天际线的联合可以用作用于执行优势测试的初始集合。因此，为了满足上述可能性以及部分查询可能包含维度或维度集合的附加可能性，必须参考数据集，其中维度或维度集合不包含在部分查询所发生的任何先前查询的维度中。然而，以上述方式计算的初始集总是有帮助的，因为它作为第一个胜利-包 含 用 于 执 行 进 一 步 的 优 势 测 试 的 过 滤 元 组 的DOW。3.1.4. 新查询如果后续查询恰好是新查询，则其skyline从未被更早地计算过。它的天际线是以传统的方式计算的，即通过扫描整个数据集并使用任何以前的天际线计算算法。从这个讨论中可以清楚地看出，如果为用户查询保留了天际线，那么从可重用性的角度来看，保留的结果最适合精确查询和子集查询。对于部分查询，它们可以帮助加速计算。对于同一数据集生成的连续查询，部分查询或新查询可能变为精确查询或子集查询并且它们的天际线可以相对更快地被服务因此，我们的结论是，在频繁和重叠的查询由用户发射的情况下，需要一个结构，保持日志的各种统计数据的每个查询，以优化响应时间的天际线计算。我们将这种结构称为让我们详细讨论这个术语。3.2. 查询配置程序对于用户提出的每个skyline查询，我们打算保存查询的各种统计数据（或元数据），以便它们可以用于避免或减少结果的重新计算工作。这种统计数据应该以某种结构化的方式保存，以便有效地检索信息。我们将这些数据结构称为查询分析器（QP）。每个查询探查器都包含以下字段。查询ID（QId）：是每个查询的唯一标识号。属性（属性）：是用户查询中涉及的维度列表。如前面3.1节所述，它是对查询进行分类所必需的。Skyline（S）：是用户查询的skyline子集（Sb）：是查询id的列表，指示对于哪些不同的查询，当前查询看起来是子集。Partial（Pr）：是查询id的列表，指示对于哪些不同的查询，当前查询看起来是部分的。查询频率（Qf）：是一个正数，表示查询的频率。因此，查询分析器可以表示为QP= {QId，Att，S，Sb，Pr，Qf}。现在参考图2（b）来理解为Qid= 5的查询保存的查询分析器数据它被表示为QP5= {5，{1，4}，{0，1，2}，nil，{1，2，3}，1}，并解释如下：查询id 5查询维度1，4，其天际线是{0，1，2}。它恰好是前面两个查询的子集。（这里我们再次断言，按照给定的查询分类顺序进行它发生在Qid为1、2和3的查询的部分查询因此，这三个查询的天际线的并集被用作用于计算Qid= 5的该查询的天际线的初始集合。当它第一次出现时，它的频率被设置为1。现在让我们讨论如何实现QP。●●●●●●用于频繁查询的451(a)样本数据集(b)他们的天际线和分类图2示例数据集和查询分类。3.2.1. Query ProfilerQP可以以这种方式实现(i) 这是第一次，它被保存在主存储器中，为了有效访问，它通过使用散列索引进行索引。(ii) 对于数据集的后续使用，可以将其然而，当在运行时再次解析数据集上的查询时，它在主内存中进行管理。每当用户触发查询时，QP被搜索以将查询分类为精确查询、子集查询、部分查询或新颖查询。在QP中，每个精确和唯一的子集和部分查询仅存储一次。如果用户重复相同的查询，则QP的相关Qf字段每次递增1。对于每个新查询，在QP中完成单独的条目。在解决用户查询的过程中，当子集和部分查询被重复，它们最终变成精确查询。我们认为以下三种策略可以使QP上的搜索更有效。(i) 通过有效的索引管理QP。(ii) 保持QP大小最小。(iii) 保持QP在两个方面排序：查询频率和查询中使用的维度数量。下文讨论了这些战略使用散列索引使QP访问高效对于d维数据集，使用d位向量。被查询的查询中涉及的那些数据集维度在位向量中被设置为1，将未使用维度的剩余位设置为0。例如，如果所考虑的数据集是一个三维数据集，并且它的用户触发了一个涉及维度1和3的查询，那么位向量将是101和H（101）？QP（i），其中i只是QP中相关条目的位置。现在，在QP上进行有效搜索的另一个方面是，其大小应保持最小。QP大小可以通过以下方式管理：(i) 当子查询到来时，QP中先前条目的属性字段被搜索以分类查询。如果查询被分类为精确查询，则使用QP中的现有条目，并且查询的相关Qf字段递增1。如果查询被分类为子集、部分或新查询，则在QP中进行单独的条目，并且将查询的相关Qf字段设置为1。(ii) 对于反相关的数据集，两个不同的查询将具有相同的skyline的可能性很高。（参见图2（b）：Qid= 3和Qid= 7具有不同的尺寸，但具有相同的天际线。）在这种情况下，具有与新查询相同的天际线的旧查询的QP条目被重用。旧条目的Att字段相关的Qf字段递增1。上面提到的最后一种策略可以在不使用索引的情况下使用。我们的目标是通过保持QP始终排序来使QP上的搜索更有效。 我们通过对两个字段上的QP条目进行排序来实现这一点：Qf和Att。这意味着QP的最上面的条目总是用于最高频率的查询。表示查询频率的Qf字段在两种情况下递增：第一种情况是当查询重复时，第二种情况是当两个不同的查询具有相同的天际线时。因此，如果具有较高Qf的这些条目保持在QP中的顶部，则它们将在搜索期间被更早地访问。 此外，如果查询Q0具有更高数量的维度，则它是服务其他查询的更好候选，所述其他查询可以出现在Q0的子集或局部。因此，将具有较高维度的查询保留在QP中的较高侧是一个好主意。我们总结了这一讨论，给出了下面用户输入查询Q被接收，并且Q的维度的位向量被散列以知道Q在QP中的位置loc。Q是分类的。对于每个唯一的Q，在QP中维护单独的条目，并且如果Q不是唯一的（重复查询），则引用具有位置位置的条目以辅助Q的天际线计算。Q的每次重复出现导致相关Qf场增加1。IDA1A2A3A4t01102017T1210215T237186T3413218T4541610T5610121T6711227Qid查询尺寸天际线查询类型1{a1，a2}{t0，t2，t4}小说2{a1、a2、a3}{t0，t1，t2，t4，t5}小说3{a2、a3、a4}{t1，t2，t4，t5}小说4{a2，a3}{t4，t5}子集5{a1，a4}{t0，t1，t2}部分6{a1，a2}{t0，t2，t4}确切7{a3，a4}{t1，t2，t4，t5}子集452R.D. Kulkarni，B.F. 某敏3.3. QPSkyline算法上面解释的QP管理策略已经由QPSkyline算法处理。下面给出了该算法的伪代码算法1输入：Skyline查询Q，涉及d个维度输出：Skyline ofQ。1.开始QPSkylineQf=0）2. 初始化Q。(QId= 0，Att←d，S←u，Sb←u，Pr←u，3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.20.21.22.23.24.25.26.27.28.29.loc = hash（Q.Att）c=分类（Q）如果（c =精确）copy_profile（Q，loc）return（Q.S）end if如果（c =子集）get_other_parents_subsetStore_QP（loc）return（Q.S）endif如果（c =部分）get_other_parents_partial（Q）initial_set←union（skyline_of_parents_partialQ.S←交集（skyline_of_parents_subset（Q））store_QP（loc）return（Q.S）endif如果（c =新）Q.S compute_skyline_novel（（Q）store_QP（loc）return（Q.S）endifmatch_skylines（Q）sortQ.S←compute_skyline（initial_set）该算法解释如下：当用户查询到达时，算法首先使用哈希搜索来查看它是否预先存在。散列函数接受用户查询的维度，并且如果在QP中搜索查询，则给出位置loc，否则生成用于存储用户查询的QP的新位置查询分类由分类函数完成QP在locationloc和skyline处提供的确切查询copy_profile函数针对精确查询将Qf增加1。为了服务子集查询，当通过get_other_parents_subset函数找到子集查询时，查询发生的各种查询，修改相关的Q.Sb，并且通过交集函数计算它们的相关天际线的交集用户查询的QP由store_QP函数记录。对于部分查询，函数get_other_parents_partial找到用户查询作为部分查询出现的各种查询，更新Q.Pr字段，并且联合函数计算由函数get_other_parents_partial返回的查询的天际线的联合作为初始集合。在这个初始集合和数据集的帮助下，需要计算这是由compute_skyline函数完成的。该函数使用BNL（Borzsonyi等人，2001）算法来计算天际线。同样，用户查询的QP由stor-e_QP函数记录。被归类为新颖查询的用户查询由函数compute_skyline_novel提供服务，该函数通过扫描计算用户查询的skyline整个数据集，并使用传统的BNL算法。如前所述，新查询的天际线计算不受初始集合的为了帮助减少QP的大小，match_skyline函数可以工作。此功能旨在将先前的天际线与用户查询的天际线进行匹配同样，为了帮助减少QP上的搜索时间，QP应该按照查询频率的排序顺序进行管理，将流行的查询保持在顶部。最后的sort函数根据两个属性对QP进行排序：查询频率和查询中使用的查询属性的数量。因此，算法QPSkyline计算频繁和接近频繁的天际线查询的天际线。通过该算法，我们专注于重用早期的结果，这些结果由QP有效地管理，并且旨在将QP大小保持为最小以允许有效的搜索。实验结果验证了算法的有效性3.4. 实验结果：QPSkyline算法对于我们的工作，我们使用了可在www.basketball.com上获得的玩家的真实生活数据集。实验是在Intel Core i-32100 CPU、3.10 GHz、2 GB RAM、Windows 7环境下进行的。实验涉及天际线计算方法的性能比较，其中使用四种不同的技术计算天际线：（1）NQP：使用BNL的传统方法，（2）QP：使用QP概念的方法（没有排序和散列），（3）SQP：使用QPSkyline进行排序而不启用散列的方法，以及（4）SHQP：使用QPSkyline（启用排序和散列）的方法。实验评估响应时间对数据集的基数，数据集的维数和用户查询的数量的方差。结果讨论如下。对于第一个实验，我们设置n=3925，d=5。如图 3（a），当查询次数增加时，QPSkyline算法优于传统的skyline计算方法。这是显而易见的，因为随着用户查询的数量增长，查询最终被分类为精确的或子集或部分的，并且错误计算的查询的天际线用于后续计算，并且后续查询的响应时间得到改善。对于第二个实验，我们有一组q=25和d=5。随着数据集基数的增长，传统方法要进行的优势测试的数量明显增加。在相同的场景中，QPSkyline算法要么切断这些测试（对于精确查询），要么大大减少它们（对于子集和部分查询），并以优化的响应时间获得结果。(As应用散列的概念来获得用于存储用户查询的QP的适当位置，相关实验仅在场景（a）中相关，因此在实验（b）中跳过了SHQP用于频繁查询的453H我hihihihihi(a)性能与查询(b)针对数据集图3（a）查询数量，（b）数据集基数的影响我们也可以对更大的维度、更大的基数和大量的用户查询进行相同的实验。然而，很明显，可重用性因素将增长，并且QPSkyline算法也利用了这一点，因此，在这些情况下，它也必然会给出更好的结果。4. 在更新密集型环境中使用Query Profiler在本节中，我们扩展了QP的概念，使其在更新密集型环境中工作。在实践中，数据库经历更新操作，如添加新元组，删除元组和更新元组值。如果数据集被更新，则重复天际线查询的旧天际线让我们详细阐述这一点。回想一下第1节中讨论的酒店数据集，其天际线计算为{h1，h3}。我们已经介绍了更新操作的三种主要情况。情况1：添加一个元组：假设添加一个新的元组为h0，1000，2。在这种情况下，旧的天际线将变为无效，新的天际线将为{h 0}。然而，元组h0，8000，9的添加不会影响天际线。情况2：删除元组：假设第一个元组h1，2000，五是删除。在这种情况下，由于元组是旧天际线的一部分，因此新天际线将是{h3}。然而，删除元组h5，4000，7不会影响天际线。重要的是要注意，删除对天际线有贡献的元组可以使数据集中的其他现有元组对更新的天际线有情况3：元组值的更新：假设第一个元组hh1，2000，5i被更新，变成hh1，1000，2i。在这种情况下，Min[n]（Min-n）：一个n维列表，存储数据集的n维中每个维的所有值的最小值。当扫描整个数据集以计算第一个新查询的天际线时，该字段获得其值，并且每当数据集经历上面列出的任何更新操作时，该字段被引用以计算新的天际线。在每次更新中，如果更新后为任何维生成了更新的最小值，则该字段将更新。这对是否重新计算天际线有一定的指导意义。在节省了计算工作的情况下，skyline立即返回给用户，并且记录更新下的元组，以便稍后携带“惰性更新”。这就是响应时间的优化下一次讨论将详细讨论这一点4.1. 处理更新为了帮助理解更新时的天际线计算，我们提出以下引理。回想一下我们的假设，即所有的天际线查询都是针对单个关系R提出的，并且不失一般性地，我们假设天际线标准是找到相关维度的最小值在接下来的讨论中，每当我们提到维度的值时现在，我们提出的指导方针处理的更新和相关的天际线计算的帮助下，以下引理。引理1. 当元组t hv，v，.. . 要添加到数据集的vi新的天际线将是{h 0}。然而，如果元组hh6，3500，3i12 N更新为类似h6，8000，3，此更新不会影响天际线。这里需要注意的是，对天际线做出贡献的元组的更新可以使数据集中的其他现有元组对更新的天际线做出贡献从上面的例子可以清楚地看出，每当对数据集的更新操作影响查询Q的现有天际线时，重新计算天际线就变得必要。在讨论的所有情况下，保存在相关Query Profiler中的skyline结果似乎都没有用。然而，如果我们修改QP的结构，那么我们仍然可以减少在某些更新情况下的重新计算工作。我们现在添加以下内容-把场地让给QP。保持6in：v i> min i，则元组的添加不影响针对n维数据集提出的查询Q的天际线S。证据这意味着，如果元组的所有值碰巧大于其相关的最小值，则添加元组不会影响天际线在证明中，我们提出两点：(1) 假设一个元组t v1，v2，. vn被添加到n维数据集。如果这些值属于v1>min 1，v2>min 2，. vn> min n，则它们不会●454R.D. Kulkarni，B.F. 某敏hi算法2输入Q：skyline配置集，QP：查询分析器，F：更新操作集输出：S：Q的天际线。1. 开始QPUpdateSkyIine2. ←oper read_operation_to_be_performed（F）3. t←read_tuple_to_be_operated（F）4. if（oper=5.6.7.8.9.10.11.12.oper_status = check_ins_tuple（t，QP）if（oper_status =will_a_object_sky）insert其他C←compute_sky（Q）记录（t）end ifS←return_old_sky（Q）13. end if14. if（oper=15.16.17.18.19.20.21.22.oper_status = check_del_tuple（t，，QP）if（oper_status =will_a_object_sky）delete（t）其他C←compute_sky（Q）记录（t）end ifS←return_old_sky（）23. end if24. if（oper=25.26.27.28.29.30.31.32.oper_status = check_new_tuple（t，QP）if（oper_status =will_a_object_sky）update（t）C←compute_sky（Q）其他记录（t）end ifS←return_old_sky（Q）33. end if34. lazy_update_recoded_operation（t）35. 结束QPUpdateSkyIinehihihihihi作为最小值vmin1，vmin2，. 所有对Q有贡献的维中的vminn已经在S中了。(2) 即使当t v1，v2，. vn等于或小于维度的相关最小值，则需要检查元组是否适合于对较新的天际线做出贡献。在后一种情况下（v imin i.因此它不可能是天际线的一部分。所以它的删除不会影响天际线。 在第二种情况下，$i∈n：vi=min i。在这种情况下，被删除的元组必须是天际线的一部分，并且如上所述，其删除可以使数据集中的其他现有元组对天际线有贡献，并且在这种删除中必须调用对天际线的重新计算。在上面讨论的第一种情况下，完全节省了重新计算天际线的工作 我们上面没有讨论元组thv1，v2，.. .vni保持6in：vimini，因为这是不可能的。 min i，则针对n维数据集提出的查询Q的天际线S不受影响。证据 当任何元组t更新其值时，可能有三种情况。 在第 一 种 情 况 下 ， 元 组 thv1 ， v2 ， ... vni 保 持 6in ：vi>mini。因此，它不能成为天际线的一部分，其更新不会影响天际线。 在第二种情况下（极端情况），6i n：v i

下载后可阅读完整内容，剩余1页未读，立即下载