当前不确定数据广泛存在于诸如传感器网络、RFID网络、基于位置服务、移动对象管理网上购物和市场监控等各种实际应用中.不确定Skyline查询作为不确定数据管理的一个重要方面,由于其在决策制定、市场分析、环境监控和数据挖掘等方面的重要作用,近年来在数据库和网络计算领域受到广泛关注.首先,概述了各种不确定数据类型上的Skyline查询定义,包括离散、连续概率分布模型以及不完全数据上的Skyline查询定义;其次,分析了不确定Skyline查询的特点,并在此基础上综述了现有的各种不确定数据集上的集中式和分布式Skyline查询方法,重点分析了各种算法的原理和优缺点;再次,介绍了不确定数据流上的Skyline查询定义并综述了各种不确定数据流上的Skyline查询方法;最后,基于最新研究动态指出了未来不确定Skyline查询研究的趋势.

实时复杂事件处理系统(CEP系统)用于从原子事件流中检测出复杂事件，需要确保事件处理任务在截止期内完成.确保实时性的关键问题是如何估算系统中复杂事件处理程序(CEP程序)的最坏响应时间.现有针对一般程序的估算方法需要标注对象程序中子程序执行次数的取值范围.然而，CEP程序较为复杂，难以直接获知子程序执行次数的取值范围.虽然执行次数间存在关联关系，可以间接求解出取值范围，但这样得到取值范围不够严格，使估算精度较低，因此现有估算方法难以直接使用.提出一种CEP程序的最坏响应时间估算方法.采用新标注方式，通过对CEP程序的检测结构进行分析，归纳出子程序执行次数间的关联约束，并使用关联约束进行标注，替代了标注其取值范围，避免了标注困难.实验表明方法具有较高估算精度.

集合相似连接(set similarity join)是指在给定的数据集中,按照基于集合间覆盖关系的相似度计算方法来衡量数据之间的相似度、并找出所有相似度不小于给定阈值的数据对的操作.集合相似连接作为一种新的基本操作在很多领域中有重要应用.随着社会网络、移动应用以及在线服务的发展,使得数据收集的效率和规模得到了很大的提高,同时给相似连接操作带来新的挑战.根据集合相似的必要条件,提出了相似集合之间的差异度.利用差异度和鸽巢原理,提出了一种新颖的基于数据划分的集合相似连接计算方法,该方法对集合进行自适应的均衡划分,并利用基于划分块的过滤方法来提高过滤的效率.为了进一步提高过滤的效果和相似连接的效率,利用划分块的位置信息提出了增强的过滤方法.针对提出的方法,在不同的环境下进行了实验,实验结果表明,该方法与已有的方法相比可以有效地提高相似连接的效率.

数据库外包是将数据库管理工作外包给专业第三方，而数据库外包中需要解决的关键问题之一是查询结果的验证.提出了外包追加型数据库的问题.根据外包追加型数据库的特点，在现有验证数据结构的基础上，提出了一种新型验证数据结构Min-Max Hash Tree，可以有效地解决客户对查询结果进行验证的问题.对于数据所有者端，给出了基本的数据发送算法；对于服务提供商端，分别给出了一次性查询和连续查询的查询算法和查询结果验证算法.最后，对数据所有者端的验证数据结构的存储、数据发送和服务提供商端的连续查询进行了优化处理，大大节省了数据所有者端的存储空间，提高了数据的整体处理效率.实验表明，Min-Max Hash Tree能够有效完成追加型数据库外包的查询结果验证，并且能够高效率处理大规模数据.

物化是列存储数据仓库查询中必不可少的操作，物化策略和物化技术直接影响到查询执行的性能，因此设计一种适应于列存储系统的物化策略和相关技术尤为重要.针对延迟物化可能重复读取数据块的缺陷，提出了基于带值路径的物化技术，简称VPM.首先，定义了一个描述物理执行中间结果的结构——传递块，该结构将用于重构的位置信息与实际列值相分离.在此基础上，对于给定的物理查询树，根据其操作节点是否需要某一列的值进行路径标记，生成自扫描节点或抽值节点到最终需要这些节点的引用列的祖先节点之间的路径，即带值路径.将起始节点引用列的列值保存在传递块的列值区中，并在向查询树的上层操作节点传输过程中不断对其过滤.对带值路径中的其他列仅保存其位置信息.在查询执行时，除了路径起始节点要从磁盘读取数据外，其他节点直接从传递块中获得相应的列值，有效地减少了查询处理过程的I/O开销，提高了查询的执行性能.最后在DWMS上使用TPC-H中针对数据仓库的基准数据集SSBM进行实验，验证了基于带值路径物化技术的有效性.

