检索结果-内蒙古大学图书馆

semantic query optimization FOR TREE AND CHAIN QUERIES

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 1994年第1期6卷 136-151页

作者： SUN, W YU, CT UNIV ILLINOIS DEPT ELECT ENGN & COMP SCICHICAGOIL 60680

semantic query optimization, or knowledge-based query optimization, has received increasing interest in recent years. This paper provides an effective and systematic approach to optimizing queries by appropriately choosing semantically equivalent transformations. Basically, there are two different types of transformations: transformations by eliminating unnecessary joins, and transformations by adding/eliminating redundant beneficial/nonbeneficial selection operations (restrictions). A necessary and sufficient condition to eliminate a single unnecessary join is provided. We prove that it is NP-Complete to eliminate as many unnecessary joins as possible for various types of acyclic queries with the exception of the closure chain queries whose query graphs are chains and all equi-join attributes are distinct. An algorithm is provided to minimize the number of joins in tree queries. This algorithm has an important property that, when applied to a closure chain query, it will yield an optimal solution with the time complexity 0(n * m), where n is the number of relations referenced in the chain query, and m is the time complexity of a restriction closure computation. (A restriction closure consists of all deducible restrictions of a query qualification under a given set of constraints. An algorithm to compute it was given in [46]).

关键词： CHAIN COMPLEXITY JOIN NP-COMPLETE query TRANSFORMATION RESTRICTION semantic query optimization TREE

来源：评论

学校读者我要写书评

暂无评论

semantic query optimization for query plans of heterogeneous multidatabase systems

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2000年第6期12卷 959-978页

作者： Hsu, CN Knoblock, CA Acad Sinica Inst Informat Sci Taipei 115 Taiwan Univ So Calif Inst Informat Sci Marina Del Rey CA 90292 USA Univ So Calif Dept Comp Sci Marina Del Rey CA 90292 USA

New applications of information systems, such as electronic commerce and healthcare information systems, need to integrate a large number of heterogeneous databases over computer networks. Answering a query in these applications usually involves selecting relevant information sources and generating a query plan to combine the data automatically. As significant progress has been made in source selection and plan generation, the critical issue has been shifting to query optimization. This paper presents a semantic query optimization (SQO) approach to optimizing query plans of heterogeneous multidatabase systems. This approach provides global optimization for query plans as well as local optimization for subqueries that retrieve data from individual database sources. An important feature of our local optimization algorithm is that we prove necessary and sufficient conditions to eliminate an unnecessary join in a conjunctive query of arbitrary join topology. This feature allows our optimizer to utilize more expressive relational rules to provide a wider range of possible optimizations than previous work in SQO. The local optimization algorithm also features a new data structure called AND-OR implication graphs to facilitate the search for optimal queries. These features allow the global optimization to effectively use semantic knowledge to reduce data transmission cost. We have implemented this approach into the PESTO query plan optimizer as a part of the SIMS information mediator. Experimental results demonstrate that PESTO can provide significant savings in query execution cost over query plan execution without optimization.

关键词： semantic query optimization heterogeneous multidatabase systems relational rules joins information mediators

来源：评论

学校读者我要写书评

暂无评论

semantic query optimization on object-oriented database

Semantic query optimization on object-oriented database

引用

13th ISSAT International Conference on Reliabitity and Quality in Design

作者： Wang, Mei-Tzu Chinese Culture Univ Dept Informat Management Taipei Taiwan

ISBN: (纸本)9780976348627

In this paper we discuss the problem of query optimization on object-oriented database. Rich semantic knowledge in terms of class hierarchy, aggregation hierarchy, and integrity constraints are considered in this work. In the effort of exploring the quantification of query performance, we develop a theorem to compute the maximum number of access in checking a predicate involving a nested attribute. From its corollary, we find that the decreased number of access of objects in earlier classes of the path have more effect on the total number of the access of objects under the assumption that all objects of all classes are uniformly distributed among all values of all attributes. Using this fact, we suggest that the predicate with a path of shorter length should be evaluated prior to another predicate with a path of longer length, if one path of the two is a sub path of the other. In the process of exploration, we conclude some guided rules and define efficiency ratio as measurement for quantifying query performance. Finally, a simple and easy-to-use algorithm is suggested for rewriting queries in order to achieve higher performance.

