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

On the complexity of distributed query optimization

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 1996年第4期8卷 650-662页

作者： Wang, CP Chen, MS NATL TAIWAN UNIV DEPT ELECT ENGNTAIPEITAIWAN

While a significant amount of research efforts has been reported on developing algorithms, based on joins and semijoins, to tackle distributed query processing, there is relatively little progress made toward exploring the complexity of the problems studied. As a result, proving NP-hardness of or devising polynomial-time algorithms for certain distributed query optimization problems has been elaborated upon by many researchers. However, due to its inherent difficulty, the complexity of the majority of problems on distributed query optimization remains unknown. In this paper we generally characterize the distributed query optimization problems and provide a frame work to explore their complexity. As it will be shown, most distributed query optimization problems can be transformed into an optimization problem comprising a set of binary decisions, termed Sum Product optimization (SPO) problem. We first prove SPO is NP-hard in light of the NP-completeness of a well-known problem, Knapsack (KNAP). Then, using this result as a basis, we prove that five classes of distributed query optimization problems, which cover the majority of distributed query optimization problems previously studied in the literature, are NP-hard by polynomially reducing SPO to each of them. The detail for each problem transformation is derived. We not only prove the conjecture that many prior studies relied upon, but also provide a frame work for future related studies.

关键词： distributed query optimization semijoin processing complexity NP-hard problems distributed databases

来源：评论

学校读者我要写书评

暂无评论

optimization of decentralized multi-way join queries over pipelined filtering services

引用

COMPUTING 2012年第12期94卷 939-972页

作者： Tsamoura, Efthymia Gounaris, Anastasios Manolopoulos, Yannis Aristotle Univ Thessaloniki GR-54006 Thessaloniki Greece

The capability to optimize and execute complex queries over multiple remote services (e.g., web services) is of high significance for efficient data management in large scale distributed computing infrastructures, such as those enabled by grid and cloud computing technology. In this work, we investigate the optimization of queries that involve multiple data resources, each of which is processed by non-overlapping sets of remote filtering services. The main novelty of this work is the proposal of optimization algorithms that produce an ordering of calls to services so that the query response time is minimized. The distinctive features of our work lie in the consideration of direct, heterogenous links among services and of multiple data resources. To the best of our knowledge, there is no known algorithm for this problem and the evaluation results show that the proposed algorithms can yield significant performance improvements compared to naive approaches.

关键词： distributed query processing distributed query optimization Pipelined filter ordering

来源：评论

学校读者我要写书评

暂无评论

Approximate query answering using data warehouse striping

引用

JOURNAL OF INTELLIGENT INFORMATION SYSTEMS 2002年第2期19卷 145-167页

作者： Bernardino, JR Furtado, PS Madeira, HC Polytech Coimbra ISEC DEIS P-3030601 Coimbra Portugal Univ Coimbra DEI P-3030290 Coimbra Portugal

This paper presents and evaluates a simple but very effective method to implement large data warehouses on an arbitrary number of computers, achieving very high query execution performance and scalability. The data is distributed and processed in a potentially large number of autonomous computers using our technique called data warehouse striping (DWS). The major problem of DWS technique is that it would require a very expensive cluster of computers with fault tolerant capabilities to prevent a fault in a single computer to stop the whole system. In this paper, we propose a radically different approach to deal with the problem of the unavailability of one or more computers in the cluster, allowing the use of DWS with a very large number of inexpensive computers. The proposed approach is based on approximate query answering techniques that make it possible to deliver an approximate answer to the user even when one or more computers in the cluster are not available. The evaluation presented in the paper shows both analytically and experimentally that the approximate results obtained this way have a very small error that can be negligible in most of the cases.

关键词： data warehousing distributed query optimization data partitioning performance optimization approximate query answering

来源：评论

学校读者我要写书评

暂无评论

MIND: An approach to optimize communication time via middleware tuning

引用

INFORMATION SYSTEMS 2019年 82卷 17-32页

