The SB-index and the HSB-index: efficient indices for spatial data warehouses

Spatial data warehouses (SDWs) allow for spatial analysis together with analytical multidimensional queries over huge volumes of data. The challenge is to retrieve data related to ad hoc spatial query windows according to spatial predicates, avoiding the high cost of joining large tables. Therefore, mechanisms to provide efficient query processing over SDWs are essential. In this paper, we propose two efficient indices for SDW: the SB-index and the HSB-index. The proposed indices share the following characteristics. They enable multidimensional queries with spatial predicate for SDW and also support predefined spatial hierarchies. Furthermore, they compute the spatial predicate and transform it into a conventional one, which can be evaluated together with other conventional predicates by accessing a star-join Bitmap index. While the SB-index has a sequential data structure, the HSB-index uses a hierarchical data structure to enable spatial objects clustering and a specialized buffer-pool to decrease the number of disk accesses. The advantages of the SB-index and the HSB-index over the DBMS resources for SDW indexing (i.e. star-join computation and materialized views) were investigated through performance tests, which issued roll-up operations extended with containment and intersection range queries. The performance results showed that improvements ranged from 68% up to 99% over both the star-join computation and the materialized view. Furthermore, the proposed indices proved to be very compact, adding only less than 1% to the storage requirements. Therefore, both the SB-index and the HSB-index are excellent choices for SDW indexing. Choosing between the SB-index and the HSB-index mainly depends on the query selectivity of spatial predicates. While low query selectivity benefits the HSB-index, the SB-index provides better performance for higher query selectivity.     

云原生数据库综述

云基础设施的虚拟化、高可用、可弹性调度等特点,为云数据库提供了开箱即用、可靠可用、按需计费等优势.云数据库按照架构可以划分为云托管数据库(cloud-hosted database)以及云原生数据库(cloud-native database).云托管数据库将数据库系统直接部署到云上虚拟机环境中,具备低成本、易运维、高可靠的优势.在此基础上,云原生数据库充分利用云基础设施弹性伸缩的特点,采用计算存储分离的架构,实现了计算资源和存储资源的独立伸缩,进一步提升数据库性价比.然而计算存储分离的架构为数据库系统设计带来了新的挑战.深入分析云原生数据库系统的架构和技术.首先将云原生OLTP和云原生OLAP的数据库架构按照资源分离模式的差异分别进行归类分析,并对比各类架构的优势与局限.其次,基于计算存储分离的架构,按照各个功能模块深入探讨云原生数据库的关键技术:主要包括云原生OLTP关键技术(数据组织、副本一致性、主备同步、故障恢复以及混合负载处理)和云原生OLAP关键技术(存储管理、查询处理、无服务器感知计算、数据保护以及机器学习优化).最后,总结现有云原生数据库的技术挑战并展望未来研究方向.     

LBS中外包空间数据的kNN安全查询方法

云计算服务允许数据拥有者将数据库外包出去,从而避免高昂的存储和计算资源,该方法的关键在于既要对第三方服务提供商保持数据的机密性,又要为认证用户提供实时查询结果。对此,提出一种转换和加密方法,应用到服务提供商在空间数据集上执行用户查询和响应过程中。采用空间填充Hilbert曲线将多维空间的每一个空间点映射到单维空间;基于顺序保留加密技术处理转换的空间数据;用户向服务提供商发起基于Hilbert值的空间kNN查询,并应用加密密钥对查询响应进行解密。实验证明该加密方法能减少认证用户与服务提供商之间的通信开销。     

On-demand multidimensional data integration: toward a semantic foundation for cloud intelligence

Cloud intelligence is a collection of technologies emerging from the migration of business intelligence and analytics technologies to a cloud computing environment combined with exploiting the massive range of new intelligence opportunities opened up by cloud computing. Cloud computing introduces several trends which require traditional business intelligence techniques to be re-thought, including agility, the ability to assemble resources, e.g., data sources, on-demand, and virtualization, e.g., that data are provided as a service over the web rather than stored in local databases. This paper focuses on the combination of data source agility and data-as-a-service virtualization and its use for cloud intelligence. After presenting the novel vision of the Cloud Warehouse, the paper goes on to present a comprehensive semantic foundation for on-demand multidimensional data integration, including formal data models, a range of query operators and re-write rules for optimization. This semantic foundation provides a sound formal basis for on-demand multidimensional data integration, which is a cornerstone of cloud intelligence.     