关键词： object-oriented database integrity constraint semantic query optimization schema class

来源：评论

学校读者我要写书评

暂无评论

LEARNING TRANSFORMATION RULES FOR semantic query optimization - A DATA-DRIVEN APPROACH

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 1993年第6期5卷 950-964页

作者： SHEKHAR, S HAMIDZADEH, B KOHLI, A COYLE, M HONG KONG UNIV SCI & TECHNOL DEPT COMP SCIKOWLOONHONG KONG

Learning query-transformation rules are vital for the success of semantic query optimization in domains where the user cannot provide a comprehensive set of integrity constraints. Finding these rules is a discovery task because of the lack of targets. Previous approaches to learning query-transformation rules have been based on analyzing past queries. We propose a new approach to learning query-transformation rules based on analyzing the existing data in the database. This paper describes a framework and a closure algorithm for learning rules from a given data distribution. We characterize the correctness, completeness, and complexity of the proposed algorithm and provide a detailed example to illustrate the framework.

关键词： DATA DISCOVERY IN DATABASES LEARNING RULE DISCOVERY semantic query optimization

来源：评论

学校读者我要写书评

暂无评论

Description logics for semantic query optimization in object-oriented database systems

引用

ACM TRANSACTIONS ON DATABASE SYSTEMS 2003年第1期28卷 1-50页

作者： Beneventano, D Bergamaschi, S Sartori, C Univ Modena & Reggio Emilia Modena Italy CNR CSITE I-00185 Rome Italy Univ Bologna I-40126 Bologna Italy

semantic query optimization uses semantic knowledge (i.e., integrity constraints) to transform a query into an equivalent one that may be answered more efficiently. This article proposes a general method for semantic query optimization in the framework of Object-Oriented Database Systems. The method is effective for a large class of queries, including conjunctive recursive queries expressed with regular path expressions and is based on three ingredients. The first is a Description Logic, ODLRE, providing a type system capable of expressing: class descriptions, queries, views, integrity constraint rules and inference techniques, such as incoherence detection and subsumption computation. The second is a semantic expansion function for queries, which incorporates restrictions logically implied by the query and the schema (classes + rules) in one query. The third is an optimal rewriting method of a query with respect to the schema classes that rewrites a query into an equivalent one, by determining more specialized classes to be accessed and by reducing the number of factors. We implemented the method in a tool providing an ODMG-compliant interface that allows a full interaction with OQL queries, wrapping underlying Description Logic representation and techniques to the user.

关键词： algorithms management languages theory semantic query optimization query rewriting method integrity constraints rules semantic expansion of a query description logics subsumption

来源：评论

学校读者我要写书评

暂无评论

Identifying relevant constraints for semantic query optimization

引用

INFORMATION AND SOFTWARE TECHNOLOGY 2000年第13期42卷 899-914页

作者： Lee, SG Henschen, LJ Chun, J Lee, T Seoul Natl Univ Sch Engn & Comp Sci Seoul South Korea Northwestern Univ Dept Elect & Comp Engn Evanston IL USA Myongji Univ Dept Comp Engn Yongin South Korea

semantic query optimization is the process of utilizing information implied by integrity constraints to reformulate the query into one that generates the same set of answers in a more efficient way. The difficulties of identifying relevant integrity constraints for a given query have been well recognized as have the various solutions. However, most of the previous works consider the query consisting of join(s) of base relations and the integrity constraints on base relations only. We generalize these restrictions and propose a method of identifying relevant integrity constraints for queries involving any combinations of joins and unions of base and defined relations. Our method utilizes a query graph that can be constructed dynamically during the query processing time, and, as a consequence, does not rely on heavy preprocessing or normalization. The method is extended to include the use of heuristics for generating a subset of answers. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： query processing semantic query optimization heuristics deductive database

来源：评论

学校读者我要写书评

暂无评论

semantic query optimization: Correctness and Control

引用

JOURNAL OF ADVANCED COMPUTATIONAL INTELLIGENCE AND INTELLIGENT INFORMATICS 2006年第3期10卷 270-280页

