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

Graph Traversal and Top-Down Evaluation of Logic Queries

Journal of Computer Science & Technology 1998年第4期13卷 300-316页

作者：陈阳军 Technical Institute of Changsha Changsha P.R. China

In this paper, an optimal method to handle cyclic and acyclic data relations in the linear recursive queries is proposed. High efficiency is achieved by integrating graph traversal mechanisms into a top-down evaluation. In such a way the subsumption checks and the identification of cyclic data can be done very efficielltly First, based on the subsumption checks, the search space can be reduced drastically by avoiding any redundant expansion operation. In fact, in the case of non-cyclic data, the proposed algorithm requires only linear time for evaluating a linear recursive query. On the other hand, in the case of cyclic data, by using the technique for isolating strongly connected components a lot of answers can be generated directly in terms of the intermediate results and the relevant path information instead of evaluating them by performing algebraic operations. Since the cost of generating an answer is much less than that of evaluating an answer by algebraic operations, the time consumption for cyclic data can be reduced by an order of magnitude or more.

关键词： recursive query top-down evaluation RQA/FQI strategy logic query,graph traversal

来源：评论

学校读者我要写书评

暂无评论

Comparing columnar, row and array DBMSs to process recursive queries on graphs

引用

INFORMATION SYSTEMS 2017年 63卷 66-79页

作者： Ordonez, Carlos Cabrera, Wellington Gurram, Achyuth Univ Houston Dept Comp Sci Houston TX 77204 USA

Analyzing graphs is a fundamental problem in big data analytics, for which DBMS technology does not seem competitive. On the other hand, SQL recursive queries are a fundamental mechanism to analyze graphs in a DBMS, whose processing and optimization are significantly harder than traditional SPJ queries. Columnar DBMSs are a new faster class of database system, with significantly different storage and query processing mechanisms compared to row DBMSs, still the dominating technology. With that motivation in mind, we study the optimization of recursive queries on a columnar DBMS focusing on two fundamental and complementary graph problems: transitive closure and adjacency matrix multiplication. From a query processing perspective we consider the three fundamental relational operators: selection, projection and join (SPJ), where projection subsumes SQL group-by aggregation. We present comprehensive experiments comparing-recursive query processing on columnar, row and array DBMSs to analyze large graphs with different shape and density. We study the relative impact of query optimizations and we compare raw speed of DBMSs to evaluate recursive queries on graphs. Results confirm classical query optimizations that keep working well in a columnar DBMS, but their relative impact is different. Most importantly, a columnar DBMS with tuned query optimization is uniformly faster than row and array systems to analyze large graphs, regardless of their shape, density and connectivity. On the other hand, there is no clear winner between the row and array DBMSs. (C) 2016 Elsevier Ltd. All rights reserved.

关键词： Graph SQL recursive query Matrix Reachability query optimization

来源：评论

学校读者我要写书评

暂无评论

JOIN INDEXES

引用

ACM TRANSACTIONS ON DATABASE SYSTEMS 1987年第2期12卷 218-246页

作者： VALDURIEZ, P Microelectronics and Computer Technology Corporation Austin TX

In new application areas of relational database systems, such as artificial intelligence, the join operator is used more extensively than in conventional applications. In this paper, we propose a simple data structure, called a join index, for improving the performance of joins in the context of complex queries. For most of the joins, updates to join indices incur very little overhead. Some properties of a join index are (i) its efficient use of memory and adaptiveness to parallel execution, (ii) its compatibility with other operations (including select and union), (iii) its support for abstract data type join predicates, (iv) its support for multirelation clustering, and (v) its use in representing directed graphs and in evaluating recursive queries. Finally, the analysis of the join algorithm using join indices shows its excellent performance.

关键词： Abstract data types join multirelation clustering recursive query relational query semijoin updates

来源：评论

学校读者我要写书评

暂无评论

SQL-ASTERISK - A recursive SQL

引用

INFORMATION SYSTEMS 1993年第2期18卷 121-128页

作者： KOYMEN, K CAI, QJ UNICORN SYST CO LOS ANGELESCA 90042

SQL, Structured query Language, supported by most relational database systems since its introduction by IBM in the mid 1970s, has been widely accepted and has enjoyed much popularity because of its declarativeness and the simplicity of its English-like syntax and semantics. SQL satisfied classical database applications which merely involved basic database storage and retrieval operations. However, with the emergence of modem database applications such as CAD and SE databases, we have discovered shortcomings of SQL. A severe problem is the inability of SQL to handle recursion. A relation being defined can not be referenced in conjunction with its own definition. Consequently, a whole class of application problems which require the use of recursion can not be solved with the power of SQL alone. This paper has proposed an enhancement to SQL. The enhanced version is called recursive SQL, or simply SQL*. The paper begins with the examination of the recursion facilities of Datalog, a logic-based language, and then introduces a similar scheme to extend the syntax and semantics of SQL to provide recursive capabilities. The resultant language, SQL*, has been implemented using a bottom-up incremental query evaluation strategy. SQL* makes it possible to express recursive queries as natural as they would be expressed in Datalog or in some other logic-based language. Moreover, SQL* still uses the original SQL-like syntax. Using SQL*, modem database and knowledge-base applications now become feasible.

