Search

GRAPHS ARE, BY nature, 'unifying abstractions' that can leverage interconnectedness to represent, explore, predict, and explain real- and digital-world phenomena. Although real users and consumers of graph instances and graph workloads understand these abstractions, future problems will require new abstractions and systems. What needs to happen in the next decade for big graph processing to continue to succeed? [ABSTRACT FROM AUTHOR]

We present the Succinct Range Filter (SuRF), a fast and compact data structure for approximate membership tests. Unlike traditional Bloom filters, SuRF supports both singlekey lookups and common range queries, such as range counts. SuRF is based on a new data structure called the Fast Succinct Trie (FST) that matches the performance of state-of-the-art order-preserving indexes, while consuming only 10 bits per trie node--a space close to the minimum required by information theory. Our experiments show that SuRF speeds up range queries in a widely used database storage engine by up to 5×. [ABSTRACT FROM AUTHOR]

This article proposes a solution to the existing visual query interface (VQI) setbacks with a plug-and-play method and blending visual query formulation with query processing. While VQIs contribute to the no-code or low-code frameworks necessary to counteract the worldwide developer shortage, talent gap and budgetary constraints they traditionally require high creation and maintenance costs, poor portability, and lack of support for subgraph query formation.

Monitoring and troubleshooting distributed systems are notoriously difficult; potential problems are complex, varied, and unpredictable. The monitoring and diagnosis tools commonly used today—logs, counters, and metrics—have two important limitations: what gets recorded is defined a priori, and the information is recorded in a component- or machine-centric way, making it extremely hard to correlate events that cross these boundaries. This paper presents Pivot Tracing, a monitoring framework for distributed systems that addresses both limitations by combining dynamic instrumentation with a novel relational operator: the happened-before join. Pivot Tracing gives users, at runtime, the ability to define arbitrary metrics at one point of the system, while being able to select, filter, and group by events meaningful at other parts of the system, even when crossing component or machine boundaries. Pivot Tracing does not correlate cross-component events using expensive global aggregations, nor does it perform offline analysis. Instead, Pivot Tracing directly correlates events as they happen by piggybacking metadata alongside requests as they execute. This gives Pivot Tracing low runtime overhead—less than 1% for many cross-component monitoring queries. [ABSTRACT FROM AUTHOR]

Constrained optimization problems are at the heart of significant applications in a broad range of domains, including finance, transportation, manufacturing, and healthcare. Modeling and solving these problems has relied on application-specific solutions, which are often complex, error-prone, and do not generalize. Our goal is to create a domain-independent, declarative approach, supported and powered by the system where the data relevant to these problems typically resides: the database. We present a complete system that supports package queries, a new query model that extends traditional database queries to handle complex constraints and preferences over answer sets, allowing the declarative specification and efficient evaluation of a significant class of constrained optimization problems—integer linear programs (ILP)—within a database. [ABSTRACT FROM AUTHOR]

We propose a generalization of the classical database query optimization problem: multi-objective parametric query (MPQ) optimization. MPQ compares alternative processing plans according to multiple execution cost metrics. It also models missing pieces of information on which plan costs depend upon as parameters. Both features are crucial to model query processing on modern data processing platforms. MPQ generalizes previously proposed query optimization variants, such as multi-objective query optimization, parametric query optimization, and traditional query optimization. We show, however, that the MPQ problem has different properties than prior variants and solving it requires novel methods. We present an algorithm that solves the MPQ problem and finds, for a given query, the set of all relevant query plans. This set contains all plans that realize optimal execution cost tradeoffs for any combination of parameter values. Our algorithm is based on dynamic programming and recursively constructs relevant query plans by combining relevant plans for query parts. We assume that all plan execution cost functions are piecewise-linear in the parameters. We use linear programming to compare alternative plans and to identify plans that are not relevant. We present a complexity analysis of our algorithm and experimentally evaluate its performance. [ABSTRACT FROM AUTHOR]

As data collections become larger and larger, users are faced with increasing bottlenecks in their data analysis. More data means more time to prepare and to load the data into the database before executing the desired queries. Many applications already avoid using database systems, for example, scientific data analysis and social networks, due to the complexity and the increased data-to-query time, that is, the time between getting the data and retrieving its first useful results. For many applications data collections keep growing fast, even on a daily basis, and this data deluge will only increase in the future, where it is expected to have much more data than what we can move or store, let alone analyze. We here present the design and roadmap of a new paradigm in database systems, called NoDB, which do not require data loading while still maintaining the whole feature set of a modern database system. In particular, we show how to make raw data files a first-class citizen, fully integrated with the query engine. Through our design and lessons learned by implementing the NoDB philosophy over a modern Database Management Systems (DBMS), we discuss the fundamental limitations as well as the strong opportunities that such a research path brings. We identify performance bottlenecks specific for in situ processing, namely the repeated parsing and tokenizing overhead and the expensive data type conversion. To address these problems, we introduce an adaptive indexing mechanism that maintains positional information to provide efficient access to raw data files, together with a flexible caching structure. We conclude that NoDB systems are feasible to design and implement over modern DBMS, bringing an unprecedented positive effect in usability and performance. [ABSTRACT FROM AUTHOR]

