Search

Query optimizer is at the heart of the database systems. Cost-based optimizer studied in this paper is adopted in almost all current database systems. A cost-based optimizer introduces a plan enumeration algorithm to find a (sub)plan, and then uses a cost model to obtain the cost of that plan, and selects the plan with the lowest cost. In the cost model, cardinality, the number of tuples through an operator, plays a crucial role. Due to the inaccuracy in cardinality estimation, errors in cost model, and the huge plan space, the optimizer cannot find the optimal execution plan for a complex query in a reasonable time. In this paper, we first deeply study the causes behind the limitations above. Next, we review the techniques used to improve the quality of the three key components in the cost-based optimizer, cardinality estimation, cost model, and plan enumeration. We also provide our insights on the future directions for each of the above aspects., This paper was accepted by Data Science and Engineering (DSEJ) in Dec, 2020

Indexes are crucial for the efficient processing of database workloads and an appropriately selected set of indexes can drastically improve query processing performance. However, the selection of beneficial indexes is a non-trivial problem and still challenging. Recent work in deep reinforcement learning (DRL) may bring a new perspective on this problem. In this paper, we studied the index selection problem in the context of reinforcement learning and proposed an end-to-end DRL-based index selection framework. The framework poses the index selection problem as a series of 1-step single index recommendation tasks and can learn from data. Unlike most existing DRL-based index selection solutions that focus on selecting single-column indexes, our framework can recommend both single-column and multi-column indexes for the database. A set of comparative experiments with existing solutions was conducted to demonstrate the effectiveness of our proposed method.

We study the problem of index selection to maximize the workload performance, which is critical to database systems. In contrast to existing methods, we seamlessly integrate index recommendation rules and deep reinforcement learning, such that we can recommend single-attribute and multi-attribute indexes together for complex queries and meanwhile support multiple-index access to a table. Specifically, we first propose five heuristic rules to generate the index candidates. Then, we formulate the index selection problem as a reinforcement learning task and employ Deep Q Network (DQN) on it. Using the heuristic rules can significantly reduce the dimensions of the action space and state space in reinforcement learning. With the neural network used in DQN, we can model the interactions between indexes better than previous methods. We conduct experiments on various workloads to show its superiority.

Genealogy is one of the three kinds of historical literatures which are valuable to historical research and humanities research. However, traditionally, it is hard to build and revise a genealogy. And it is even impossible to manage and query the genealogy efficiently. In this paper, we proposed PZXG, which is a genealogy data service platform, to solve these issues. Firstly, for structured and unstructured genealogy data, we employ relational database, graph database and distributed file system to store them respectively. Secondly, depending on the hybrid data model of genealogy data, various management features like data acquisition, kin seeking, genealogy exhibition and automatic typesetting are provided. Then in order to extract knowledge from genealogy data, the features of routine statistics and query, root tracing, correlation analysis and data visualization in genealogical data are discussed, and several methods and ideas of text mining for genealogical text are given. Finally, two more urgent research points in the genealogical data management platform are suggested: extracting structural information from unstructured genealogy data and construction of genealogy-specific text language model.

In recent years, a few researches focus on the similarity measure of semantic trajectories in road networks, since semantic trajectories in road networks have smaller volumes, higher qualities and can better reflect user behaviors. However, these works do not further discuss how to efficiently search similar trajectories. Thus, to implement an efficient similarity search, we design an index called SIET based on the structures of road networks. Then, we propose a novel algorithm called SSN-BF to search similar trajectories efficiently by using best-first strategy. At last, we take the experimental evaluations on real dataset and prove the efficiency of our algorithm.

The rapid flourishing of GIS applications has made the copyright protection and content authentication of vector maps two important issues in the digital world. In this paper, a multipurpose watermarking scheme is proposed for the scenarios when the two requirements are needed simultaneously. In the scheme, robust watermark and fragile watermarks are embedded into the host map simultaneously. To avoid the interference between the two kinds of watermarks, robust watermark is embedded into the feature points of the objects in the map, while fragile watermarks are embedded into the nonfeature points. Due to the independence of the feature points and non-feature points, the robust watermark and fragile watermarks can be detected independently. After watermark detection, the robust watermark can be used for copyright protection, and the fragile watermarks can be used for tamper localization and characterization. The fragility of the proposed scheme is analyzed theoretically, and both the robustness and the fragility are verified by a set comprehensive experiments.