应用需求的发展衍生各种查询类型,Top-k查询是交互环境下一种重要查询类型.由于数据的不确定性,传统数据上的Top-k查询技术和方法不能直接应用于不确定数据查询.在已有不确定数据上Top-k查询算法的基础上,提出基于二叉树的不确定数据上Top-k查询算法BTreeU-Topk;为了提高算法执行效率,对二叉树进行修剪操作进而提出BTreeOPTU-Topk和BTreePU-Topk算法.实验结果表明,BTreeU-Topk，BTreeOPTU-Topk以及BTreePU-Topk算法在不同数据分布以及k值增长时均优于现有算法.

为用户缓存实视图可以有效提高其OLAP查询的性能.但是,已有的缓存管理策略由于没有考虑用户在进行OLAP分析时的数据访问特性,在处理实视图动态选择问题时无法获得好的性能.提出了视图路径和视图树的概念,并以视图树作为客户端缓存中的实视图组织方式.提出了“逆路径增长法”来快速计算新到达查询的视图路径,提高了查询的响应速度.对于视图树的动态调整问题,以“保留路径”为参照,设计了合理有效的视图替换策略.实验证明,该方法能够比已有的动态选择方法取得更好的性能.

针对索引维护时间和空间效率低的问题,提出了一种基于分配空间自学习的在线动态索引混合更新机制(on-line dynamic index hybrid update, ODIHU).ODIHU根据Zipf分布原理对长短列表数量分布进行估计,并采用基于历史分配空间的自适应学习机制对长短列表空间进行有效管理,然后对短列表采用立即合并更新方式,长列表采用上限Y相邻多路合并的更新方式维护,实现索引更新与查询性能的有效折中.理论分析及实验结果表明,ODIHU能有效地提高索引维护与更新过程中的空间效率、索引合并与查询时间效率.

由于资源描述框架(resource description framework, RDF)具有表达灵活、简洁等优点,已被接受为表达元数据及万维网上数据互联的规范.近年来,其数据量在以飞快的速度增长.相应地,要求存储RDF数据的系统应具有高扩展性.介绍了一个高可扩展的RDF数据存储系统TripleBit.为尽可能降低存储空间消耗,采用了增量压缩和变长整数编码方法.并采用了数据分块的存储方法,既使得存储管理方便又使得存储结构紧凑,加速了数据读取.系统提供了基于启发式规则的动态查询计划生成方法,所产生的查询计划在执行过程中根据中间结果会相应作调整,以保持最优的执行顺序.对于多变量的查询,使用二步执行策略以减少查询过程中产生的中间结果.与目前流行RDF数据存储系统相比较,在存储空间上RDF-3X比TripleBit至少多40%；在查询性能上,比RDF-3X和MonetDB获得数倍的提升.

空间近似关键字查询包含一个空间条件和一组关键字相似性条件,这种查询在空间数据库中返回同时满足以下条件的对象：1)对象的位置信息满足查询中的空间条件；2)对于查询中的任何一个关键字，对象中至少包含一个关键字与其相似度大于给定阈值.随着当前数据的爆炸性增长，空间数据库无法完整地存放在内存中，因此空间数据库需要支持空间近似关键字查询的外存索引.目前，还没有在外存中支持精确的空间近似关键字查询的索引结构.设计了一种新型的外存索引RB树，在外存中支持精确的空间近似关键字查询.RB树支持的空间近似关键字查询包括多种空间条件，如范围查询、NN查询，同时支持多种关键字相似性度量，包括编辑距离、规范化编辑距离等.通过真实数据中的性能测试验证了RB树的效率.

现有轨迹相似性度量缺乏对时空语义和时间随机性的考虑,不能有效地区分移动对象的社会角色.为解决这一问题,做了如下工作:1)提出了时空关联语义(spatial-temporal associated semantics, STAS)的概念,解释了轨迹的语义相似性规律,即两条轨迹的语义相似性与其在某时段内经过同类型区域的概率正相关;2)提出了时态熵(temporal entropy)的概念,度量了轨迹经过同一类型区域的时间随机性;3)基于STAS和时态熵,给出轨迹语义相似性度量(trajectory semantic similarity, TSS),刻画了轨迹所属移动对象的社会角色的时空特征;4)提出了移动对象社会角色发现算法(social roles discovering algorithm, SRDA),该算法基于TSS实现轨迹聚类,其中一个聚簇代表一种社会角色.真实数据和仿真数据上的实验表明,SRDA在准确率上比现有方法平均提高了18%,同时具有线性时间复杂度,从而验证了算法的有效性和性能.