The article presents CryptDB, a system which enables the use of SQL queries over encrypted data and can provide confidentiality for applications which use database management systems (DBMSes). The authors argues that CryptDB addresses threats from adversaries who gain access to or control of DBMS servers or applications, presenting information on the system architecture. The article examines how CryptDB can perform query processing on encrypted databases, SQL-aware encryption, and computing joins supported by CryptDB.

The article discusses the use of LINQ (Language Integrated Query), a method of integrating data queries into computer programming language. It is noted that the premise of LINQ is very useful, but there are some difficulties associated with its implementation. These are addressed from the perspective of implementers and consumers. The article focuses on the example of building a LINQ provider for a NoSQL data store. It is recommended that each supported operation included be defined in a conventional way, and that a limited LINQ implementation is easier to manage.

The article presents a data analysis platform which is designed to guarantee a screen of privacy between the data being analyzed and the analysis results. It is named Privacy Integrated Queries (PINQ), and gives access to records through a declarative language similar to SQL, working with C# code. PINQ is described as providing a formal and unconditional guarantee of differential privacy when implemented correctly, and its performance in this regard is not dependent on any privacy-related expertise on the part of the data analysts.

The article discusses several Private Information Retrieval (PIR) schemes that contain cryptographic protocols designed to protect database users' privacy of user queries to public databases. According to the article, PIR allows clients to retrieve records from public databases while hiding the records' identity from database owners. PIR computational scheme, also called information theoretic, offers a guarantee that each server participating in protocol execution doesn't receive any information about what users are after. Locally decodable codes and Hadamard codes are discussed.

The article focuses on streaming query engine technology that processes rapidly flowing data with low latency. The author discusses why a streaming query engine is more efficient for data in flight problems than a relational database even though both have similar SQL semantics. Streaming query engines match the time-based nature of the problem, retain only the set of data necessary to solve the problem and process data asynchronously and continuously. Since they share SQL semantics, streaming query engines and relational databases can collaborate.

An introduction is presented in which the author discusses an article published in the journal about the trie-based structure known as Succinct Range Filter (SuRF).

Focuses on the development of database management system (DBMS) technology. Advances in processors and storage devices of computer systems; Underlying concepts and high-level oriented query languages; Traditional record-keeping of DBMS.

The section presents abstracts of research on database systems, from publications of the Association for Computing Machinery. They include "A Relation-Based Language Interpreter for a Content Addressable File Store," "An Implementation Technique for Database Query Languages," "Distributed Deadlock Detection Algorithm" and "Read-Only Transactions in a Distributed Database."

Presents a note on an optimal evaluation of Boolean expressions in an online Query system. Information that Boolean expression is evaluated for each record in the database, it pays to invest some time in a presearching restructuring of the query; Views on the algorithm described for the optimal evaluation of the expressions; Use of a branch and bound algorithms to achieve an optimal evaluation tree.

The relational model of data, the XRM Relational Memory System, and the SEQUEL language have been covered in previous papers and are reviewed. SEQUEL is a relational data sublanguage intended for ad hoc interactive problem solving by non-computer specialists. A version of SEQUEL that has been implemented in a prototype interpreter is described. The Interpreter is designed to minimize the data accessing operations required to respond to an arbitrary query. The optimization algorithms designed for this purpose are described. [ABSTRACT FROM AUTHOR]

The article discusses the computer data management concept of query optimization, and introduces an article in the journal on the subject of parametric and multi-objective query optimization.

In the article, authors say that although Web information is meant to be consumed by human beings, applications that process it automatically are both conceivable and desirable. A useful abstraction for modeling these problems is to view the Web as a collection of, usually small and heterogeneous, databases, and to view programs that extract and process Web data automatically as database applications. WebOQL system, developed at the University of Toronto, is a tool for building the software layer through which such programs can view Web data in a uniform, convenient format and can effectively manipulate it using a declarative query language. In WebOQL, every data source is logically viewed as a graph of trees where every arc in a tree or graph is labeled with a record. The mapping between a data source and this logical view is performed by wrappers dynamically, as queries are executed. WebOQL queries can be embedded in Java programs like SQL queries are embedded in C programs.

The article discusses an article in the issue by Popa, Redfield, Zeldovich, and Balakrishnan on the use of the standard database query language SQL in encrypted databases. The author argues that the article presents a CryptDB system which efficiently would allow the processing of encrypted data without encryption keys. The importance of data encryption in cloud computing is examined.

Several letters to the editor are presented in response to articles in previous issues including "Will Software Engineering Ever Be Engineering?" by Michael Davis in the November 2011 issue, "The World According to LINQ" by Erik Meijer in the October 2011 issue, and a response to a letter to the editor in the November 2011 issue.