一种基于维层次编码的OLAP聚集查询算法

联机分析处理(OLAP)查询往往需在海量数据上进行即席的复杂分组聚集查询，在其SQL语句中通常包含多表连接和分组聚集操作，因而减少多表连接和压缩关键字，以及对查询数据进行有效地分组聚集操作，成为ROLAP查询处理的关键问题。提出了一种基于维层次编码的新型预分组聚集算法DHEPGA．DHEPGA算法充分利用了编码长度较小的维层次编码及其前缀，来快速检索出与查询关键字相匹配的维层次编码，求得维层次属性的查询范围，减少了I／O开销，提高了OLAP查询效率。理论分析和实验结果表明，DHEPGA算法性能是非常有效的。     

分布式聚集函数支持的内存OLAP并行查询处理技术

根据OLAP查询的特点和内存数据库的性能特征提出了由多个内存数据库组成的并行OLAP查询处理系统,将OLAP应用中的多维聚集查询分布到各个计算节点并行进行聚集计算,并将聚集计算的结果进行合并输出.与其他并行处理方法相比,该算法充分利用OLAP DB结构中维表远小于事实表的特性,根据数据库中事实表的数据量和节点的数据处理能力进行水平数据库分片,并根据聚集函数的可分布计算特性提高查询处理的并行度,延迟并行查询处理中的合并过程,充分利用节点的并行处理能力,减少并行查询处理过程中的数据通信量,提高系统并行查询处理性能.该算法易于实现,具有较好的可扩展性和性能,适用于企业级海量数据处理领域的需求.     

Ranked Query Processing in Uncertain Databases

Recently, many new applications, such as sensor data monitoring and mobile device tracking, raise up the issue of uncertain data management. Compared to "certain” data, the data in the uncertain database are not exact points, which, instead, often reside within a region. In this paper, we study the ranked queries over uncertain data. In fact, ranked queries have been studied extensively in traditional database literature due to their popularity in many applications, such as decision making, recommendation raising, and data mining tasks. Many proposals have been made in order to improve the efficiency in answering ranked queries. However, the existing approaches are all based on the assumption that the underlying data are exact (or certain). Due to the intrinsic differences between uncertain and certain data, these methods are designed only for ranked queries in certain databases and cannot be applied to uncertain case directly. Motivated by this, we propose novel solutions to speed up the probabilistic ranked query (PRank) with monotonic preference functions over the uncertain database. Specifically, we introduce two effective pruning methods, spatial and probabilistic pruning, to help reduce the PRank search space. A special case of PRank with linear preference functions is also studied. Then, we seamlessly integrate these pruning heuristics into the PRank query procedure. Furthermore, we propose and tackle the PRank query processing over the join of two distinct uncertain databases. Extensive experiments have demonstrated the efficiency and effectiveness of our proposed approaches in answering PRank queries, in terms of both wall clock time and the number of candidates to be refined.     

Policies for Caching OLAP Queries in Internet Proxies

The Internet now offers more than just simple information to the users. Decision makers can now issue analytical, as opposed to transactional, queries that involve massive data (such as, aggregations of millions of rows in a relational database) in order to identify useful trends and patterns. Such queries are often referred to as On-Line-Analytical Processing (OLAP). Typically, pages carrying query results do not exhibit temporal locality and, therefore, are not considered for caching at Internet proxies. In OLAP processing, this is a major problem as the cost of these queries is significantly larger than that of the transactional queries. This paper proposes a technique to reduce the response time for OLAP queries originating from geographically distributed private LANs and issued through the Web toward a central data warehouse (DW) of an enterprise. An active caching scheme is introduced that enables the LAN proxies to cache some parts of the data, together with the semantics of the DW, in order to process queries and construct the resulting pages. OLAP queries arriving at the proxy are either satisfied locally or from the DW, depending on the relative access costs. We formulate a cost model for characterizing the respective latencies, taking into consideration the combined effects of both common Web access and query processing. We propose a cache admittance and replacement algorithm that operates on a hybrid Web-OLAP input, outperforming both pure-Web and pure-OLAP caching schemes.     

Spatial aggregation: Data model and implementation

