外包数据库中基于随机噪声的查询完全性验证

数据库外包允许企业或机构把数据库管理工作外包给专业第三方,将精力集中在其核心业务。在数据库外包研究领域中存在隐私保护、查询完整性验证和用户访问控制等安全问题。在冗余数据方法的基础上,提出对冗余数据增加随机噪声,为外包数据库提供查询结果完整性检验。实验结果表明了该方法安全性和有效性。     

基于数字水印的外包数据库查询验证

外包数据库的查询验证,是指客户端对外包数据库的数据来源真实性、查询运算正确性及查询结果完整性的验证。提出一种基于脆弱型数字水印对外包数据库查询的真实性进行验证的解决方案。在密钥的控制下,以混沌方程产生随机二值序偶作为水印信号并确定其嵌入方式,通过修改数值型属性低位数字的奇偶性嵌入水印,通过对数据库查询结果运行水印检测算法进行查询验证。该方法具有冗余存储量与网络附加负载小、隐蔽性好、能同时实现篡改定位等优点。     

外包空间数据库中反向k近邻查询验证

在外包空间数据库模式下,数据持有者委托第三方数据发布者代替它来管理数据并且执行查询.当发布者受到攻击或者由于自身的不安全性,它可能返回不正确的查询结果给用户.基于已有的反向k近邻(ReversekNearest Neighbor,RkNN)查询方法,采用将反向k近邻查询验证转化成k近邻查询验证和范围查询验证的思想,提出一种反向k近邻查询验证的方法,并且设计了相应的算法,用于验证返回给客户端结果的正确性(没有结果点被篡改),有效性(结果点都满足用户的查询要求)和完整性(没有遗漏符合查询要求的结果点).实验验证了算法的有效性和实用性.     

追加型数据库外包中的查询结果验证

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

基于MH树的外包数据库查询验证方法

分析Merkle Hash(MH)树的结构特征,针对MH树的验证对象大、验证过程存在冗余、安全性低等不足,提出一种新的外包数据查询认证方法,使用部分物化中间节点的签名方法进行优化。分析结果表明,该方法具有网络附加负载小、验证快、安全性较高、能迅速实现篡改定位等优点。     

外包XML数据库查询验证技术

外包XML数据库的查询验证目标是保证XML数据和结构的可信性.为此,设计一种基于RMH树的数据结构,改进现有查询验证算法,对XML数据和结构进行真实性、完整性和最新性的验证,并且使数据的完整性验证具有隐私保护功能.理论分析和实验结果表明,该方案在查询验证效率、存储成本、安全性等方面均优于现有验证方案.     

面向外包空间数据库的范围查询验证

针对空间范围查询验证方法（例如VR-tree和MR-tree）普遍存在验证对象（VO）中包含大量的节点验证信息,造成服务器到客户端的传输代价较大以及客户端验证效率较低等问题,提出一种新的验证索引结构（ADS）MGR-tree。首先利用拆分思想,通过在Grid-tree的叶子节点中嵌入R-tree,并结合Merkle哈希树的验证方法,极大地减小VO的大小,提高查询和验证的效率。在此基础上,利用Hilbert曲线降维的特性,构建了优化的索引结构MHGR-tree,并提出一种过滤策略,进一步提高验证的效率。实验结果表明,所提方法具有更好的表现。在最好情况下,MHGR的VO大小和验证时间仅为MR的63%和19%。     

一种改进的外包数据库查询验证技术

在外包数据库系统模式下,由于外包服务器并非完全可信,给外包服务带来一系列安全问题。讨论了外包数据库安全体系的分类,针对外包数据中的完整性问题,介绍了常用的外包数据库查询验证技术。通过对SAE模型的分析研究,提出一种改进的基于B+树的查询验证方案,可以有效减少存储开销,提高搜索效率,并能精确定位篡改位置,同时保证可信第三方的合法权益。理论分析和实验数据表明,该方案具有存储开销小、验证速度快、安全性高等优点。     