作者： Belghoul, Abdeslem Baiou, Mourad Toumani, Farouk Univ Clermont Auvergne CNRS LIMOS Clermont Ferrand France

Minimizing the communication time due to the transfer over a network of the intermediary results produced during the execution of a distributed query is a fundamental problem in distributed database management systems. We take a new look at this problem by investigating the relationship between the communication time and a remote data access middleware. We focus on two middleware parameters that are manually tuned by database administrators or programmers: the fetch size (i.e., the number of tuples that are communicated at once) and the message size (i.e., the size of the buffer at the middleware level). We present an experimental study which shows that these parameters have a crucial impact on the communication time. Then, we propose the MIND framework, which tunes the aforementioned middleware parameters, while adapting to different queries (that may vary in terms of selectivity) and networks (that may vary in terms of bandwidth). The main technical contributions of MIND are (i) a communication time estimation function that takes into account the middleware parameters, the size of the query result and the network environment, and (ii) an iterative optimization algorithm to find the fetch size and the message size that allow a good trade-off between low resource consumption and low communication time. We conclude with an experimental study that emphasizes the effectiveness of the MIND framework. (C) 2018 Elsevier Ltd. All rights reserved.

关键词： Data access middleware distributed query optimization Communication cost model Automatic tuning

来源：评论

学校读者我要写书评

暂无评论

Optimizing cyclic join view maintenance over distributed data sources

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2006年第3期18卷 363-376页

作者： Liu, B Rundensteiner, EA Worcester Polytech Inst Dept Comp Sci Worcester MA 01609 USA

Materialized views defined over distributed data sources are critical for many applications to ensure efficient access, reliable performance, and high availability. Materialized views need to be maintained upon source updates since stale view extents may not serve well or may even mislead user applications. Thus, view maintenance performance is one of the keys to the success of these applications. In this work, we investigate two maintenance strategies, extended batching and view graph transformation, for maintaining general join views where join conditions may exist between any pairs of data sources possibly with cycles. Many choices are available for maintaining cyclic join views. We thus propose a cost-driven view maintenance framework which generates optimized maintenance plans tuned to the environmental settings. The proposed framework has been implemented in the TxnWrap system. Experimental studies illustrate that our proposed optimization techniques significantly improve the view maintenance performance in a distributed environment.

关键词： materialized view maintenance view maintenance optimization distributed query optimization grouping maintenance view graph

来源：评论

学校读者我要写书评

暂无评论

Application on query of distributed Database Based on Improved Genetic Algorithm

Application on query of Distributed Database Based on Improv...

引用

International Conference on Mechatronics Engineering and Computing Technology (ICMECT)

作者： Chen Fuxing Xie Xusheng Jiangxi Normal Univ Coll Comp Informat Engn Nanchang Peoples R China

ISBN: (纸本)9783038351153

The query cost usually as an important criterion for a distributed database. The genetic algorithm is an adaptive probabilistic search algorithm, but the crossover and mutation probability usually keep a probability in traditional genetic algorithm. If the crossover probability keep a large value, the possibility of damage for genetic algorithm model is greater;In turn, if the crossover probability keep a small value, the search process will transform a slow processing or even stagnating. If the mutation probability keep a small value, a new individual can be reproduced difficultly;In turn, if the mutation probability keep a large value, the genetic algorithm will as a Pure random search algorithm. To solve this problem, proposed a improved genetic algorithm that multiple possibility of crossover and mutation based on k-means clustering algorithm. The experiment results indicate that the algorithm is effective.

关键词： distributed database genetic algorithm distributed query optimization k-means clustering algorithm

来源：评论

学校读者我要写书评

暂无评论

Approximate query answering using data warehouse striping 3rd

引用

3rd International Conference on Data Warehousing and Knowledge Discovery (DaWaK 2001)

作者： Bernardino, JR Furtado, PS Madeira, HC Polytech Coimbra ISEC DEIS P-3030601 Coimbra Portugal Univ Coimbra DEI P-3030290 Coimbra Portugal