关键词： SQL recursive query TRANSITIVE CLOSURE DATALOG LOGIC RULES SEMI-NAIVE query EVALUATION INCREMENTAL TUPLES

来源：评论

学校读者我要写书评

暂无评论

A Quantitative Method for Measuring Health of Authoritative Name Servers

引用

INTERNATIONAL JOURNAL OF INFORMATION SECURITY AND PRIVACY 2022年第1期16卷 1-19页

作者： Adiwal, Sanjay Rajendran, Balaji Shetty, Pushparaj D. Ctr Dev Adv Comp Bengaluru India Natl Inst Technol Mangalore Karnataka India

The domain name system (DNS) is regarded as one of the critical infrastructure components of the global internet because a large-scale DNS outage would effectively take a typical user offline. Therefore, the internet community should ensure that critical components of the DNS ecosystemthat is, root name servers, top-level domain registrars and registries, authoritative name servers, and recursive resolvers-function smoothly. To this end, the community should monitor them periodically and provide public alerts about abnormal behavior. The authors propose a novel quantitative approach for evaluating the health of authoritative name servers - a critical, core, and a large component of the DNS ecosystem. The performance is typically measured in terms of response time, reliability, and throughput for most of the internet components. This research work proposes a novel list of parameters specifically for determining the health of authoritative name servers: DNS attack permeability, latency comparison, and DNSSEC validation. The aim is to understand the general behavior of authoritative name servers, detect sluggishness in their performance, and arrive at a score of their health through the aforesaid parameters. The effectiveness of identified parameters is evaluated by devising the corresponding probing algorithms and experimented with them among the authoritative name servers serving the world's top 500 domains. This approach could be used periodically to assess and take necessary measures to protect authoritative domain name servers from abuse.

关键词： DNS DNS Health DNS Security DNS Vulnerabilities DNSSEC Dual-Stack query RTT recursive query Reverse Lookup SOA Zone Transfer

来源：评论

学校读者我要写书评

暂无评论

RaSQL: Greater Power and Performance for Big Data Analytics with recursive-aggregate-SQL on Spark 19

RaSQL: Greater Power and Performance for Big Data Analytics ...

引用

ACM SIGMOD International Conference on Management of Data (SIGMOD)

作者： Gu, Jiaqi Watanabe, Yugo H. Mazza, William A. Shkapsky, Alexander Yang, Mohan Ding, Ling Zaniolo, Carlo Univ Calif Los Angeles Los Angeles CA 90095 USA Univ Naples Federico II Naples Italy Workday Inc Pleasanton CA USA Google LLC Mountain View CA USA

ISBN: (纸本)9781450356435

Thanks to a simple SQL extension, recursive-aggregate-SQL (RaSQL) can express very powerful queries and declarative algorithms, such as classical graph algorithms and data mining algorithms. A novel compiler implementation allows RaSQL to map declarative queries into one basic fixpoint operator supporting aggregates in recursive queries. A fully optimized implementation of this fixpoint operator leads to superior performance, scalability and portability. Thus, our RaSQL system, which extends Spark SQL with the before-mentioned new constructs and implementation techniques, matches and often surpasses the performance of other systems, including Apache Giraph, GraphX and Myria.

关键词： recursive query Aggregates in Recursion Declarative Algorithms in SQL Distributed Computation

来源：评论

学校读者我要写书评

暂无评论

Enhancing recursive graph querying on RDBMS with data clustering approaches 20

Enhancing recursive graph querying on RDBMS with data cluste...

引用

35th Annual ACM Symposium on Applied Computing (SAC)

作者： Scabora, Lucas C. Spadon, Gabriel Oliveira, Paulo H. Rodrigues-Jr, Jose F. Traina-Jr, Caetano Univ Sao Paulo Inst Ciencias Matemat & Comp ICMC Sao Carlos Brazil

ISBN: (纸本)9781450368667