关于外包数据库完整性验证的研究

数据库外包是一种重要的新兴的趋势,它让数据所有者把他们的数据管理工作委托给一个外部服务商.服务商管理客户的数据库,为客户提供安全可靠的机制来创建、存储、更新和访问他们自己的数据库.这种模式引出了数据安全的研究议题,文中通过对比几种不同的签名方式,提出了有效的数据完整性机制模型和安全有效的压缩RSA方案来确保数据的完整性和真实性.它在单一客户端和多查询者模型中运行良好,同时保证了计算量和带宽损耗在最低范围内.     

数据库查询理论

一、引言从 Codd 引进关系数据库开始,在理解怎样才能从数据库中提取数据方面已做了大量工作。已经提出和开发了许多数据库系统和查询语言,包括 SQL,QBE,QUEL,L-DL 等。与此同时,数据库的查询理论已成长为一个丰满的技术领域,这一发展把更重实效的开发建立在对问题的全面理解之上。确实,现在逻辑程序设计方面开展的研究就是这种情况。本文的目的不是全面地综述数据库查询理论,而是指出随着该领域的发展,使得该领域成型的一些思想。二、一阶查询和关系代数第一个重要的思想来自 Codd,他考察     

Bucket‐based authentication for outsourced databases

When outsourced database owners delegate their data to service providers, which might be untrusted or compromised, two issues of data security emerge, including data confidentiality and data integrity. Most of the previous research focuses on only one issue and the solution to integrate two approaches is expensive. In this paper, we propose bucket‐based authentication that can keep data confidentiality and meanwhile guarantee data integrity. Specifically, we first propose a new approach based on bucket checksum, which can be used for the authentication of multiple tuples at one time. We then apply bucket checksum to the authentication of various types of queries in static scenarios, including range queries and aggregation queries, such as MIN, MAX, SUM and COUNT queries. In the authentication of aggregation queries, several pruning rules have been proposed to improve performance further. We also extend our approach to dynamic scenarios based on incremental hash. Cost analysis shows the advantages of our approach over previous ones in terms of construction and verification cost. Experimental results show that our approach is both efficient and effective. Copyright © 2010 John Wiley & Sons, Ltd.     

Authenticated indexing for outsourced spatial databases

In spatial database outsourcing, a data owner delegates its data management tasks to a location-based service (LBS), which indexes the data with an authenticated data structure (ADS). The LBS receives queries (ranges, nearest neighbors) originating from several clients/subscribers. Each query initiates the computation of a verification object (VO) based on the ADS. The VO is returned to the client that can verify the result correctness using the public key of the owner. Our first contribution is the MR-tree, a space-efficient ADS that supports fast query processing and verification. Our second contribution is the MR*-tree, a modified version of the MR-tree, which significantly reduces the VO size through a novel embedding technique. Finally, whereas most ADSs must be constructed and maintained by the owner, we outsource the MR- and MR*-tree construction and maintenance to the LBS, thus relieving the owner from this computationally intensive task.     

Query optimization in XML structured-document databases

While the information published in the form of XML-compliant documents keeps fast mounting up, efficient and effective query processing and optimization for XML have now become more important than ever. This article reports our recent advances in XML structured-document query optimization. In this article, we elaborate on a novel approach and the techniques developed for XML query optimization. Our approach performs heuristic-based algebraic transformations on XPath queries, represented as PAT algebraic expressions, to achieve query optimization. This article first presents a comprehensive set of general equivalences with regard to XML documents and XML queries. Based on these equivalences, we developed a large set of deterministic algebraic transformation rules for XML query optimization. Our approach is unique, in that it performs exclusively deterministic transformations on queries for fast optimization. The deterministic nature of the proposed approach straightforwardly renders high optimization efficiency and simplicity in implementation. Our approach is a logical-level one, which is independent of any particular storage model. Therefore, the optimizers developed based on our approach can be easily adapted to a broad range of XML data/information servers to achieve fast query optimization. Experimental study confirms the validity and effectiveness of the proposed approach.     

