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

EFFICIENT query-processing FOR A SUBSET OF LINEAR recursive BINARY RULES

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 1994年第5期6卷 842-849页

作者： GUH, KC YU, C UNIV ILLINOIS DEPT ELECT ENGN & COMP SCICHICAGOIL 60680

We study the complexity of processing a class of rules called simple binary rule sets. The data referenced by the rules are stored in secondary memory. A necessary and sufficient condition that a simple binary rule set can be processed in a single pass of a file containing the base relations is given. Because not all simple binary rule sets can be processed in a single pass, a necessary and sufficient condition that a simple binary rule set can be processed by a constant number of passes is also given.

关键词： CONSTANT-PASS PROCESSABLE LINEAR CHAIN RULE ONE-PASS PROCESSABLE recursive query processing SIMPLE BINARY RULE

来源：评论

学校读者我要写书评

暂无评论

CONSTRAINT-BASED query EVALUATION IN DEDUCTIVE DATABASES

引用

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

作者： HAN, JW School of Computing Science Simon Fraser University Burnaby BC Canada

Constraints play an important role in the efficient query evaluation in deductive databases. In this paper, constraint-based query evaluation in deductive databases is investigated, with emphasis on linear recursions with function symbols. Constraints are grouped into three classes: rule constraints integrity constraints, and query constraints. Techniques are developed for the maximal use of different kinds of constraints in rule compilation and query evaluation. Our study on the roles of different classes of constraints in set-oriented evaluation of linear recursions shows the following: 1) Rule constraints should be integrated with their corresponding deduction rules in the compilation of recursions;2) integrity constraints, including finiteness constraints and monotonicity constraints, should be used in the analysis of finite evaluability and termination for specific queries;and 3) query constraints, which are often useful in search space reduction and termination, should be transformed, when necessary, and should be pushed into the compiled chains as deeply as possible for efficient evaluation. Our constraint-based query-processing technique integrates query-independent compilation and chain-based query evaluation methods and demonstrates its great promise in deductive query evaluation.

关键词： DEDUCTIVE DATABASES CONSTRAINT-BASED query EVALUATION COMPILATION TECHNIQUES LINEAR RECURSIONS, FUNCTIONAL RECURSIONS recursive query processing query OPTIMIZATION

来源：评论

学校读者我要写书评

暂无评论

AN EFFICIENT DATABASE TRANSITIVE CLOSURE ALGORITHM

引用

APPLIED INTELLIGENCE 1994年第2期4卷 205-218页

作者： TOROSLU, IH QADAH, GZ HENSCHEN, L AT&T BELL LABS MIDDLETOWNNJ 07748 NORTHWESTERN UNIV DEPT EECSEVANSTONIL 60208

The integration of logic rules and relational databases has recently emerged as an important technique for developing knowledge management systems. An important class of logic rules utilized by these systems is the so-called transitive closure rules, the processing of which requires the computation of the transitive closure of database relations referenced by these rules. This article presents a new algorithm suitable for computing the transitive closure of very large database relations. This algorithm proceeds in two phases. In the first phase, a general graph is condensed into an acyclic one, and at the same time a special sparse matrix is formed from the acyclic graph. The second phase is the main one, in which all the page 1/0 operations are minimized by removing most of the redundant operations that appear in previous algorithms. Using simulation, this article also studies and examines the performance of this algorithm and compares it with the previous algorithms.

关键词： KNOWLEDGE BASES DEDUCTIVE DATABASES recursive RULES recursive query processing TRANSITIVE CLOSURE QUERIES

来源：评论

学校读者我要写书评

暂无评论

EFFICIENT EVALUATION OF MULTIPLE LINEAR-RECURSIONS

引用

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING 1991年第12期17卷 1241-1252页

作者： HAN, JW LING, L School of Computing Science Simon Fraser University Burnaby BC V5A 1S6 Canada

A multiple linear (ML) recursion is a recursion which consists of multiple linear recursive rules and one or more nonrecursive rules. ML recursions can be classified into two classes: side-coherent and non-side-coherent. This paper studies the efficient evaluation of side-coherent ML recursions, which can be further classified into three types: (1) multiple one-sided, (II) multiple balanced k-sided, and (III) multiple mixed k-sided. New techniques are developed by integrating the existing single-linear recursive query evaluation methods with the idea of side-relation unioned processing, which leads to a set of efficient query evaluation algorithms such as a side-relation unioned transitive closure algorithm for the processing of Type I ML recursions, and a generalized side-relation unioned magic sets method for the processing of Types II and III ML recursions. Therefore the evaluation of ML recursions can be mapped to the framework of the evaluation of single linear recursions. Previously developed techniques for the evaluation of single linear recursions, such as the selection of processing strategies for queries with complex instantiations and inquiries, can be applied to the evaluation of ML recursions as well.

关键词： DEDUCTIVE DATABASE LOGIC PROGRAMMING MULTIPLE LINEAR RECURSION query OPTIMIZATION recursive query processing

来源：评论

学校读者我要写书评

暂无评论

EVALUATING recursive QUERIES IN DISTRIBUTED DATABASES

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 1993年第1期5卷 104-121页

作者： NEJDL, W CERI, S WIEDERHOLD, G STANFORD UNIV DEPT COMP SCISTANFORDCA 94305 POLITECN MILAN DIPARTIMENTO ELETTR & INFORMAZI-20133 MILANITALY VIENNA TECH UNIV A-1040 VIENNAAUSTRIA UNIV MODENA I-41100 MODENAITALY