Data aggregation in Geographic Information Systems (GIS) is a desirable feature, only marginally present in commercial systems nowadays, mostly through ad hoc solutions. We address this problem introducing a formal model that integrates, in a natural way, geographic data and non-spatial information contained in a data warehouse external to the GIS. This approach allows both aggregation of geometric components and aggregation of measures associated to those components, defined in GIS fact tables. We define the notion of geometric aggregation, a general framework for aggregate queries in a GIS setting. Although general enough to express a wide range of (aggregate) queries, some of these queries can be hard to compute in a real-world GIS environment because they involve computing an integral over a certain area. Thus, we identify the class of summable queries, which can be efficiently evaluated replacing this integral with a sum of functions of geometric objects. Integration of GIS and OLAP (On Line Analytical Processing) is supported also through a language, GISOLAP-QL. We present an implementation, denoted Piet, which supports four kinds of queries: standard GIS, standard OLAP, geometric aggregation (like “total population in states with more than three airports”), and integrated GIS-OLAP queries (“total sales by product in cities crossed by a river”, also allowing navigation of the results). Further, Piet implements a novel query processing technique: first, a process called subpolygonization decomposes each thematic layer in a GIS, into open convex polygons; then, another process (the overlay precomputation) computes and stores in a database the overlay of those layers for later use by a query processor. Experimental evaluation showed that for a wide class of geometric queries, overlay precomputation outperforms R-tree-based techniques, suggesting that it can be an alternative for GIS query processing.     

支持混合事务和分析处理的数据库管理系统综述

数据库管理系统根据应用场景分为事务型(OLTP)系统和分析型(OLAP)系统.随着实时数据分析需求增长, OLTP任务和OLAP任务混合的场景越来越普遍,业界开始重视支持混合事务和分析处理(HTAP)的数据库管理系统.这种HTAP数据库系统除了需要满足高性能的事务处理外,还需要满足实时分析对数据新鲜度的要求.因此,对数据库系统的设计与实现提出了新的挑战.近年来,在工业界和学术界涌现了一批架构多样、技术各异的原型和产品.综述HTAP数据库的背景和发展现状,并且从存储和计算的角度对现阶段的HTAP数据库进行分类.在此基础上,按照从下往上的顺序分别总结HTAP系统在存储和计算方面采用的关键技术.在此框架下介绍各类系统的设计思想、优劣势以及适用的场景.此外,结合HTAP数据库的评测基准和指标,分析各类HTAP数据库的设计与其呈现出的性能与数据新鲜度的关联.最后,结合云计算、人工智能和新硬件技术为HTAP数据库的未来研究和发展提供思路.     

Improving performance by creating a native join-index for OLAP

The performance of online analytical processing (OLAP) is critical for meeting the increasing requirements of massive volume analytical applications. Typical techniques, such as in-memory processing, column-storage, and join indexes focus on high performance storage media, efficient storage models, and reduced query processing. While they effectively perform OLAP applications, there is a vital limitation: mainmemory database based OLAP (MMOLAP) cannot provide high performance for a large size data set. In this paper, we propose a novel memory dimension table model, in which the primary keys of the dimension table can be directly mapped to dimensional tuple addresses. To achieve higher performance of dimensional tuple access, we optimize our storage model for dimension tables based on OLAP query workload features. We present directly dimensional tuple accessing (DDTA) based join (DDTAJOIN), a technique to optimize query processing on the memory dimension table by direct dimensional tuple access. We also contribute by proposing an optimization of the predicate tree to shorten predicate operation length by pruning useless predicate processing. Our experimental results show that the DDTA-JOIN algorithm is superior to both simulated row-store main memory query processing and the open-source column-store main memory database MonetDB, thanks to the reduced join cost and simple yet efficient query processing.     

Efficient Distributed Skyline Queries for Mobile Applications

In this paper, we consider skyline queries in a mobile and distributed environment, where data objects are distributed in some sites (database servers) which are interconnected through a high-speed wired network, and queries are issued by mobile units (laptop, cell phone, etc.) which access the data objects of database servers by wireless channels. The inherent properties of mobile computing environment such as mobility, limited wireless bandwidth, frequent disconnection, make skyline queries more complicated. We show how to efficiently perform distributed skyline queries in a mobile environment and propose a skyline query processing approach, called efficient distributed skyline based on mobile computing (EDS-MC). In EDS-MC, a distributed skyline query is decomposed into five processing phases and each phase is elaborately designed in order to reduce the network communication, network delay and query response time. We conduct extensive experiments in a simulated mobile database system, and the experimental results demonstrate the superiority of EDS-MC over other skyline query processing techniques on mobile computing.     