指出不确定性和模糊性在时空语义上的区别；提出不确定移动对象的模糊时空范围查询问题，即查询条件中时间、空间范围的外延是模糊的，无清晰的边界，而目标对象的位置不确定；用模糊集表示模糊查询条件，概率密度函数表示移动对象在各自不确定区域内的可能位置分布；给出了不确定对象关于模糊查询条件匹配度的计算方法；设计了基于α截集的无效对象排除和有效对象确认规则及查询算法.算法规则适用于任意概率密度分布.现有的确定或不确定范围查询可以看成是模糊时空范围查询的特例.通过实验验证了算法的效率，在各种参数设置下，约有30%~90%的查询结果可在不计算匹配度的情况下获得.

空间查询处理已经广泛地应用于基于位置的服务、设施选址等领域.提出一种新的空间查询:主题相关区域查询(topic-relevant region queries, T2R),该查询可以用于位置选址等空间决策分析.给定一个由空间特征对象集合R定义的主题T、查询窗口q,T2R查询返回不交叠的k个与主题最相关的区域,区域与主题的相关程度由区域内特征对象的数量结合其重要性进行计算.为了有效处理T2R查询,提出BSL，FR和SHR 3种算法,其中SHR算法将高相关程度区域先聚类、再收缩以获得更优的剪枝效果.所提出的算法解决了给定查询窗口下对数据空间任意位置按主题相关程度进行排序的问题.利用真实与人工数据集进行了充分实验,评估了所提出算法在不同参数设置下的查询效率,通过针对实际主题的查询验证了T2R查询的有效性.

对于社交网络影响力最大化问题,Kemple和Kleinberg提出了有较好影响范围的贪心算法,但是KK算法的复杂度非常高,并不实用.利用线性阈值模型提出了一种基于节点激活阈值的启发式算法.它综合考虑了节点之间的影响力和节点的激活阈值,根据每个节点在激活过程中动态变化的阈值来计算PIN值,启发过程中,每一次都选取PIN最大的节点作为种子节点进行激活,贪心阶段中再贪心地挑选那些具有最大影响范围增量的节点作为种子节点.通过实验表明,即使在完全不采用贪心阶段,该算法的激活范围与KK算法都非常接近,而算法的复杂度则相对非常小.实验还表明该算法相对于HPG算法在相同启发因子c的情况下具有更大的激活范围.

频繁项查询在网络监控、网络入侵检测、关联规则挖掘等方面是一项非常重要的技术.该技术在静态的不确定数据中已经得到了深入的研究.但随着数据流特征和不确定性表现的日益明显，在不确定数据流环境下的查询已经成为一项新的研究课题.因此基于数据流普遍采用的滑动窗口模型，提出了一种高效的概率Top-K频繁项查询算法sTopK-UFI.该算法避免了每次窗口更新都重新计算查询答案，而是利用现有的计算结果进行增量更新，从而减少查询代价.另外，该算法基于窗口中的现有数据对未来可能成为频繁项的元素进行预测，并利用泊松分布计算元素成为频繁项的概率上下界，提出相应的过滤策略，可以显著减少检测数据的数量，提高查询效率.实验结果表明，所提出算法可以有效地减少候选集、降低搜索空间、改善在不确定数据流上的查询性能.

提出一种基于建模同步动力学行为的Kuramoto模型的网络社团发现算法SYN.该方法首先将网络中节点对象按照链接密度关系进行排序，每一个节点对象用一个一维坐标值表示，从而将网络数据矢量化.在聚类过程中，采用同步聚类原理对一个局部邻域内的对象实现同步，最终同步到一起的节点形成一个社团.通过不断扩大节点同步的邻域半径，可以得到不同分辨率的多种社团划分结果.结合社团模块度函数，可以自动选择最佳聚类结果.方法不依赖于任何数据分布假设，可以检测出任意数量、大小和形状的社团.在大量人工合成数据集和真实数据集上的实验结果表明其聚类准确率较高.

研究了不确定图上的最短距离问题,提出了期望最短距离的概念,证明了该问题不存在多项式时间的算法.为了解决该问题,使用了随机采样技术获得不确定图的一些可能世界,在每个可能世界上计算有穷的最短距离,最后计算出平均值作为期望最短距离的估计值.为提高计算效率,使用了过滤条件来减少采样过程中采样的边数从而加快随机采样.在此基础上,提出了一种基于对称变量的、无偏的随机采样近似算法,并证明了与直接随机采样方法相比,该方法在不增加时间开销的同时能减小采样方差.通过真实数据上的实验表明,提出的算法在时间开销和采样方差上均明显好于直接随机采样方法.