ISBN: (纸本)3540425535

关键词： data warehousing distributed query optimization data partitioning performance optimization approximate query answering

来源：评论

学校读者我要写书评

暂无评论

Steering query Optimizers: A Practical Take on Big Data Workloads 21

Steering Query Optimizers: A Practical Take on Big Data Work...

引用

ACM SIGMOD International Conference on Management of Data (SIGMOD)

作者： Negi, Parimarjan Interlandi, Matteo Marcus, Ryan Alizadeh, Mohammad Kraska, Tim Friedman, Marc Jindal, Alekh MIT 77 Massachusetts Ave Cambridge MA 02139 USA Microsoft Redmond WA USA Intel Labs Hillsboro OR USA

ISBN: (纸本)9781450383431

In recent years, there has been tremendous interest in research that applies machine learning to database systems. Being one of the most complex components of a DBMS, query optimizers could benefit from adaptive policies that are learned systematically from the data and the query workload. Recent research has brought up novel ideas towards a learned query optimizer, however these ideas have not been evaluated on a commercial query processor or on large scale, real-world workloads. In this paper, we take the approach used by Marcus et al. in Bao and adapt it to SCOPE, a big data system used internally at Microsoft. Along the way, we solve multiple new challenges: we define how optimizer rules affect final query plans by introducing the concept of a rule signature, we devise a pipeline computing interesting rule configurations for recurring jobs, and we define a new learning problem allowing us to apply such interesting rule configurations to previously unseen jobs. We evaluate the efficacy of the approach on production workloads that include 150K daily jobs. Our results show that alternative rule configurations can generate plans with lower costs, and this can translate to runtime latency savings of 7 - 30% on average and up to 90% for a non trivial subset of the workload.

关键词： learning for query optimization distributed query optimization

来源：评论

学校读者我要写书评

暂无评论

On the importance of tuning in incremental view maintenance: An experience case study (extended abstract)

On the importance of tuning in incremental view maintenance:...

引用

2nd International Conference on Data Warehousing and Knowledge Discovery

作者： O'Gorman, K Agrawal, D El Abbadi, A Univ Calif Santa Barbara Dept Comp Sci Santa Barbara CA 93106 USA

ISBN: (纸本)3540679804

We describe the tuning of a gigabyte-scale TPC-D database for investigation of incremental maintenance of a materialized view. We find that incremental maintenance is feasible over a wide range of update sizes (granularities), that intuitive SQL formulations perform poorly, but that there are better alternatives. We show that these results can be meaningfully evaluated and presented only in the context of reasonable instance tuning.

关键词： view maintenance query and update tuning distributed query optimization

来源：评论

学校读者我要写书评

暂无评论

Dirtributed query optimization using PERF joins

Dirtributed query optimization using PERF joins

引用

2000 ACM Symposium on Applied Computing, SAC 2000

作者： Haraty, Ramzi Fany, Roula Lebanese American University P.O. Box 13-5053 Beirut Lebanon

ISBN: (纸本)1581132409

The advent of telecommunication era and the constant development of hardware and network structures have encouraged the decentralization of data while increasing the needs to access information from different sites. query optimization strategies aim to minimize the cost of transferring data across networks. Many techniques and algorithms have been proposed to optimize queries. Perhaps one of the more important algorithms is the AHY algorithm using semi-joins that is implemented by Apers, Hevner and Yao. Nowadays, a new technique called PERF (Partially Encoded Record Filters), presented by Kenneth Ross seems to bring some improvement over semi-joins. PERF joins are two-way semi-joins using a bit vector as their backward phase. Our research encompasses applying PERF joins to the AHY algorithm and producing the AHYPERF algorithm. Programs were designed to implement both the AHY and AHYPERF. Several experiments were conducted and the results showed a very considerable enhancement of AHYPERF over the original AHY. © 2000 ACM.

关键词： distributed query optimization PERF joins Semi joins

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：