With the rapid development of GIS and computer technology, the geo-spatial data has been widely used in many fields. Since the production of geo-spatial data is very costly, illegal copying will lead to huge loss of the data owner. In order to protect the copyright of geo-spatial data, digital watermarking has been employed in recent years. In this paper, current works on geo-spatial watermarking and cardinal attacks are analyzed. Consequently, a blind watermarking scheme for polylines in vector geo-spatial data is proposed. In the proposed scheme, FVDR (feature vertex distance ratio) is constructed based on the feature vertices of polylines. As the cover data, FVDR is slightly modified through quantization index modulation to embed the corresponding watermark bit. Each bit in the watermark is embedded in several polylines, by doing so each of these polylines contains a copy of the corresponding watermark bit. Because of the specially designed cover data, quantization modulation and redundant embedding, the proposed scheme is robust to geometrical attacks, vertex attacks and object attacks. Also, the results of extensive experiments demonstrate the robustness of the proposed scheme.

With the development of the positioning technology, studies on trajectories have been growing rapidly in the past decades. As a fundamental part involved in trajectory recommendation and prediction, trajectory similarity has attracted considerable attention from researchers. However, most existing works focus on raw trajectory similarity by comparing their shapes, while very few works study semantic trajectory similarity and none of them take all the geographical, semantic, and timestamp information into consideration. In this paper, we model semantic trajectories based on road networks considering all these information, and propose a Constrained Time-based Common Parts (CTCP) approach to measure the similarity. Since the strict time constraint in CTCP may lead to many zero values, we further propose an improved Weighted Constrained Time-based Common Parts (WCTCP) method by relaxing the time constraint to measure the similarity more accurately. We conducted extensive performance studies on real datasets to confirm the effectiveness of our approaches.

With the rapid development of GIS and computer techniques, vector map data has been widely used in many fields. Since the production of map data is very costly, illegal copying will result in huge loss for data owners. In order to protect the copyright of vector data, digital watermarking has been employed in recent years. In this paper, a zero-watermarking scheme for vector map data is proposed. In the proposed scheme, FVDR (feature vertex distance ratio) is constructed based on the feature vertices of objects. The feature data, FVDR, is combined with watermark to generate the zero-watermark. Due to the specially designed cover data, the proposed scheme is robust to geometrical attacks, vertex attacks, and object attacks. The results of extensive experiments also demonstrate the robustness of the proposed scheme.

In order to improve the retrieval performance of on-line information retrieval systems, an efficient index update scheme is proposed in this paper, which can provide better skipping function and further enhance both space and time efficiencies without inserting any additional auxiliary information. A uniform storage model (USM) is proposed to manage both short and long postings lists based on link. A USM-based update scheme also is proposed to distinguish long and short posting lists, which merges short lists with immediately merge, and merges long lists with improved Y-limited contiguous multiple merge scheme, which balances the trade-off of the time and space efficiencies effectively. The proposed update scheme not only considers both index level and inverted list level update, but also effectively improves time and space efficiencies of index update. Detailed experimental results and comparison with existed schemes show that the proposed scheme greatly averagely reduces space cost, conjunctive Boolean query time, and the cost of on-line index construction

In this paper, with current cryptography theory and watermarking technology of vector spatial data, we design a watermarking protocol for vector spatial data. This protocol combines trusted third party protocol and buyer-seller rotocol. In this protocol, digital signature technique is employed to identity buyer and seller involved in the trade of spatial data product. Trusted third party transforms watermark information used in the trade to ensure the secrecy. Anonymous mechanism is employed in this protocol, the buyer has the anonymity to protect its privacy. In the watermark embedding process, we make the embedding operation and the encrypted operation into an atomic operation, to protect the interests of consumers. In addition, all information is encrypted to prevent disclosure in every stage of the trade. After theoretical analysis, it shows that this protocol can solve the security aspects of watermarking protocol and can resist all kinds of attacks against the protocol.

