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

37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS)

作者： Deep, Shaleen Koutris, Paraschos Univ Wisconsin Madison WI 53706 USA

ISBN: (纸本)9781450347068

Relational queries, and in particular join queries, often generate large output results when executed over a huge dataset. In such cases, it is often infeasible to store the whole materialized output if we plan to reuse it further down a data processing pipeline. Motivated by this problem, we study the construction of space-efficient compressed representations of the output of conjunctive queries, with the goal of supporting the efficient access of the intermediate compressed result for a given access pattern. In particular, we initiate the study of an important tradeoff: minimizing the space necessary to store the compressed result, versus minimizing the answer time and delay for an access request over the result. Our main contribution is a novel parameterized data structure, which can be tuned to trade off space for answer time. The tradeoff allows us to control the space requirement of the data structure precisely, and depends both on the structure of the query and the access pattern. We show how we can use the data structure in conjunction with query decomposition techniques in order to efficiently represent the outputs for several classes of conjunctive queries.

关键词： Query enumeration Compressed representation Space delay tradeoff join algorithms Constant delay enumeration

来源：评论

学校读者我要写书评

暂无评论

What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? 17

What do Shannon-type Inequalities, Submodular Width, and Dis...

引用

36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS)

作者： Khamis, Mahmoud Abo Ngo, Hung Q. Suciu, Dan LogicBlox Inc Atlanta GA 30309 USA Univ Washington Seattle WA 98195 USA

ISBN: (纸本)9781450341981

Recent works on bounding the output size of a conjunctive query with functional dependencies and degree bounds have shown a deep connection between fundamental questions in information theory and database theory. We prove analogous output bounds for disjunctive datalog rules, and answer several open questions regarding the tightness and looseness of these bounds along the way. The bounds are intimately related to Shannon-type information inequalities. We devise the notion of a "proof sequence" of a specific class of Shannon-type information inequalities called "Shannon flow inequalities". We then show how a proof sequence can be used as symbolic instructions to guide an algorithm called PANDA, which answers disjunctive datalog rules within the size bound predicted. We show that PANDA can be used as a black-box to devise algorithms matching precisely the fractional hypertree width and the submodular width runtimes for aggregate and conjunctive queries with functional dependencies and degree bounds. Our results improve upon known results in three ways. First, our bounds and algorithms are for the much more general class of disjunctive datalog rules, of which conjunctive queries are a special case. Second, the runtime of PANDA matches precisely the submodular width bound, while the previous algorithm by Marx has a runtime that is polynomial in this bound. Third, our bounds and algorithms work for queries with input cardinality bounds, functional dependencies, and degree bounds. Overall, our results showed a deep connection between three seemingly unrelated lines of research;and, our results on proof sequences for Shannon flow inequalities might be of independent interest.

关键词： Submodular width Disjunctive datalog Shannon-type inequalities Entropy Functional dependencies Restricted access patterns Degree bounds join algorithms

来源：评论

学校读者我要写书评

暂无评论

Rank join Queries in NoSQL Databases

引用

PROCEEDINGS OF THE VLDB ENDOWMENT 2014年第7期7卷 493-504页

作者： Ntarmos, Nikos Patlakas, Ioannis Triantafillou, Peter Univ Glasgow Sch Comp Sci Glasgow Lanark Scotland Max Planck Inst Informat Saarbrucken Germany

Rank (i.e., top-k) join queries play a key role in modern analytics tasks. However, despite their importance and unlike centralized settings, they have been completely overlooked in cloud NoSQL settings. We attempt to fill this gap: We contribute a suite of solutions and study their performance comprehensively. Baseline solutions are offered using SQL-like languages (like Hive and Pig), based on MapReduce jobs. We first provide solutions that are based on specialized indices, which may themselves be accessed using either MapReduce or coordinator-based strategies. The first index-based solution is based on inverted indices, which are accessed with MapReduce jobs. The second index-based solution adapts a popular centralized rank-join algorithm. We further contribute a novel statistical structure comprising histograms and Bloom filters, which forms the basis for the third index-based solution. We provide (i) MapReduce algorithms showing how to build these indices and statistical structures, (ii) algorithms to allow for online updates to these indices, and (iii) query processing algorithms utilizing them. We implemented all algorithms in Hadoop (HDFS) and HBase and tested them on TPC-H datasets of various scales, utilizing different queries on tables of various sizes and different score-attribute distributions. We ported our implementations to Amazon EC2 and "in-house" lab clusters of various scales. We provide performance results for three metrics: query execution time, network bandwidth consumption, and dollar-cost for query execution.

关键词： Query languages Inverted indices Network bandwidth On line updates Query execution Query execution time Query processing algorithms Rank join algorithms Statistical structures

来源：评论

学校读者我要写书评

暂无评论

