硬件组合技术在数据库查询优化中的应用

查询优化技术是关系数据库成功运作的关键技术之一。随着现代数据库规模不断扩大到以十亿字节(GB)计量,对能够处理如此巨大的数据信息的系统的需求也随之而来。找到一种高效的信息提取方法对于使研发过程更快、更容易地进行是十分必要的。文章介绍了一种将与或图和数字逻辑电路技术应用于SQL查询优化,得到数据库中有效信息的技术方法。该方法中把与或图作为一种中间数据结构,用来描述布尔值域上的查询集合的子集;数字逻辑电路则用来表示二进制数集合上的各项逻辑运算功能的一种实现方式。该文同时给出了相关实验结果,实验表明这是一个十分有效的方法。     

B~+-Tree的改进算法在可复用软构件库中的应用

文章通过对B+-Tree索引算法的改进,将其应用到可复用软构件库中。该改进算法继承了B+-Tree的优点,结合可复用软构件库的特点,将构件库多维数据索引转化为B+-Tree一维数据索引进行存储、查询。通过对比分析,证明了该构件库索引算法大大改进了构件库中构件的查找效率。     

经济地理信息系统

经济地理信息系统是基于地理信息系统开发平台，实现对大量资源数据信息进行计算机管理与辅助决策的大型软件系统。它利用计算机技术、地理信息系统(GIS)技术，在现有的基础信息库的基础上，联系相关部门的业务需要，实现经济信息管理的科学化和自动化。     

High-Speed Tools for Global Information Management.II. Specifications and Uses of the Transparent Query Language (TQL) Part IIF. Additional Uses of TQL, Data Structures, Concise Definitions, Conclusions and Acknowledgments

This part, PART IIF [6], concludes the document HIGH-SPEED TOOLS FOR GLOBAL INFORMATION MANAGEMENT. II. Specifications and Uses of the Transparent Query Language (TQL) [1–6]. It describes novel applications of TQL, the key data structures, and contains a dictionary of Transparent Query Language terms. PART IIF references PART IIA [1], PART IIB [2], PART IIC [3], PART IID [4], and PART IIE [5] and contains Conclusions and Acknowledgements.     

Faster joins, self-joins and multi-way joins using join indices

We propose a new algorithm, called Stripe-join, for performing a join given a join index. Stripe-join is inspired by an algorithm called ‘Jive-join’ developed by Li and Ross. Stripe-join makes a single sequential pass through each input relation, in addition to one pass through the join index and two passes through a set of temporary files that contain tuple identifiers but no input tuples. Stripe-join performs this efficiently even when the input relations are much larger than main memory, as long as the number of blocks in main memory is of the order of the square root of the number of blocks in the participating relations. Stripe-join is particularly efficient for self-joins. To our knowledge, Stripe-join is the first algorithm that, given a join index and a relation significantly larger than main memory, can perform a self-join with just a single pass over the input relation and without storing input tuples in intermediate files. Almost all the I/O is sequential, thus minimizing the impact of seek and rotational latency. The algorithm is resistant to data skew. It can also join multiple relations while still making only a single pass over each input relation. Using a detailed cost model, Stripe-join is analyzed and compared with competing algorithms. For large input relations, Stripe-join performs significantly better than Valduriez's algorithm and hash join algorithms. We demonstrate circumstances under which Stripe-join performs significantly better than Jive-join. Unlike Jive-join, Stripe-join makes no assumptions about the order of the join index.     

Evolutionary techniques for updating query cost models in a dynamic multidatabase environment

Deriving local cost models for query optimization in a dynamic multidatabase system (MDBS) is a challenging issue. In this paper, we study how to evolve a query cost model to capture a slowly-changing dynamic MDBS environment so that the cost model is kept up-to-date all the time. Two novel evolutionary techniques, i.e., the shifting method and the block-moving method, are proposed. The former updates a cost model by taking up-to-date information from a new sample query into consideration at each step, while the latter considers a block (batch) of new sample queries at each step. The relevant issues, including derivation of recurrence updating formulas, development of efficient algorithms, analysis and comparison of complexities, and design of an integrated scheme to apply the two methods adaptively, are studied. Our theoretical and experimental results demonstrate that the proposed techniques are quite promising in maintaining accurate cost models efficiently for a slowly changing dynamic MDBS environment. Besides the application to MDBSs, the proposed techniques can also be applied to the automatic maintenance of cost models in self-managing database systems.Received: 25 November 2002, Accepted: 20 May 2003, Published online: 30 September 2003Edited by: L. LiuResearch supported by the US National Science Foundation under Grant # IIS-9811980 and The University of Michigan under OVPR and UMD grants.     

Using categorical methods in computer science

Some categorical methods used in developing computer programs are considered. Relevant theorems are proved. Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 3–11, July–August, 2000.     

On querying simple conceptual graphs with negation

We consider basic conceptual graphs, namely simple conceptual graphs (SGs), which are equivalent to the existential conjunctive positive fragment of first-order logic. The fundamental problem, deduction, is performed by a graph homomorphism called projection. The existence of a projection from a SG Q to a SG G means that the knowledge represented by Q is deducible from the knowledge represented by G. In this framework, a knowledge base is composed of SGs representing facts and a query is itself a SG. We focus on the issue of querying SGs, which highlights another fundamental problem, namely query answering. Each projection from a query to a fact defines an answer to the query, with an answer being itself a SG. The query answering problem asks for all answers to a query.

This paper introduces atomic negation into this framework. Several understandings of negation are explored, which are all of interest in real world applications. In particular, we focus on situations where, in the context of incomplete knowledge, classical negation is not satisfactory because deduction can be proven but there is no answer to the query. We show that intuitionistic deduction captures the notion of an answer and can be solved by projection checking. Algorithms are provided for all studied problems. They are all based on projection. They can thus be combined to deal with several kinds of negation simultaneously. Relationships with problems on conjunctive queries in databases are recalled and extended. Finally, we point out that this discussion can be put in the context of semantic web databases.     

基于XML＋DOM4J的数据库集成技术研究

如何实现数据库的集成、共享和利用，提高了信息系统的整体效能，以及解决了XML和数据库双向传输的瓶颈，成为信息支持系统的关键问题之一。该文在分析可扩展标记语言XML特点的基础上，对XML与数据库之间基于DOM模型的映射方式进行了探讨，并给出了以XML文件作为中间文件的异构数据库集成，以及XML文档和数据库之间数据传输的实现方法。