In this paper, we study the execution of logic queries in a distributed database environment. We assume that each local database system can execute logic queries, and we design methods for the efficient execution or queries requiring data from multiple sites. Conventional optimization strategies which are well known in the field of distributed databases, such as the early evaluation of selection conditions and the clustering of processing to manipulate and exchange large sets of tuples, are redefined in view of the additional difficulties due to logic queries, in particular to recursive rules. In order to allow efficient processing of these logic queries we present several program transformation techniques which attempt to minimize distribution costs based on the idea of semi-joins and generalized semi-joins in conventional databases. Although local computation of semi-joins is not possible for the general case, we indicate classes of programs for which these transformations succeed in producing set-oriented computation. We describe processes evaluating the recursive program in a distributed network and develop an efficient method for testing the termination of the computation. Finally, we compare our approach with sequential as well as dataflow-oriented evaluation. Datalog is assumed as logic programming language and paradigm.

关键词： DEDUCTIVE DATABASES DISTRIBUTED DATABASES DISTRIBUTED query processing query OPTIMIZATION recursive query processing SEMI-JOIN

来源：评论

学校读者我要写书评

暂无评论

GENERAL TRANSITIVE CLOSURE OF RELATIONS CONTAINING DUPLICATES

引用

INFORMATION SYSTEMS 1990年第3期15卷 335-347页

作者： EDER, J Institut für Informatik Universität Klagenfurt Universitätsstrasse 65 A-9020 Klagenfurt Austria

General transitive closures are introduced to process recursive structures of data stored in relations. General transitive closures allow a broad range of practical applications to be supported, and yet have the property of being efficiently implementable and easy to use. We extend general transitive closures to relations containing duplicates, so-called multiset-relations, to increase the expressiveness, and because database management systems usually permit the appearance of duplicates in tables. In particular, we show that complicated surrogate generation is no longer necessary for the processing of reconvergent structures. General transitive closures can easily be integrated into the view definition of SQL, requiring a minimum of new concepts and constructs. recursively defined views can be used in queries like other relations. Due to the formal declarative definition of the semantics of general transitive closure, query optimization and reasoning about effective computation can be left with the query processing system.

关键词： relational database SQL recursive query processing multiset-relations algebra of multiset-relations general transitive closure

来源：评论

学校读者我要写书评

暂无评论

A System for Using Wireless Sensor Networks as Globally Deductive Databases

A System for Using Wireless Sensor Networks as Globally Dedu...

引用

4th Annual IEEE International Conference on Wireless and Mobile Computing, Networking and Communications (WIMOB)/SecPriWiMob/SAUCEWiMob/HWN-RMQWiMob/STWiMob

作者： Choochaisri, Supasate Intanagonwiwat, Chalermek Chulalongkorn Univ Dept Comp Engn Bangkok 10330 Thailand

ISBN: (纸本)9780769533933

Several research efforts have abstracted wireless sensor networks as relational databases whose data can be easily queried by users. However, none of these works includes recursive query mechanisms and globally logic reasoning techniques necessary for powerful uses as in deductive databases. In this paper, we propose an approach for abstracting wireless sensor networks as deductive databases that consist of rules, predicates, and logic-based queries. Our approach enables globally logic reasoning and data relating on a query that can be recursive or non-recursive. Additionally, the approach is more convenient to users because the users no longer need to be concerned about local behaviors of each sensor node. We also present LogicQ, an underlying system for disseminating and processing logic-based queries as well as collecting data in an energy-efficient manner. LogicQ uses a data filtering and suppressing technique that directly corresponds to an injected logic-based query for energy savings. Our performance analysis indicates that LogicQ can handle logic-based queries efficiently in terms of completeness and soundness while minimizing the energy consumption.

关键词： Declarative Programming Deductive Database Logic Programming recursive query processing Wireless Sensor Networks

来源：评论

学校读者我要写书评

暂无评论

Compiling general linear recursions by variable connection graph analysis

引用

Computational Intelligence 1989年第1期5卷 12-31页

作者： Han, Jiawei School of Computing Science Simon Fraser University Burnaby British Columbia V5A 1S6 Canada

Compilation is a powerful preprocessing technique in the processing of recursions in knowledge‐based systems. This paper develops a method of compiling and optimizing complex function‐free linear recursions using a variable connection graph, the V‐graph. It shows that a function‐free recursion consisting of a linear recursive rule and one or more nonrecursive rules can be compiled to (1) a bounded recursion, in which recursion can be eliminated from the program, or (2) an n‐chain recursion, whose compiled formula consists of one chain, when n= 1, or n synchronized compiled chains, when n > 1. The study is based on a classification of linear recursions and a study of the compilation results of each class. Using the variable connection graph, linear recursions are classified into six classes: acyclic paths, unit cycles, uniform cycles, nonuniform cycles, connected components, and their disjoint mixtures. Recursions in each class share some common properties in compilation. Our study presents an organized picture for the compilation of general function‐free linear recursions. After compilation, the processing of complex linear recursions becomes essentially the processing of primitive n‐chain recursions or bounded recursions to which efficient processing methods are available. Copyright © 1989, Wiley Blackwell. All rights reserved

关键词： bases de données déductives compilation techniques deductive databases knowledge‐based systems logic programming programmation logique recursive query processing systèmes à base de connaissances techniques de compilation traitement des requětes récursif

来源：评论

学校读者我要写书评

暂无评论

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：