Beyond Worst-case Analysis for joins with Minesweeper 14

Beyond Worst-case Analysis for Joins with Minesweeper

引用

33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems

作者： Ngo, Hung Q. Nguyen, Dung T. Re, Christopher Rudra, Atri SUNY Buffalo Buffalo NY 14260 USA

ISBN: (纸本)9781450323758

We describe a new algorithm, Minesweeper, that is able to satisfy stronger runtime guarantees than previous join algorithms (colloquially, 'beyond worst-case guarantees') for data in indexed search trees. Our first contribution is developing a framework to measure this stronger notion of complexity, which we call certificate complexity, that extends notions of Barbay et al. and Demaine et al.;a certificate is a set of propositional formulae that certifies that the output is correct. This notion captures a natural class of join algorithms. In addition, the certificate allows us to define a strictly stronger notion of runtime complexity than traditional worst-case guarantees. Our second contribution is to develop a dichotomy theorem for the certificate-based notion of complexity. Roughly, we show that Minesweeper evaluates beta-acyclic queries in time linear in the certificate plus the output size, while for any beta-cyclic query there is some instance that takes superlinear time in the certificate (and for which the output is no larger than the certificate size). We also extend our certificate-complexity analysis to queries with bounded treewidth and the triangle query. We present empirical results that certificates can be much smaller than the input size, which suggests that ideas in minesweeper might lead to faster algorithms in practice.

关键词： join algorithms Adaptive Algorithm Instance Optimality Certificate Beta-acyclic queries Bounded Treewidth Triangle query

来源：评论

学校读者我要写书评

暂无评论

基于三级存储器的join算法

基于三级存储器的Join算法

引用

第十八届全国数据库学术会议

作者：张冬冬李建中张艳秋哈尔滨工业大学计算机科学与技术学院

1引言在信息量成爆炸性趋势增长的今天,我们需要数据库管理系统能够处理上G、上T、甚至上P级的海量数据。例如,美国NASA发射的人造卫星每年要向地面返回10字节的数据。据估算,我国近年内各类空间遥感系统每天将提供10字节的遥感观测数... 详细信息

1引言在信息量成爆炸性趋势增长的今天,我们需要数据库管理系统能够处理上G、上T、甚至上P级的海量数据。例如,美国NASA发射的人造卫星每年要向地面返回10字节的数据。据估算,我国近年内各类空间遥感系统每天将提供10字节的遥感观测数据。显然,传统

关键词： Massive data Tertiary storage join algorithms

来源：评论

学校读者我要写书评

暂无评论

Authenticated join Processing in Outsourced Databases

Authenticated Join Processing in Outsourced Databases

引用

35th ACM SIGMOD Conference

作者： Yang, Yin Papadias, Dimitris Papadopoulos, Stavros Kalnis, Panos Hong Kong Univ Sci & Technol Dept Comp Sci & Engn Hong Kong Hong Kong Peoples R China

ISBN: (纸本)9781605585543

Database outsourcing requires that a query server constructs a proof of result correctness, which can be verified by the client using the data owner's signature. Previous authentication techniques deal with range queries on a single relation using an authenticated data structure (ADS). On the other hand, authenticated join processing is inherently more complex than ranges since only the base relations (but not their combination) are signed by the owner. In this paper, we present three novel join algorithms depending on the ADS availability: (i) Authenticated Indexed Sort Merge join (AISM), which utilizes a single ADS on the join attribute, (ii) Authenticated Index Merge join (AIM) that requires an ADS (on the join attribute) for both relations, and (iii) Authenticated Sort Merge join (ASM), which does not rely on any ADS. We experimentally demonstrate that the proposed methods outperform two benchmark algorithms, often by several orders of magnitude, on all performance metrics, and effectively shift the workload to the outsourcing service. Finally, we extend our techniques to complex queries that combine multi-way joins with selections and projections.

关键词： Database Outsourcing join algorithms Query Authentication

来源：评论

学校读者我要写书评

暂无评论

RRPJ: Result-rate based progressive relational join

引用

12th International Conference on Database Systems for Advanced Applications

作者： Tok, Wee Hyong Bressan, Stephane Lee, Mong-Li Natl Univ Singapore Sch Comp Singapore 117548 Singapore

ISBN: (纸本)9783540717027