Trip planning queries with location privacy in spatial databases

Privacy has become a major concern for the users of location-based services (LBSs) and researchers have focused on protecting user privacy for different location-based queries. In this paper, we propose techniques to protect location privacy of users for trip planning (TP) queries, a novel type of query in spatial databases. A TP query enables a user to plan a trip with the minimum travel distance, where the trip starts from a source location, goes through a sequence of points of interest (POIs) (e.g., restaurant, shopping center), and ends at a destination location. Due to privacy concerns, users may not wish to disclose their exact locations to the location-based service provider (LSP). In this paper, we present the first comprehensive solution for processing TP queries without disclosing a user’s actual source and destination locations to the LSP. Our system protects the user’s privacy by sending either a false location or a cloaked location of the user to the LSP but provides exact results of the TP queries. We develop a novel technique to refine the search space as an elliptical region using geometric properties, which is the key idea behind the efficiency of our algorithms. To further reduce the processing overhead while computing a trip from a large POI database, we present an approximation algorithm for privacy preserving TP queries. Extensive experiments show that the proposed algorithms evaluate TP queries in real time with the desired level of location privacy.     

A workload-driven approach to database query processing in the cloud

This paper is concerned with data provisioning services (information search, retrieval, storage, etc.) dealing with a large and heterogeneous information repository. Increasingly, this class of services is being hosted and delivered through Cloud infrastructures. Although such systems are becoming popular, existing resource management methods (e.g. load-balancing techniques) do not consider workload patterns nor do they perform well when subjected to non-uniformly distributed datasets. If these problems can be solved, this class of services can be made to operate in more a scalable, efficient, and reliable manner. The main contribution of this paper is a approach that combines proprietary cloud-based load balancing techniques and density-based partitioning for efficient range query processing across relational database-as-a-service in cloud computing environments. The study is conducted over a real-world data provisioning service that manages a large historical news database from Thomson Reuters. The proposed approach has been implemented and tested as a multi-tier web application suite consisting of load-balancing, application, and database layers. We have validated our approach by conducting a set of rigorous performance evaluation experiments using the Amazon EC2 infrastructure. The results prove that augmenting a cloud-based load-balancing service (e.g. Amazon Elastic Load Balancer) with workload characterization intelligence (density and distribution of data; composition of queries) offers significant benefits with regards to the overall system’s performance (i.e. query latency and database service throughput).     

基于划分的数据仓库查询归并缓冲算法

在数据仓库中存在着大量的数据。联机分析处理包含着对大量数据的复杂的查询过程。在对这些数据的存储与查询中都遇到了许多困难。解决这一问题的有效办法就是先将数据划分成便于处理的数据块,再分别对每个数据块进行处理,最后将个数据块的处理结果归并在一起。对几种常用的归并算法进行了比较,并讨论了归并中的缓冲区分配问题。     

空间数据索引与查询技术研究及其应用

由于空间数据本身的复杂性,以及目前对海量空间数据快速查询的要求日益提高,当前地理信息系统正面临着大数据量空间数据存储及管理的挑战。因此,该文在对当今空间存储方法及空间查询的一些主要技术进行比较和分析之后,提出了基于R树的优化的空间查询系统框架设计,并在一个地理信息系统的应用实例中实现了该设计。     

High Performance OLAP and Data Mining on Parallel Computers

On-Line Analytical Processing (OLAP) techniques are increasingly being used in decision support systems to provide analysis of data. Queries posed on such systems are quite complex and require different views of data. Analytical models need to capture the multidimensionality of the underlying data, a task for which multidimensional databases are well suited. Multidimensional OLAP systems store data in multidimensional arrays on which analytical operations are performed. Knowledge discovery and data mining requires complex operations on the underlying data which can be very expensive in terms of computation time. High performance parallel systems can reduce this analysis time. Precomputed aggregate calculations in a Data Cube can provide efficient query processing for OLAP applications. In this article, we present algorithms for construction of data cubes on distributed-memory parallel computers. Data is loaded from a relational database into a multidimensional array. We present two methods, sort-based and hash-based for loading the base cube and compare their performances. Data cubes are used to perform consolidation queries used in roll-up operations using dimension hierarchies. Finally, we show how data cubes are used for data mining using Attribute Focusing techniques. We present results for these on the IBM-SP2 parallel machine. Results show that our algorithms and techniques for OLAP and data mining on parallel systems are scalable to a large number of processors, providing a high performance platform for such applications.     

