具有常数延迟的查询求值" - 沃伊切赫·卡扎纳的博士论文

具有常数延迟的沃伊切赫·卡扎纳引用此版本：沃伊切赫·卡扎纳查询评估具有恒定延迟。其他[cs.OH]。卡尚高等师范学校-卡尚高等师范学校，2013年。英语NNT：2013DENS 0030。电话：00919786HAL Id：tel-00919786https://theses.hal.science/tel-009197862014年12月9日提交HAL是一个多学科的开放获取档案馆，用于存放和传播科学研究文件，无论它们是否已这些文件可能来自法国或国外的教学和研究机构，或来自公共或私人研究中心。L’archive ouverte pluridisciplinaireENSC-（nTHE`SEDEDOCT ORATDEL沃伊切赫·卡扎纳先生发来的为了获得等级DocturDEL域名：InformatiqueSujetdelathe`se：具有常数延迟的查询求值The`se pre` sente` e et soutenuea`Cachan le 16e` eme Septembre 2013 d evant le jury compose` de：妮可·比多瓦Professeur新闻中心阿尔诺·杜兰德Professeur特别报告员帕特里斯·奥索纳·德门德斯研究费用特别报告员维克托·维亚努Professeur考官吕克·塞古芬Directeur de RechercheDirecteur de the` seCachan的认证和验证ENS，UMR 8643du CNRS61，avenueduPre sidentWilson94235 CACHAN Cedex，法国23致谢我很感谢Luc Segoufin，他好心地接受了我作为他的博士生。他向我介绍了查询枚举的问题，并鼓励我寻找我们合作过程中出现他是一个真正伟大的顾问，总是支持和讨论和建议。我想感谢Arnaud Durand和Patrice Ossona de Mendez接受审查这篇论文，并对这份手稿的早期版本提出建设性的意见。非常感谢Nicole Bidoit和Victor Vianu接受我的陪审团。特别感谢我的父母，他们指导我走科学的道路，并在任何时候都全力支持我。感谢LSV的所有成员我想感谢我在4楼同一个办公室工作的那些了不起的人如果没有那些有趣的谜语和精彩的法语课，我的时间非常感谢我的儿子鲍里斯，他很善良，整晚都在睡觉，让他的父亲把论文写下来。最后但并非最不重要的是，最大的感谢我亲爱的妻子金佳。如果没有她的不断支持，整个巴黎的冒险45内容页面致谢3内容51引言92个房间132.1数据库、关系结构和查询. . . . . . . . . . . . . . . . . . . . . . . . 142.2计算模型142.3参数化复杂性162.4逻辑学172.5核心查询问题172.5.1模型检验问题172.5.2查询评估问题172.5.3查询枚举问题182.5.4测试问题182.5.5查询的计数问题182.5.6查询的第j个182.6示例192.7复杂性等级212.7.1线性-时间类222.7.2评价等级LINEAR- EVAL222.7.3枚举类CONSTANT- DELAYlin222.7.4回答类CONSTANT- TIMElin和LOGARCHARMIC- TIMElin232.8图表232.8.1结构图242.8.2图的类别243基本成果293.1查询问题293.1.1第30章枚举问题3.1.2第j个问题的解313.2有限扩张323.3Gaifman vs邻接3263.3.1Bounded Degree323.3.2有界树宽333.3.3有限扩张344技术水平374.1数据库设置中的查询枚举384.1.1任意关系结构384.1.2X-底杆结构414.1.3稀疏结构414.1.4数据树474.2其他查点问题4.2.1抽象枚举问题494.2.2多项式总时间494.2.3递增多项式时间504.2.4多项式延迟504.2.5强多项式延迟514.2.6概率枚举算法514.2.7枚举类的顺序和分隔的影响524.3结论. 525有界度为53的结构类上的FO5.1导言. 535.2第54章5.2.1Gaifman第54号地点5.2.2模型检查555.2.3连接、分区和拆分555.3索引结构575.3.1基本索引结构575.3.2数到595.3.3增加半径605.3.4基本索引结构，计数为625.4解决问题635.4.1FO查询的枚举635.4.2测试FO查询645.4.3计算FO查询645.4.4FO查询的第j个解决方案问题656MSO over classes of structures with bounded treewidth有界树宽的结构类6.1一、导言. 686.2martaries696.2.1树木696.2.2有用的结果6.3简化问题706.3.170、树木的价值观6.3.2考虑二叉树就足够了706.3.3考虑也输出所有最小共同祖先71的查询就足够了76.3.4考虑具有祖先类型输出的了716.3.5考虑o兼容查询了6.3.6只要考虑到o兼容的查询可在foots2（）72中定义就足够了。6.4索引结构736.4.1骨骼分解736.4.2从x2（）到多项式746.4.3τ阶756.4.4基本索引结构766.4.5完整的索引结构786.4.6完整的索引结构，计数为796.5解决问题816.5.1Enumerating simpleEQUIP2（）queries枚举简单EQUIP2（）查询816.5.2测试简单的mysql2（）查询826.5.3计算简单的code2（）查询的826.5.4对于简单的m2（）查询的第j个解决方案问题846.6讨论856.7结论. 887FO over classes of structures with bounded expansion有界扩张的7.1一、导言. 897.2martaries917.2.1Graphs with bounded expansion and augmentation有界扩张和增广的图927.2.2作为函数结构927.2.3从结构到图表947.2.4无量词一阶查询957.3模型检查977.4测试1017.5枚举1027.6数到1067.7讨论1107.8结论. 1118讨论1138.1下限1148.1.1线性-EVAL/= CONSTANT- DELAY线性1148.1.2WEAK- CONSTANT- DELAYlinclass1158.1.3关于WEAK-CONSTANT- DELAYlin和CONSTANT- DELAYlin115的分离8.2有界度，有界扩张和超过1208.2.1有界度上的强逻辑。 . . . . . . . . . . . . . . . . . . . . . . . 1208.2.2有限扩张。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1228.2.3有界展开的其他性质 . . . . . . . . . . . . . . . . . . . . . . 124书目127891介绍“Knowledge is– Francis知识就是力量.在16世纪末17世纪初的某个时候，当弗朗西斯·培根说出这些令人难忘的话时，它们肯定有着与现在不同的味道公会仍然处于最佳状态，没有受到任何全球批评的威胁，并成功地保护外部世界免受他们的秘密知识的影响。书籍，甚至是最基本的教育都非常有限，只有社会的一小部分人才能获得。毫无疑问，培根毋庸置疑，知识就是力量。我们远不能说它不是。但是随着知识在过去的岁月中不断传播，以及由于互联网的普及而真正在全球范围内爆炸“培根到底是什么时候离开的？ 拿破仑见过狮身人面像吗？乌姆里奇街在瓦尔斯的哪一部分？你可能会想好吧，只要打开你的网络浏览器，在搜索引擎中输入问题，然后就可以了！ 一切都在那里。 只是在等好奇的人问。但你要坚持住！我们到底在问谁？上面的故事，尽管相当天真，但指出了两个重要的事实。首先，上述三个问题的随机性以及它们确实有容易获得的答案的事实1应该向我们表明，如今每个人都可以获得的知识量确实令人震惊。第二个重音几乎太突然地放在了ASK这个词上。当然，另一边没有人类。这些是计算机程序，做所有的肮脏的工作。查询数据库从现在开始，让我们转向计算机世界，特别是数据库部分。每个数据库的一个组成部分是数据的存储方式它应该是高效的，以免使用太多的内存。当然，数据应该受到很好的保护，这样未经授权的第三方就无法访问它。但是，存储数据背后的主要思想始终是相同的：在某些时候，我们希望能够访问它。原因可以是任意的：我们可能想检查我们的银行账户余额，或者我们可能只是渴望一些关于我们最喜欢的电影明星的新八卦。我们想要的是我们知道的信息。我们认为，可以说查询评估是数据库中最重要的问题给定一个查询q和一个数据库D，它要计算D上q的输出中所有元组的集合q（D）。1.它可以工作10然而，集合q（D）可以大于数据库本身，因为它可以具有形式nl的大小，其中n是数据库的大小，l是查询的元数。因此，它可能需要太多的可用资源来完全计算它。例1.0.1想象一个拥有1亿用户的社交网络。假设我们想要输出“握手距离”小于10的所有人对。虽然没有正式证明，但有很多理由可以预测输出将包含所有可能的用户对！1亿平方已经是一个可怕的数字，而查询只是二进制的。所谓的自由变量越多，查询的输出就越快失控。有许多解决方案来克服这个问题。例如，可以想象可以快速计算q（D）的一个小子集，并且该子集将足以满足用户的需求。通常，可以想象计算相对于某个排序函数的最相关的答案，或者提供相对于某个分布的q（D）我们也可以想象只计算解的个数|q（D）|或者提供对于给定元组是否属于q（D）的有效测试。查询枚举我们主要关注以下场景：给定一个查询q和一个数据库D，我们希望以常数延迟枚举q（D）直观地说，这意味着我们正在寻找一个两阶段的算法，其工作方式如下：它从预处理阶段开始，该阶段在数据库大小的时间上是线性的，然后是枚举阶段，在任何两个连续输出之间具有恒定延迟的情况下，逐个输出q（D）特别地，第一答案在与数据库的大小成线性关系的时间之后输出，并且一旦枚举开始，新答案就以与数据库的大小无关的速度定期输出1、求f（q）的值，求f（q）的值（||D||+的|q（D）|）对于某个只依赖于q而不依赖于D的函数f.为什么我们要以某种方式将查询的大小与数据库的大小分开，并且我们坚持数据库部分的线性，而我们根本不限制查询的大小，这在示例1.0.1中得到了说明：虽然1亿人的数据库是巨大的，但我们只花了大约一行文本来描述查询。一般认为，查询往往很小，而数据库的大小越来越大。例1.0.2考虑例1.0.1中的场景。所述查询具有用于所述数据库的自然查询算法：预处理阶段简单地将所有人放在一个链表上，并存储两个指针，都指向它的第一个元素。枚举阶段只是沿着列表移动第二个指针，在每一步输出第一个和第二个指针当前指向的指针对一旦遍历了所有元素，它就沿着列表移动第一个指针（仅一次），将第二个指针重置为第一个指针的当前值，并重新开始枚举过程。它继续这个循环，直到第一个指针到达列表上的最后一个元素。还有另一种方式来看待常数延迟枚举，我们发现这确实很有吸引力。预处理阶段在线性时间内计算一个索引结构，该索引结构以紧凑的方式表示集合q（D）（其大小与数据库的大小成线性然后，枚举算法是流式解压缩算法。作为补充，还可以要求枚举阶段以某种给定的顺序输出答案在某种程度上，我们也解决在这篇论文中的输出顺序的问题，它对枚举算法的复杂性（或存在性）的影响11围绕枚举有许多问题与枚举有关其中最主要的是模型检测问题。这是当查询是布尔值时的情况，即仅输出0或1。在这种情况下，常数延迟枚举算法是用于q的模型检查问题的固定参数线性（FPL）算法，即， 它在时间f（q）上工作||D||. 这是一个相当强的约束，因为即使是合取查询的模型检查问题也不是FPL（模参数化复杂性中的一些假设）[57]。因此，为了获得常数延迟枚举算法，我们需要对查询和/或数据库进行限制与枚举相关的另一个问题是已经描述过的计数问题，其中我们只对计算查询的解决方案的数量感兴趣。之前提到的测试问题是提供一个有效的测试，以确定给定的元组是否属于查询的输出。由于查询的输出可能是巨大的，即使其紧凑的表示和高效的解压缩可能也不够令人满意我们可能对直接计算输出集的第j个解（相对于某些选定的阶数）感兴趣然后我们讨论第j个解的问题.虽然我们的主要焦点仍然是枚举问题，但我们也总是试图解决上述四个问题论文结构本文的结构安排如下。• 在第二章中，我们介绍了所有必要的术语并展示了一些例子。• 在下面的第3章中，我们将给出一些简单的结果，这些结果将在后面使用。它也可能是第2章的一部分，但为了可读性，我们决定将其提取出来。• 在第4章中，我们试图揭示我们所知道的关于枚举的所有结果。本报告分为两节。首先，我们考虑如上所述的数据库场景。在另一方面，我们提到了在更广泛的意义上理解的各种枚举算法：而不是枚举查询的解决方案，我们可能感兴趣的是枚举给定图的所有生成树或满足任意属性的任何其他对象• 接下来的三章是本文的核心部分和主要贡献。我们反过来考虑：• 对具有有界度的结构类的一阶查询（参见第五章）。我们遵循[46]的行在枚举算法的介绍。然后，我们通过推广[46]的方法，给出了相应的计数、检验和第j个• 在具有有界树宽的结构类上的一元二阶查询（cf.第六章）。我们遵循[48]的行在枚举算法的介绍。通过推广文[48]的方法，我们给出了相应的计数、检验和第j解问题有效解的存在性的新证明• 对具有有界扩展的结构类的一阶查询（参见，第七章）。我们遵循[47]的思路来介绍模型检查、枚举、测试和计数算法。我们稍后将展示为什么[47]“免费”为我们提供了第j个解决方案问题12• 在第八章的讨论中，我们首先对前几章的内容进行了总结然后，我们讨论了一些有趣的开放的问题，自然出现的考虑的问题，我们试图概述我们的直觉，解决这些问题的可能方法。关于具体定义的细节，读者可参阅第二章。我们决定不在这里介绍第5、6和7章的证明大纲，因为必要的术语还没有定义，我们想让这一章的介绍保持轻松和非正式的水平。熟悉所有提到的概念的读者可以直接转到第4章来找到省略的草图。否则，我们觉得通过分析第2章和第3章来熟悉我们在这篇论文中使用的所有定义和符号可能是有益的。132预赛内容2.1数据库、关系结构和查询2.2计算模型142.3参数化复杂性162.4逻辑学172.5核心查询问题172.5.1模型检验问题172.5.2查询评估问题172.5.3查询枚举问题182.5.4测试问题182.5.5查询的计数问题182.5.6查询的第j个182.6示例192.7复杂性等级212.7.1线性-时间类222.7.2评价等级LINEAR-EVAL222.7.3枚举类CONSTANT-DELAYlin222.7.4回答类CONSTANT-TIMElin和LOGARCHARMIC- TIMElin232.8图表232.8.1结构图242.8.2图的类别2424度有界有界树宽25有限扩展25正如第一章所提到的，在这篇论文中，我们一直在研究关于数据库查询的问题。由于我们处理的是线性时间复杂度，因此必须使计算模型精确。在本章中，我们给出了所有必要的定义。我们介绍所有涉及的符号和定义的方式遵循Luc Segoufin [62]最近关于这个主题的调查142.1数据库、关系结构和查询我们将数据库定义为关系结构。定义2.1.1关系签名是一个元组σ=。（R1，. . . ，R1），其中R1是阿瑞提河岛σ上的关系结构是元组D=D，RD，. . .，RD，其中D是有限集（称为Dr1lD的定义域），并且每个Ri是Di的子集。定义域D中元素的个数记为与|D|.在上面的定义中，如果对于某个i，我们有ri= 1，那么我们也称关系Ri为颜色。此外，我们经常使用术语模式而不是术语关系签名。查询是将数据库D与D的域上的关系相关联的可计算函数。关联关系的arity仅取决于查询（即，给定查询q，存在整数rq，使得对于输入数据库D，查询q返回Drq的子集），并且称为查询的arity。如果这个arity是0，我们说q是一个句子，它在D上要么为真要么为假，它定义了D的一个性质。一个查询是一元的，如果它的arity是1，然后它定义了D上的颜色。 给定一个查询q、数据库D和一个元组a<$D ，我们写D|=q（a<$）表示a<$在D上的q的像中的事实，并且D|=<$q（a<$）表示相反的情况。在句子的特殊情况下，我们写D|=q，如果q在D上为真（或者，换句话说，D具有性质q）和D|=<$q否则。 设q（D）={a<$：D|=q（a<$）}，我们称这个集合为D上q的解的集合。如果D在上下文中是明确的，我们只需写出q的解集。我们说两个查询q和q′在D上是互斥的，如果它们在D上的解集是不相交的，即q（D）<$q′（D）=<$。同样，如果上面的交集碰巧是空的，并且D从上下文中是清楚的，我们就说q和q′是互斥的。注意，如果查询的arityrq大于1，则q（D）的大小可以是rq的指数。查询语言是一类查询。通常，它被定义为逻辑形式主义，例如FO（用于一阶查询）或MSO（用于一元二阶查询）。事实上，这两种形式主义在第5、6和7章中讨论过，它们也是本论文关注的中心给定一个查询语言L，L的模型检验问题是如下计算问题：给定一个句子q ∈ L和一个数据库D，判定D是否|= q或不。如果数据库D被限制为一类C结构（这将是大多数时间在整个论文的情况下），我们说的模型检查问题的L在C。给定查询语言L，L的查询求值问题是如下计算问题：给定查询q∈ L和数据库D的计算集q（D）.与模型检查问题的情况类似，如果数据库D被限制为一类C结构，我们称之为LoverC的查询评估问题。上面给出的模型检查和查询评估问题的定义对应于它们的组合复杂性，这意味着每个问题的输入都是查询q和数据库D。在接下来的大部分时间里，我们假设查询是问题的一个参数（唯一的输入是数据库）。然后我们谈到问题的数据复杂性2.2计算模型在第2.5节中，我们定义了一系列问题，这些问题是本论文的核心。因为他们的解决方案是我们都将提到线性时间，我们必须使我们的计算模型精确。我们使用随机存取机（RAM或RAM机）的加法和统一的成本措施作为计算模型。由于这不是本文的重点，我们不给出这个模型的详细定义（关于模型本身的更多信息见[2]，关于它在逻辑中的使用见[26]）。我们只列出与本论文最相关的关键特征：• 在一个大小为n的输入上，RAM机器有一定数量的寄存器，每个寄存器由其值和唯一地址，两者都包含logn位。 我们经常写RAM机器的内存15以表示其寄存器组，并且存储器单元以表示单个寄存器。给定一个寄存器r，我们也写一个存储在r中的值来引用r的值。• 机器可以像图灵机一样修改寄存器的内容。• 此外，它可以使用任何寄存器r来直接访问另一个寄存器r′，使得r′的地址由r的值给出。在这种情况下，我们说r是指向r′的指针。• 此外，RAM机可以执行数值运算（通常是加法或乘法）的寄存器的值。• 使用一个寄存器或两个寄存器的加法对存储器的访问在RAM中花费单位时间，即作为恒定时间计数。RAM在现实生活中的一个很好的近似是汇编程序中的低级命令式编程存储在汇编程序寄存器中的值这正是RAM所提供的，只有算术部分仅限于加法，执行单个加法的时间和访问存储单元的此外，虽然在汇编程序中，通常需要在操作其值之前首先将存储单元的内容加载到寄存器中，但在RAM模型中，我们在某种意义上继续“现实生活”中的命令式编程类比，当描述RAM算法时，我们通常会谈论元素的列表或数组。而且，也许甚至作为第一步，我们希望有恒定大小的记录（例如存储元素对的记录）。思考这些对象的一个好方法可以是：• 一个包含k个“信息单元”的记录例如，为了表示一对值n、m，可以使用两个寄存器r和r′，分别具有值n和m以及地址a和a+ 1。注意，如果只访问r或r′，我们就可以在恒定时间内轻松恢复另一个值（因为地址是连续的，寄存器知道它的地址）。还请注意，我们可以通过在记录中嵌套记录来使用附加值来丰富这些记录• 如果我们希望寄存器r既存储值v，又存储指向其他寄存器r′的指针，我们可以用r的值指向描述r的记录来实现它。然后，这个记录可以在连续寄存器的值中存储值v和r′的地址。• 一个列表可以被看作是一个寄存器序列，每个寄存器除了存储它的值之外，还存储一个指向列表中下一个元素的指针（这可以通过使用上面所示的描述寄存器的记录来实现）。• 最后，一个数组可以被看作是一个具有连续地址的寄存器序列在我们的设置中，输入将始终是一个数据库。我们没有给出一个精确的定义，关系结构是如何编码为RAM机器的输入。这与图灵机相同，在许多教科书中都有描述，参见。[1]的文件。对于这篇论文来说，唯一重要的是我们可以在线性时间内枚举数据库的域或关系为了演示的简单性（特别是为了清楚地描述2.6节中的例子），我们稍后假设定义域和每个关系都是以列表或包含匹配列表的连续元组的数组的形式给出的特别是，我们不允许使用未初始化的内存。数组表示的优点是只有可能在常数时间内直接访问它的第j个元素从现在开始，我们用二进制字对结构进行合理的编码D的大小，表示为||D||是D的编码长度。注意，对于一个固定的模式σ和σ上的数据库D，其定义域大小为n，D中所有关系中的元组总数等于m，D的编码长度为O（（n+m）log（n+m））位，可以存储在O（n+m）个寄存器中。一个直接的观察是，RAM模型可以对m个大小的元素进行时间复杂度为O（logm）在时间O中，我们可以对D的域进行排序（||D||），即以线性16在RAM机器的输入方面的时间一个重要的观察是，我们也可以在线性时间内对节点的元组进行排序[40]。当我们说LoverC的模型检验问题可以解决时，我们的意思是存在一个解决这个问题的RAM机器当然，这也可以扩展到其他问题，比如查询评估等。接下来，当我们说LoverC的模型检测问题可以在线性时间内解决时，我们只指数据复杂度，即。 这意味着它可以在O（||D||），当大O可能依赖于q时。2.3参数化复杂性在2.1节和2.2节的结尾，我们已经提到了问题的数据复杂性这是因为数据库D和查询q在我们的算法中扮演着不同的角色||假设是大的，而||Q|被认为是小的。|is assumed to be small. 因此，区分这两个输入以一种正式的方式。参数化复杂性是分析这种情况的合适框架。与RAM模型类似，由于参数化复杂性本身不是本文的主题，因此我们在这里仅提供其基础。有兴趣的读者可以参考这本书[33]，以获得关于参数化复杂性的广泛覆盖。在参数化复杂性中，一个问题由以下三元组组成• 输入，• 参数是可从输入计算的数字• 还有一个问题一个典型的例子是参数化模型检查问题，其中输入是数据库D和句子q，参数为|Q|问题是D|= q。一个参数化问题是固定参数可处理的，如果在输入大小为n和参数k的情况下，对于某个合适的可计算函数f和常数c，它可以在时间f（k）nc内求解。我们写的问题是在FPT，如果它是固定参数可处理的。这个定义背后的想法是，对于许多场景（特别是数据库设置中的查询评估问题），最好有一个算法在时间2kn而不是nk中工作。参数化的复杂性被证明是一个非常强大的概念。有一个合适的归约概念这是FPT类在FPT-归约下封闭的情况。有一些硬类的参数化问题，也是封闭的FPT约简，但他们包含的问题，没有已知的FPT算法，并认为是不同的类FPT。参数化复杂度中的完备性概念总是被理解为模FPT约简。参数化复杂度设置中的类FPT在经典复杂度中扮演P的角色。一个重要的硬类记为W[1]。它在参数化复杂性中扮演着经典复杂性中NP的角色对于W[1]来说是完备的一个典型问题是合取矩阵（CQ）的参数化模型检验问题（详见[57它以数据库D和句子q∈ CQ作为输入，作为参数|Q|问D是否|= q。另一个重要的硬类表示为AW[*]。它在参数化复杂性中扮演着经典复杂性中PSpace的角色。AW[*]的一个典型问题是一阶逻辑（FO）的参数化模型检验问题（详见[57]）。 它以数据库D和句子q∈ FO作为输入，作为参数|Q|问D是否|= q。17虽然我们知道类FPT<$ W[1]<$ AW[2]的明显包含，但不知道这些包含是否严格。正如经典复杂性中的P、NP和P空间一样，所有这些包含都被强烈地认为是严格的。2.4逻辑在2.1节中我们已经提到，典型的查询语言是逻辑形式主义。第5、6、7章的情况也是如此，在这三章中，我们将讨论一阶（FO）和一元二阶（MSO）逻辑。我们假设读者对这两种形式主义都很熟悉，所以在续集中我们只给出了它们的简要概述。一阶逻辑（FO）是由形式为x = y或Ri（x1，. . . ，xri） ，并且在通常的布尔连接词（<$，<$，<$）以及存在量词和全称量词（<$，<$）下是封闭的。一元二阶逻辑（Monadic Second Order Logic，MSO）是集合变量X和集合量化的FO的扩展由于我们将查询定义为将数据库与其域上的关系相关联的函数，因此当我们谈论MSO查询时，我们不允许自由集变量。为了表示集合变量，我们总是使用大写字母（X，Y）来区分它们与一阶变量（x，y），同样地，我们区分一阶量化（x）与二阶量化（X）。我们用希腊字母如φ、、等来表示公式。当写φ（x<$）时，我们通常意味着x<$是φ的一阶自由变量。 给定数据库D和D的元素的元组a，我们写D|=φ（a<$）如果公式φ在D中用a <$替换其自由变量后为真。 像往常|φ|表示公式φ的大小，它是自由变量的数量，量化的数量，布尔连接词的数量和出现在φ中的原子公式的数量之和。2.5核心查询问题在本节中，我们介绍了一系列的问题，这是本论文的中心利益其中一些已经提到，但我们在这里重复他们无论如何都有他们在一个地方聚集修正了一个查询语言L和一类数据库C。下面提到的每一个问题都是这样的：给定一个查询q∈ L（可能对q有一些额外的约束）和一个数据库D∈ C，计算问题的解（可能只依赖于q和D）。对于下面的部分，假设L和C分别是固定的查询语言和一类数据库。2.5.1模型检验问题C上L的模型检验问题是给定一个句子q∈L和一个数据库D∈ C，判定D是否|=q或不。2.5.2查询求值问题C上L的查询求值问题是给定查询q∈ L和数据库D∈ C，计算集合q（D）的计算问题。182.5.3查询枚举问题C上L的枚举是的计算问题，给定查询q∈ L和数据库D∈ C，逐个输出q（D）中的元素，不重复。在枚举场景中，我们将来自q（D）的元素的任何两个连续输出之间的最大时间表示为延迟。这篇论文的目标是证明对L，C，使得在C上的L的枚举允许这个延迟是常数。2.5.4查询测试问题L在C上的测试是这样的计算问题，给定具有k个自由变量的查询q∈ L和数据库D∈C，所有这些都是为了回答以下问题：从D中找到k个元素的元组a，决定D是否|=q（a<$）或不。我们称之为测试问题的动态输入，并回答D是否|=q（a<$）称为动态答案。2.5.5查询的计数问题C上L的计数问题是给定查询q∈ L和数据库的计算问题D∈ C，计算值|q（D）|.2.5.6查询的第j个解决方案问题C上L的第j个解问题是这样的计算问题，给定一个查询q∈L，有k个自由变量和一个数据库D∈ C，允许回答以下问题：给定j∈N，计算集合q（D）的第j个元素（关于D的k个节点的元组的某个阶≤），或者说这样的元素不存在。与测试问题的情况类似，我们将j称为测试问题的动态输入，将返回的第j个元素（或表示该元素不存在的响应）称为动态答案。在我们讨论这些例子之前，我们想指出两件事。注意，测试和第j个解决方案问题具有类似的重要的共同点是，两个动态输入的大小都与输入数据库的大小无关（a的大小仅取决于q的arity，并且可以假设由j表示的值适合单个寄存器），并且对于相应的动态输出也是如此为此，我们写一个动态查询问题，每当我们想谈论这两个问题之一，但我们不想指定哪一个。当然，这可以推广到一个更广泛和抽象的概念，但由于我们考虑的唯一动态问题是测试和第j个解决方案，我们坚持这个非常有限的定义动态查询问题。此外，我们介绍这些问题的顺序不是随机的。• 模型检测和查询评估是最经典的查询问题。模型检查，输入查询结果是一个句子，是起点（并且是一个在计算机科学的其他领域中发挥巨大作用的成熟在接下来的章节中，除了第7章，我们将直接讨论模型检验问题，我们通常将它们作为已知的黑盒来19• 然后，我们引入枚举问题作为一个细化的评价问题。正如第一章所提到的，这实际上是本论文从一开始就集中讨论的问题，也是作者感兴趣的中心。• 接下来是测试问题，在本文中考虑的所有情况下，都可以使用为枚举算法开发的工具来• 然后，我们转移到计数问题，这是有用的两个原因：假设我们有一个约束的延迟，它允许预测所需的时间枚举的所有解决方案的查询，通常是一个很好的开始的路径上理解和解决第j个解决方案的问题。• 最后，我们有第j个解的问题.虽然它与枚举问题有很强的联系（在某种意义上，我们可能会要求从“中间”得到一个特定的解决方案，结果证明是非常不直观的，并且第j个解决方案问题的解决方案可以用于生成随机解决方案（但没有重复）而不是特定的解决方案;或者在复杂性方面有损失，其中将第j个解决方案连续应用于1，2，.. .、|q（D）|枚举q（D），连续解之间的延迟严格比直接通过枚举过程获得的延迟更差。2.6示例我们在这一节专门分析几个简单的例子，我们认为这些例子具有足够的代表性，足以指出人们在处理2.5节所描述的问题时所面临的主要困难。设σ是一个包含关系符号P的关系模式，D是σ上的一个数据库。虽然在形式上我们应该写PD来表示D中的实际关系P，但为了表示的简单，我们跳过上标D而简单地写P。在介绍例子之前，我们要注意解决枚举、测试和第j个解决方案问题的算法将有两个不同的阶段：• 在枚举第一解或读取第一动态输入之前执行的所谓的预处理• 然后是枚举/动态阶段。其原因是，如果不使用一些额外的导航功能来增强输入数据库（预处理阶段正是为此目的），即使是最简单的情况也很难解决。我们通常针对预处理阶段，||D||以及常数/对数延迟/动态输出。例2.6.1考虑一个数据库模式，它包含一个一元关系符号P和查询q（x）：=P（x）。设D为每个算法的输入。q的枚举是平凡的：算法遍历属于P的节点列表，在每一步输出当前节点。计数问题也是直接的：算法遍历上面的列表并计算其长度。第j个解问题的算法首先执行计数过程。然后，每当给定j时，它首先测试是否实际上至少有j个解，并且只有在这种情况下，它才执行其他步骤。我们在下面的例子中没有提到这一部分，但读者应该记住，虽然这一步很琐碎，但总是必要的。第j个解问题的其余部分的如果描述P的元素已经在一个数组中，每当我们给出j时，就足以输出这个数组的第j个元素，仅此而已。如果P的描述是一个列表，我们首先在线性时间内将其转换为数组，然后像前面的情况一样进行令人惊讶的是，测试问题似乎有最苛刻的解决方案（尽管仍然很简单）。给定域的元素a，