recursive queries are one of the main mechanisms in Relational Database Management Systems to process topology-aware, or graph-like, queries. However, existing works focus only on optimizing the recursive query statements and processing, disregarding the potential physical arrangements that might improve performance. In this work, we propose to use an approach based on adjacent-list storage to physically organize the graph-like data aiming at both reducing the recursive query time and the number of I/O operations. By using Clustered Tables, we tied the adjacency list in chunks for (i) storing both vertex and edge tables together in a Combined Tables approach;and (ii) reordering the edge table with the Edge Clustered Table approach using 20% and 80% of the total adjacency list size. The clustered approaches enabled a faster recursive query processing (up to 22%) and a reduction of up to 61% in the number of page accesses when compared to the Conventional approach. When starting from multiple vertices, the Combined Tables approach achieved a query reduction time of up to 50% in the first join operation, and Edge Clustered Table 20% provided an overall time reduction of up to 20%. The results show that our physical design is effective and allows one to use recursive queries without adaptations.

关键词： recursive query Cluster Tables Adjacency List Storage

来源：评论

学校读者我要写书评

暂无评论

Moving Recursion Out of the RDBMS for Transactional Graph Workloads 11

Moving Recursion Out of the RDBMS for Transactional Graph Wo...

引用

11th IEEE Annual Ubiquitous Computing, Electronics and Mobile Communication Conference (UEMCON)

作者： Reilly, Christine F. Clark, Matthew Skidmore Coll Dept Comp Sci Saratoga Springs NY 12866 USA

ISBN: (纸本)9781728196565

This paper presents work in progress that focuses on querying transactional graph data that is stored in a relational database system (RDBMS). We focus on transactional workloads where there are frequent insert and update operations. Although these types of workloads are common in social network, scientific, and business applications, much of the prior work has focused on graph analytics workloads where there is little to no change to the data over time. We introduce an approach that combines simple database queries with parallel programming, and compare our approach to the recursive SQL operations that are known to have poor performance. Our initial experiments and results provide guidance for the future directions of this project where we will refine the parallel programing approach and structure of the experiment in order to better compare these two approaches.

关键词： relational database recursive query transactional graph database

来源：评论

学校读者我要写书评

暂无评论

SHARq: Sharing recursive Queries in Relational Databases 21

<i>SHARq</i>: Sharing Recursive Queries in Relational Databa...

引用

36th Annual ACM Symposium on Applied Computing (SAC)

作者： Scabora, Lucas C. Spadon, Gabriel Cazzolato, Mirela T. Kaster, Daniel S. Traina, Agma J. M. Rodrigues-, Jose F., Jr. Traina-, Caetano, Jr. Univ Sao Paulo Inst Math & Comp Sci Sao Paulo Brazil Univ Londrina UEL Londrina Parana Brazil

ISBN: (纸本)9781450381048

Processing navigational graph-like queries in relational databases requires executing several recursive join operations, which are computationally costly. However, when the need for graph-like queries arises, applications often execute a sequence of related queries in a single session. We argue that it is possible to reduce the total cost of a set of related queries, by expanding individual intermediate results and sharing them among multiple queries. SHARq is our framework that enables sharing intermediate results of the common graph-like queries Single-Source Shortest Paths (SSSP), Connected Components (CC), and PageRank (PR). Our solution prepares result tables expanded with additional columns to store partial results of graph-like query combinations, such as multiple SSSP, or a sequence of queries comprising SSSP, CC, and PR. Experimental results on 9 datasets show query speedups of up to ten times when combining multiple SSSP queries, and up to two times when combining SSSP, CC, and PR queries. The results reveal a significant reduction in the query time, providing timely results for analyses relying on multiple navigational graph-like queries.

关键词： RDBMS recursive query graph analysis join operation

来源：评论

学校读者我要写书评

暂无评论

RASQL: A Powerful Language and its System for Big Data Applications 20

RASQL: A Powerful Language and its System for Big Data Appli...

引用

ACM SIGMOD International Conference on Management of Data (SIGMOD)

作者： Wang, Jin Xiao, Guorui Gu, Jiaqi Wu, Jiacheng Zaniolo, Carlo Univ Calif Los Angeles Los Angeles CA 90095 USA Tsinghua Univ Beijing Peoples R China

ISBN: (纸本)9781450367356

There is a growing interest in supporting advanced Big Data applications on distributed data processing platforms. Most of these systems support SQL or its dialect as the query interface due to its portability and declarative nature. However, current SQL standard cannot effectively express advanced analytical queries due to its limitation in supporting recursive queries. In this demonstration, we show that this problem can be resolved via a simple SQL extension that delivers greater expressive power by allowing aggregates in recursion. To this end, we propose the recursive-aggregate-SQL (RaSQL) language and its system on top of Apache Spark to express and execute complex queries and declarative algorithms in many applications, such as graph search and machine learning. With a variety of examples, we will (i) show how complicated analytic queries can be expressed with RaSQL;(ii) illustrate formal semantics of the powerful new constructs;and (iii) present a user-friendly interface to interact with the RaSQL system and monitor the query results.

关键词： big data query language recursive query

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：