作者： Chippimolchai, Pongtawat Akama, Kiyoshi Wuwongse, Vilas Asian Inst Technol Comp Sci & Informat Management Program Km 42Paholyothin Highway Klongluang 12120 Pathumthani Thailand Hokkaido Univ Div Large Scale Computat Syst Informat Initiat Ct Kita Ku Sapporo Hokkaido 0600811 Japan

We developed a semantic query optimization framework for deductive databases based on equivalent transformation (ET) rules. ET rules, prepared from the semantic knowledge of databases, such as integrity constraints, transform given queries into syntactically different but semantically equivalent and more efficient forms. We formally prove the correctness of query transformations by ET rules. For efficiency, we propose a two-phase heuristic-based strategy to guide query transformations and introduce a condition-based control strategy to prevent unwanted, unnecessary transformations. We give examples demonstrating the possible optimization.

关键词： semantic query optimization deductive database integrity constraint equivalent transformation semantic preservation

来源：评论

学校读者我要写书评

暂无评论

An Efficient Algorithm for query Transformation in semantic query optimization

引用

High Technology Letters 2002年第1期8卷 32-36页

作者：何增有 Deng Shengchun Xu Xiaofei Song Yufu Department of Computer Science and Engineering Harbin Institute of Technology Harbin 150001 P.R.China

semantic query optimization (SQO) is comparatively a recent approach for the transformation of given query into equivalent alternative query using matching rules in order to select an optimal query based on the costs of executing alternative queries. The key aspect of the algorithm proposed here is that previous proposed SQO techniques can be considered equally in the uniform cost model, with which optimization opportunities will not be missed. At the same time, the authors used the implication closure to guarantee that any matched rule will not be lost. The authors implemented their algorithm for the optimization of decomposed sub-query in local database in Multi-Database Integrator (MDBI), which is a multidatabase project. The experimental results verify that this algorithm is effective in the process of SQO.

关键词： semantic query optimization Implication closure Multidatabase system Predict introduction Predict elimination

来源：评论

学校读者我要写书评

暂无评论

A semantic approach to optimize linear datalog programs

引用

ACTA INFORMATICA 2006年第5期43卷 341-370页

作者： Parama, Jose R. Brisaboa, Nieves R. Penabad, Miguel R. Places, Angeles S. Univ A Coruna Fac Informat Dept Comp Sci Database Lab La Coruna Spain

In this work, we present a semantic query optimization approach to improve the efficiency of the evaluation of a subset of SQL:1999 recursive queries. Using datalog notation, we can state our main contribution as an algorithm that builds a program P' equivalent to a given program P, when both are applied over a database d satisfying a set of functional dependencies. The input program P is a linear recursive datalog program. The new program P' has less different variables and, sometimes, less atoms in rules, thus it is cheaper to evaluate. Using CORAL and IBM DB2, P' is empirically shown to be more efficient than the original program.

关键词： deductive databases semantic query optimization SQL : 1999 recursion

来源：评论

学校读者我要写书评

暂无评论

Implication and referential constraints: A new formal reasoning

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 1997年第6期9卷 894-910页

作者： Zhang, XB Ozsoyoglu, ZM Intel Corp Santa Clara CA 95051 USA Case Western Reserve Univ Dept Comp Engn & Sci Cleveland OH 44106 USA

In this paper, we address the issue of reasoning with two classes of commonly used semantic integrity constraints in database and knowledge-base systems: implication constraints and referential constraints. We first consider a central problem in this respect, the IRC-refuting problem, which is to decide whether a conjunctive query always produces an empty relation on (finite) database instances satisfying a given set of implication and referential constraints. Since the general problem is undecidable, we only consider acyclic referential constraints. Under this assumption, we prove that the IRC-refuting problem is decidable, and give a novel necessary and sufficient condition for it. Under the same assumption, we also study several other problems encountered in semantic query optimization, such as the semantics-based query containment problem, redundant join problem, and redundant selection-condition problem, and show that they are polynomially equivalent or reducible to the IRC-refuting problem. Moreover, we give results on reducing the complexity for some special cases of the IRC-refuting problem.

关键词： semantic integrity constraints implication constraints referential constraints query containment semantic query optimization refutation database

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：