近年来，图模型广泛应用于生物信息、计算化学、语义网等领域.目前，“过滤-验证”机制被广泛用于子图包含查询，即首先根据图数据的特征构造索引，然后根据索引产生候选集，最后对候选集中的每一个图进行子图同构验证.在这类算法中，“过滤”阶段是关注的重点，力争过滤掉更多的数据；而“验证”阶段则只是单纯地进行候选图子图同构检测，并没有进一步优化查询性能的可能.因此，提出了一种新的子图包含查询的迭代处理机制：“选择-验证-过滤”，可利用从子图同构验证过程中得到的信息，结合数据库中图数据之间的相关关系，进行迭代查询处理.该机制首先选择数据库中的图与查询图进行同构验证，然后根据本次验证得到的信息，结合图数据之间的子图映射关系，进行迭代查询处理.一旦子图同构验证成功则可直接获得查询结果，而若验证不成功，则可以缩小下次迭代的查询搜索空间.为提高验证成功概率，提出了一种基于搜索空间预测的图选择策略.大量实验表明，该算法具有较“过滤-验证”机制更高的查询处理性能.

对于部署在恶劣环境中且无法放置Sink节点的无线传感器网络,节点的能量有限且易于损坏.每个节点为了避免自己死亡后数据丢失,需要将数据分发到网络中其他一部分节点上进行保存.但是,由于节点只知道自己邻居的信息,同时存储容量有限,因此如何有效地进行数据分发和存储是一个具有挑战性的问题.提出一个基于自适应概率广播的数据保存协议APBDP来解决这个问题.在APBDP中,节点通过一种自适应的概率广播机制分发数据，这种机制不仅可以使所有节点接收到数据包,而且能有效地减少数据的冗余传输以节省节点能量.此外,节点利用LT码来对数据进行编码存储,所有节点完成数据的分发和存储后,数据采集者只需要访问少量的节点就能恢复出所有的源数据.理论分析和实验表明,APBDP不仅具有较高的解码性能,而且能量有效.

伴随语义网的发展,语义网本体数量激增.然而万维网上绝大多数的数据仍存储在关系数据库中.建立关系数据库模式与语义网本体间的映射是一种实现两者之间互操作性的有效途径.因此,提出了一种基于语义的关系数据库模式与OWL本体间的映射方法SMap,包含简单映射发现和复杂映射学习两个阶段.在简单映射发现阶段,首先通过逆向工程规则将关系数据库模式和本体中的元素对应地分为不同类别,再为每个元素构建虚拟文档并计算它们之间的相似度,其中针对不同类别的元素设计了不同的虚拟文档抽取方案.在复杂映射学习阶段,基于已发现的简单映射以及重叠的数据库记录和本体实例,自动化地生成训练事实数据,然后运用归纳逻辑编程算法学习出多种类型的基于Horn规则的复杂映射.真实数据集上的实验结果表明,SMap在简单映射发现和复杂映射学习上均明显优于现有的关系数据库模式与本体间映射方法.

关系数据库中的关键词搜索技术已经成为信息检索领域的研究热点，它为没有任何SQL语法知识的用户提供了一个简单友好的接口.但是现存的关键词搜索系统主要依赖于数据图或模式图，而单独使用数据图或模式图的算法搜索效率不高，结果准确率也较低.设计实现了一个Top-k关键词搜索系统(keyword search system based on database graph and schema graph,KWSDS)，用户提交关键词后，系统对关键词进行预处理，消除一些脏关键词.首次提出使用数据图与模式图相结合的方法，设计了同表查询算法和异表查询算法，分析了算法的正确性和时间复杂度，并且提出了相关性结果排序方法.KWSDS系统的搜索算法运行时间短，搜索结果准确性高，具有良好的查询性能.最后通过实验验证了KWSDS的效率.

当前,在OLTP数据库的应用场景中,事务通常由一些简单的查询构成,尤其是大量存在的基于主键的读写事务.在这种应用场景下,逻辑锁能够避免复杂的逻辑判定,通过基于简单比较的语义封锁来防止不可重复读、幻象读等问题,从而实现事务的串行化调度.为了提高事务读写的并发能力,针对当前OLTP应用的特点,在谓词锁的基础上进一步细分锁粒度,提出属性谓词锁的理论,并在给定的复杂度内讨论了该理论在上述应用场景下的可行性.此外,通过在国产神通数据库的事务线程框架下模拟TPC-C的事务并发,一个测试属性谓词锁与物理行锁性能差异的实验得以顺利进行.对比实验结果表明，属性谓词锁在相对固定的属性列上进行简单查询和更新的应用中,可以大幅度地减少加锁的数目,从而在CPU和内存开销等性能指标上占据优势.