A study of homogeneity in relational databases

We define four different properties of relational databases which are related tothe notion of homogeneity in classical model theory. The main question for their definition is, for any given database to determine the minimum integer k, such that whenever two k-tuples satisfy the same properties which are expressible in first order logic with up to k variables (FO ^k ), then there is an automorphism which maps each of these k-tuples onto each other. We study these four properties as a means to increase the computational power of subclasses of the reflective relational machines (RRMs) of bounded variable complexity. These were introduced by S. Abiteboul, C. Papadimitriou and V. Vianu and are known to be incomplete. For this sake we first give a semantic characterization of the subclasses of total RRM with variable complexity k (RRM ^k ) for every natural number k. This leads to the definition of classes of queries denoted as Q C Q ^k . We believe these classes to be of interest in their own right. For each k>0, we define the subclass Q C Q ^k as the total queries in the class C Q of computable queries which preserve realization of properties expressible in FO ^k . The nature of these classes is implicit in the work of S. Abiteboul, M. Vardi and V. Vianu. We prove Q C Q ^k =total(RRM ^k ) for every k>0. We also prove that these classes form a strict hierarchy within a strict subclass of total(C Q). This hierarchy is orthogonal to the usual classification of computable queries in time-space-complexity classes. We prove that the computability power of RRM ^k machines is much greater when working with classes of databases which are homogeneous, for three of the properties which we define. As to the fourth one, we prove that the computability power of RRM with sublinear variable complexity also increases when working on databases which satisfy that property. The strongest notion, pairwise k-homogeneity, allows RRM ^k machines to achieve completeness.     

脏数据库的查询方法研究

对于给定的约束,多个数据源分别是一致的,但是在它们集成时可能是脏的.已经存在的技术能够通过特别的方法识别出数据集成环境下的脏数据,但是不能进行有效处理.分析查询对应的连接图是否为有向连接图,判断查询是否可重写,并且给出了元组概率计算和基本查询重写方法.使用TPC-H基准的数据和查询比较脏数据多粒度的执行性能,实验显示方法是可行的.     

可验证的多用户云加密关键字搜索方案

针对云环境下多用户访问和大数据量存储的特点,提出了一种云环境下加密关键字搜索方案。与已有的大多数方案相比,该方案使用签名绑定关键字索引和其关联加密文件,实现了查询结果完备性和完整性的验证,使用重加密技术实现了多用户隐查询,并动态更新用户查询权限。此外,该方案在查询过程中使用哈希查询优化索引结构,实现了对云数据的快速访问。安全性分析表明,该方案是安全的;性能分析及仿真实验结果表明该方案和已有的一些算法相比有了较大的性能提升。     

Query verification schemes for cloud-hosted databases: a brief survey

Database query verification schemes provide correctness guarantees for database queries. Typically such guarantees are required and advisable where queries are executed on untrusted servers. This need to verify query results, even though they may have been executed on one’s own database, is something new that has arisen with the advent of cloud services. The traditional model of hosting one’s own databases on one’s own servers did not require such verification because the hardware and software were both entirely within one’s control, and therefore fully trusted. However, with the economical and technological benefits of cloud services beckoning, many are now considering outsourcing both data and execution of database queries to the cloud, despite obvious risks. This survey paper provides an overview into the field of database query verification and explores the current state of the art in terms of query execution and correctness guarantees provided for query results. We also provide indications towards future work in the area.     

基于商用数据库管理系统的字符串数据的加密存储与查询

在非可信环境下对数据进行加密是保护数据库中数据安全的一种有效方法，但如何对加密数据进行高效地查询是一个难点，引起了研究界的重视．本文提出加密字符数据的一种存储结构，除了加密数据以外，还以加密的方式存储了原始数据的特征值，并基于这种结构实现了对加密数据的两阶段查询方法，通过实验证明其性能较先解密后查询的方法有较大的提高．