Progressive join algorithms are join algorithms that produce results incrementally as input data is available. Because they are non-blocking, they are particularly suitable for online processing of data streams. Reference algorithms of this family are the symmetric hash join, the X-join and more recently, the rate-based progressive join (RPJ). While the symmetric hash join introduces the idea of a symmetric processing of the input streams but assumes sufficient main memory, the X-join suggests that the processing can scale to very large amounts of data if main memory is regularly flushed to disk, and a reactive/cleanup phase is triggered for disk-resident data. The X-join flushing strategy is based on a simple largest-first strategy, where the largest partition is flushed to disk. The recently proposed RPJ predicts the main memory tuples or partitions that should be flushed to disk in order to maximize throughput by computing their probabilities to contribute to a result. In this paper, we discuss the limitations of RPJ and propose a novel extension, called Result Rate-based Progressive join (RRPJ), which addresses these limitations. Instead of computing the probabilities from statistics over the input data, RRPJ directly observes the output (result) statistics. This not only yields a better performance, but also simplifies the generalization of the algorithm to non-relational data such as multidimensional data and hierarchical data. We empirically show that RRPJ is effective and efficient and outperforms the state-of-art RPJ. We also investigate the relevance and performance of an adaptive version of these algorithms using amortization parameters.

关键词： query processing join algorithms data streams

来源：评论

学校读者我要写书评

暂无评论

Optimizing main-memory join on modern hardware

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2002年第4期14卷 709-730页

作者： Manegold, S Boncz, P Kersten, M CWI NL-1098 SJ Amsterdam Netherlands

In the past decade, the exponential growth in commodity CPU's speed has far outpaced advances in memory latency. A second trend is that CPU performance advances are not only brought by increased clock rate, but also by increasing parallelism inside the CPU. Current database systems have not yet adapted to these trends and show poor utilization of both CPU and memory resources on current hardware. In this paper, we show how these resources can be optimized for large joins and translate these insights into guidelines for future database architectures, encompassing data structures, algorithms, cost modeling, and implementation. In particular, we discuss how vertically fragmented data structures optimize cache performance on sequential data access. On the algorithmic side, we refine the partitioned hash-join with a new partitioning algorithm called radix-cluster, which is specifically designed to optimize memory access. The performance of this algorithm is quantified using a detailed analytical model that incorporates memory access costs in terms of a limited number of parameters, such as cache sizes and miss penalties. We also present a calibration. tool that extracts such parameters automatically from any computer hardware. The accuracy of our models is proven by exhaustive experiments conducted with the Monet database system on three different hardware platforms. Finally, we investigate the effect of implementation techniques that optimize CPU resource usage. Our experiments show that large joins can be accelerated almost an-order of magnitude on modern RISC hardware when both memory and CPU resources are optimized.

关键词： main-memory databases query processing memory access optimization decomposed storage model join algorithms implementation techniques

来源：评论

学校读者我要写书评

暂无评论

Optimizing database architecture for the new bottleneck: memory access

引用

VLDB JOURNAL 2000年第3期9卷 231-246页

作者： Manegold, S Boncz, PA Kersten, ML CWI NL-1098 SJ Amsterdam Netherlands Data Distilleries BV NL-1098 SM Amsterdam Netherlands

In the past decade, advances in the speed of commodity CPUs have far out-paced advances in memory latency. Main-memory access is therefore increasingly a performance bottleneck for many computer applications, including database systems, in this article, we use a simple scan test to show the severe impact of this bottleneck. The insights gained are translated into guidelines for database architecture, in terms of both data structures and algorithms. We discuss how vertically fragmented data structures optimize cache performance on sequential data access. We then focus on equi-join, typically a random-access operation, and introduce radix algorithms for partitioned hash-join. The performance of these algorithms is quantified using a detailed analytical model that incorporates memory access cost. Experiments that validate this model were performed on the Monet database system. We obtained exact statistics on events such as TLB misses and L1 and L2 cache misses by using hardware performance counters found in modern CPUs. Using our cost model, we show how the carefully tuned memory access pattern of our radix algorithms makes them perform well, which is confirmed by experimental results.

关键词： main-memory databases query processing memory access optimization decomposed storage model join algorithms implementation techniques

来源：评论

学校读者我要写书评

暂无评论

Adaptive algorithms for join processing in distributed database systems

引用

DISTRIBUTED AND PARALLEL DATABASES 1997年第3期5卷 233-269页

作者： Scheuermann, P Chong, EI ORACLE CORP NEW ENGLAND R&D CTR NASHUA NH 03062 USA

Distributed query processing algorithms usually perform data reduction by using a semijoin program, but the problem with these approaches is that they still require an explicit join of the reduced relations in the final phase. We introduce an efficient algorithm for join processing in distributed database systems that makes use of bipartite graphs in order to reduce data communication costs and local processing costs. The bipartite graphs represent the tuples that can be joined in two relations taking also into account the reduction state of the relations. This algorithm fully reduces the relations at each site. We then present an adaptive algorithm for response time optimization that takes into account the system configuration, i.e., the additional resources available and the data characteristics, in order to select the best strategy for response time minimization. We also report on the results of a set of experiments which show that our algorithms outperform a number of the recently proposed methods for total processing time and response time minimization.

关键词： distributed query processing join algorithms adaptive algorithms bipartite graphs

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：