Currently, most indexing methods of moving objects are focused on the past position, or the present and future one. In this paper, we propose a novel indexing method, called History TPR*-tree(HTPR*-tree), which not only supports predictive queries but also partial history ones involved from the most recent update instant of each object to the last update time of all objects. Based on the TPR*-tree, our Basic HTPR*-tree adds creation or update time of moving objects to leaf node entries. In order to improve the update performance, we present a bottom-up update strategy for the HTPR*-tree by supplementing a hash table, a bit vector and a direct access table. Experimental results show that the update performance of the HTPR*-tree is better than that of the Basic HTPR*-and TPR*-tree. In addition to support partial history queries, the update and predictive query performance of the HTPR*-tree are greatly improved compared with those of the RPPF-tree.

This paper proposes an index structure for Object Deputy Database, which is named as 'Object Deputy Path Index (ODPI)'. ODPI can reduce the cost of evaluating path expressions, which is the most important process of Cross-Class Query in Object Deputy Database. Object Deputy Path Index can materialize path instances in the index structure, avoiding redundant object traversal in query processing. This paper also introduces a maintenance method for ODPI. The experiments analyze the influential factors of path expression evaluation, and the experimental results demonstrate that path expression evaluation with ODPI outperforms the other methods in most cases.

Object-fusion is an important problem in database integration. In spatial databases, we can use spatial properties of objects for fusing them. Most approaches has been proposed only considered the point-like objects but rarely linear and polygonal objects. These approaches use points (e.g., center point) of complex objects to approximate them. Actually the fusion of linear and polygonal objects are as important as point-like ones in practice. Furthermore, linear or polygonal objects can not be approximated by points simply, for many linear or polygonal objects with very different shapes can also have the very similar approximation points. For these reasons, approaches for linear and polygonal objects fusion are desirably in spatial database integration. In this paper, we proposed a method to fuse polygonal objects using their spatial properties such as locations and shapes. An evaluation is also given in this paper.

Information integration service has changed from the traditional query-oriented to the future user-oriented service. The current research on information integration service focuses on providing personalized service based on user's preference, interest and habit. In order to solve the problem of personality in information integration, a novel method based on Object Deputy Model is proposed and the architecture of Personalized Information Integration System by Object Deputy Model (PIISODM) is established. PIISODM has fully utilized the flexible object views, multiple roles and dynamic classification of Object Deputy Model. It can generalize personalized integration views very easily and efficiently. A use case of PIISODM applied in personalized electronic map system is shown to illustrate the validity of the method.

The development of a spatio-temporal access method suitable for objects moving on fixed networks is a very attractive challenge due to a large number of applications dealing with this type of objects. In this paper, we propose a novel indexing technique named PPFI which consists of a 2D R*-tree, a forest of 1D R*-tree, and a hash structure. PPFI not only supports queries related to the past positions or trajectories of moving objects on fixed networks, but also provides an efficient update mechanism, stores current positions and supports predictive query. The performance study, comparing this access method with FNR-Tree, STR-Tree under range query and trajectory query, shows that PPFI outperforms them.

Multi-representation geographic information system (GIS) is used to store and manage geographic objects with different scales and semantics. It is difficult for relational and object-oriented databases to support multi-representation GIS. This paper proposed a new approach to realize multi-representation GIS using our object deputy database, where an object can have multiple deputy objects which inherit attributes and methods of the source object and can have their own attributes and methods. Multi-representations of a geographic object are defined by its deputy objects. So deputy objects can be used to represent viewpoint-multiplicity and role-multiplicity of geographic objects. Dynamic classification and automatic consistency maintenance of geographic objects can be supported through the update propagation mechanism of our object deputy database. In addition, the bilateral links between a geographic object and its deputy objects make cross-representation query easier. We have implemented a multi-representation GIS based on our object deputy database. Experiments show our method is more efficient than the traditional ones.

With the rapid development of Internet, the demand for various kinds of electronic maps is increased greatly. But the existing electronic maps have some problem. In terms of user, there is too much geographical information on the maps; it is very difficult for user to find ones' targets very clearly. On the other hand, in terms of developer, the data is stored and managed by relational database or objectrelational database. If we need to extend the system, we must change the structure of data greatly or add more redundancy. In this paper, we proposed a method to build electronic map systems using Object Deputy Model proposed by us under supervision of Prof. Kambayashi. Our electronic map system enables user to create their own maps according to their need or interests. In addition, the electronic maps can be personalized more easily.