HTAP数据库关键技术综述

混合事务与分析处理(hybridtransactionalanalyticalprocessing,HTAP)技术是一种基于一站式架构同时处理事务请求与查询分析请求的技术. HTAP技术不仅消除了从关系型事务数据库到数据仓库的数据抽取、转换和加载过程,还支持实时地分析最新事务数据.然而,为了同时处理OLTP与OLAP, HTAP系统也需要在系统性能与数据分析新鲜度之间做出取舍,这主要是因为高并发、短时延的OLTP与带宽密集型、高时延的OLAP访问模式不同且互相干扰.目前,主流的HTAP数据库主要以行列共存的方式来支持混合事务与分析处理,但是由于该类数据库面向不同的业务场景,所以它们的存储架构与处理技术各有不同.首先,全面调研HTAP数据库,总结它们主要的应用场景与优缺点,并根据存储架构对它们进行分类、总结与对比.现有综述工作侧重于基于行/列单格式存储的HTAP数据库以及基于Spark的松耦合HTAP系统,而这里侧重于行列共存的实时HTAP数据库.特别地,凝炼了主流HTAP数据库关键技术,包括数据组织技术、数据同步技术、查询优化技术、资源调度技术这4个部分.同时总结分析了HTAP数据库构...     

Distributed snapshot maintenance in wide-column NoSQL databases using partitioned incremental ETL pipelines

Wide-column NoSQL databases are an important class of NoSQL (Not only SQL) databases which scale horizontally and feature high access performance on sparse tables. With current trends towards big Data Warehouses (DWs), it is attractive to run existing business intelligence/data warehousing applications on higher volumes of data in wide-column NoSQL databases for low latency by mapping multidimensional models to wide-column NoSQL models or using additional SQL add-ons. For examples, applications like retail management can run over integrated data sets stored in big DWs or in the cloud to capture current item-selling trends. Many of these systems also employ Snapshot Isolation (SI) as a concurrency control mechanism to achieve high throughput for read-heavy workloads. SI works well in a DW environment, as analytical queries can now work on (consistent) snapshots and are not impacted by concurrent update jobs performed by online incremental Extract-Transform-Load (ETL) flows that refresh fact/dimension tables. However, the snapshot made available in the DW is often stale, since at the moment when an analytical query is issued, the source updates (e.g. in a remote retail store) may not have been extracted and processed by the ETL process in time due to high input data volume or slow processing speed. This staleness may cause incorrect results for time-critical decision support queries. To address this problem, snapshots which are supposed to be accessed by analytical queries need to be first maintained by corresponding ETL flows to reflect source updates based on given freshness needs. Snapshot maintenance in this work means maintaining the distributed data partitions that are required by a query. Since most NoSQL databases are not ACID compliant and do not provide full-fledged distributed transaction support, snapshot may be inconsistently derived when its data partitions are updated by different ETL maintenance jobs.This paper describes an extended version of HBelt system [1] which tightly integrates the wide-column NoSQL database HBase with a clustered & pipelined ETL engine. Our objective is to efficiently refresh HBase tables with remote source updates while a consistent snapshot is guaranteed across distributed partitions for each scan request in analytical queries. A consistency model is defined and implemented to address so-called distributed snapshot maintenance. To achieve this, ETL jobs and analytical queries are scheduled in a distributed processing environment. In addition, a partitioned, incremental ETL pipeline is introduced to increase the performance of ETL (update) jobs. We validate the efficiency gain in terms of data pipelining and data partitioning using the TPC-DS benchmark, which simulates a modern decision support system for a retail product supplier. Experimental results show that high query throughput can be achieved in HBelt when distributed, refreshed snapshots are demanded.     

联机分析查询处理中的一种聚集算法

联机分析处理(online analytical processing,简称OLAP)查询是涉及大量数据的即席复杂查询,从SQL(structured query language)角度来看,这些查询通常都包含多表连接和分组聚集操作.从OLAP查询处理角度出发,提出一种新的基于排序的聚集查询算法MuSA(sort-based aggregation with multi-table join).该方法充分考虑到数据仓库星型模式的特点,将聚集操作和新的多表连接算法MJoin相结合,排序时采用