bluuebunny/crossref_metadata_2025 huggingface dataset:
A first tutorial on dataspaces
Authors: Franklin Michael , Halevy Alon , Maier David
Published: June 2014

Dataspace systems offer services on data without requiring upfront semantic integration. In sharp contrast with existing information-integration systems, dataspaces systems offer best-effort answers even before semantic mappings are provided to the system. Dataspaces offer a
pay-as-you-go
approach to data management. Users (or administrators) of the system decide where and when it is worthwhile to invest more effort in identifying semantic relationships. As such, dataspaces offer services on the data
in place
, without losing the context surrounding the data.
Systems aspects of probabilistic data management
Authors: Balazinska Magdalena , Ré Christopher , Suciu Dan
Published: June 2014

There has been a wide interest recently in managing probabilistic data [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26]. But in order to follow the rich literature on probabilistic databases one is often required to take a detour into probability theory, correlations, conditionals, Monte Carlo simulations, error bounds, topics that have been studied extensively in several areas of Computer Science and Mathematics. Because of that, it is often difficult to get to the algorithmic and systems level aspects of probabilistic data management. In this tutorial, we will distill these aspects from the, often theory-heavy literature on probabilistic databases. We will start by describing a real application at the University of Washington, using the
RFID Ecosystem
; we will show how probabilities arise naturally, and why we need to cope with them. We will then describe what an implementor needs to know to process SQL queries on probabilistic databases. In the second half of the tutorial, we will discuss more advanced issues, such as event processing over probabilistic streams, and views over probabilistic data.
XML Structural Summaries
Authors: Moro Mirella M. , Vagena Zografoula , Tsotras Vassilis J.
Published: June 2014

This tutorial introduces the concept of
XML Structural Summaries
and describes their role within XML retrieval. It covers the usage of those summaries for Database-style query processing and Information Retrieval-style search tasks in the context of both centralized and distributed environments. Finally, it discusses new retrieval scenarios that can potentially be favorably supported by those summaries.
A benchmark for evaluating moving object indexes
Authors: Chen Su , Jensen Christian S. , Lin Dan
Published: June 2014

Progress in science and engineering relies on the ability to measure, reliably and in detail, pertinent properties of artifacts under design. Progress in the area of database-index design thus relies on empirical studies based on prototype implementations of indexes. This paper proposes a benchmark that targets techniques for the indexing of the current and near-future positions of moving objects. This benchmark enables the comparison of existing and future indexing techniques. It covers important aspects of such indexes that have not previously been covered by any benchmark. Notable aspects covered include update efficiency, query efficiency, concurrency control, and storage requirements. Next, the paper applies the benchmark to half a dozen notable moving-object indexes, thus demonstrating the viability of the benchmark and offering new insight into the performance properties of the indexes.
Mining patterns and rules for software specification discovery
Authors: Lo David , Khoo Siau-Cheng
Published: June 2014

Software specifications are often lacking, incomplete and outdated in the industry. Lack and incomplete specifications cause various software engineering problems. Studies have shown that program comprehension takes up to 45% of software development costs. One of the root causes of the high cost is the lack-of documented specification. Also, outdated and incomplete specification might potentially cause bugs and compatibility issues. In this paper, we describe novel data mining techniques to mine or reverse engineer these specifications from the pool of software engineering data.

A large amount of software data is available for analysis. One form of software data is program execution traces. A program trace can be viewed as a sequence of events collected when a program is run. A set of program traces in turn can be viewed as a sequence database. In this paper, we present some novel work in mining software specifications by employing novel pattern mining and rule mining techniques. Performance studies show the scalability of our technique. Case studies on traces of a real industrial application show the utility of our technique in recovering program specifications from execution traces.
Querying web-based applications under models of uncertainty
Authors: Deutch Daniel , Milo Tova
Published: June 2014

Many businesses offer their services to customers via Web-based application interfaces. Reasoning about execution flows of such applications is extremely valuable for companies. Such reasoning must often operate under terms of uncertainty and partial information, due to partial tracing, effects of unknown external parameters, and more. The objectives of this research are (1) to define models for capturing Web application executions, with partial information and uncertainly of various flavors, (2) to design algorithms that allow for efficient reasoning over applications/execution traces under these models, and (3) to provide practical implementations that exploit these sound theoretical foundations for effective optimization of Web applications. We identify a restricted class of models that capture realistic scenarios, while allowing for an efficient query-based applications analysis. Hardness results indicate the necessity of such restricted models. We describe these results, highlight open problems, and consider directions for future research.
XML-document-filtering automaton
Authors: Silvasti Panu , Sippu Seppo , Soisalon-Soininen Eljas
Published: June 2014

In a publish-subscribe system based on filtering of XML documents subscribers specify their interests with profiles expressed in the XPath language. The system processes a stream of XML documents and delivers to subscribers a notification or content of documents that match the profiles. We present a new XML-document-filtering algorithm that is based on the classic Aho-Corasick pattern-matching automaton. The automaton has a size linear in the sum of the sizes of the filters. We assume that the XML documents all conform to a given DTD; our algorithm utilizes the DTD in the preprocessing phase of the automaton to prune out descendant axes (//) and wildcards (*) from the XPath filters. The XPath subset currently supported consists of linear XPath expressions without predicates. In the case of a 683 MB protein-sequence database, we obtained a throughput of 18.8 MB/sec for 50 000 filters and 17.0 MB/sec for 500 000 filters, using a SAX parser with a throughput of 27 MB/sec.
An object placement advisor for DB2 using solid state storage
Authors: Canim Mustafa , Mihaila George A. , Bhattacharjee Bishwaranjan , Ross Kenneth A. , Lang Christian A.
Published: June 2014

Solid state disks (SSDs) provide much faster random access to data compared to conventional hard disk drives. Therefore, the response time of a database engine could be improved by moving the objects that are frequently accessed in a random fashion to the SSD. Considering the price and limited storage capacity of solid state disks, the database administrator needs to determine which objects (tables, indexes, materialized views, etc.), if placed on the SSD, would most improve the performance of the system. In this paper we propose a tool called "Object Placement Advisor" for making a wise decision for the object placement problem. By collecting profile inputs from workload runs, the advisor utility provides a list of objects to be placed on the SSD by applying heuristics like the greedy knapsack technique or dynamic programming. To show that the proposed approach is effective in conventional database management systems, we have conducted experiments on IBM DB2 with queries and schemas based on the TPC-H and TPC-C benchmarks. The results indicate that using a relatively small amount of SSD storage, the response time of the system can be reduced significantly by considering the recommendation of the advisor.
XPEDIA
Authors: Bhide Manish , Agarwal Manoj K. , Bar-Or Amir , Padmanabhan Sriram , Mittapalli Srinivas K. , Venkatachaliah Girish
Published: June 2014

Data Integration engines increasingly need to provide sophisticated processing options for XML data. In the past, it was adequate for these engines to support basic shredding and XML generation capabilities. However, with the steady growth of XML in applications and databases, integration platforms need to provide more direct operations on XML as well as improve the scalability and efficiency of these operations. In this paper, we describe a robust and comprehensive framework for performing Extract-Transform-Load (ETL) of XML. This includes (i) full computational model and engine capabilities to perform these operations in an ETL flow, (ii) an approach to pushing down XML operations into a database engine capable of supporting XML processing, and (iii) methods to apply partitioning techniques to provide scalable, parallel processing for large XML documents. We describe experimental results showing the effectiveness of these techniques.
XQuery reloaded
Authors: Bamford Roger , Borkar Vinayak , Brantner Matthias , Fischer Peter M. , Florescu Daniela , Graf David , Kossmann Donald , Kraska Tim , Muresan Dan , Nasoi Sorin , Zacharioudakis Markos
Published: June 2014

This paper describes a number of XQuery-related projects. Its goal is to show that XQuery is a useful tool for many different application scenarios. In particular, this paper tries to correct a common myth that XQuery is merely a query language and that SQL is the better query language. Instead, XQuery is a full-fledged programming language for Web applications and services. Furthermore, this paper tries to correct a second myth that XQuery is slow. This paper gives an overview of the state-of-the-art in XQuery implementation and optimization techniques and discusses one particular open-source XQuery processor, Zorba, in more detail. Among others, this paper presents an XQuery Benchmark Service which helps practitioners and XQuery processor vendors to find performance problems in an XQuery processor.
Enhanced subquery optimizations in Oracle
Authors: Bellamkonda Srikanth , Ahmed Rafi , Witkowski Andrew , Amor Angela , Zait Mohamed , Lin Chun-Chieh
Published: June 2014

This paper describes enhanced subquery optimizations in Oracle relational database system. It discusses several techniques -- subquery coalescing, subquery removal using window functions, and view elimination for group-by queries. These techniques recognize and remove redundancies in query structures and convert queries into potentially more optimal forms. The paper also discusses novel parallel execution techniques, which have general applicability and are used to improve the scalability of queries that have undergone some of these transformations. It describes a new variant of antijoin for optimizing subqueries involved in the universal quantifier with columns that may have nulls. It then presents performance results of these optimizations, which show significant execution time improvements.
SQL/MapReduce
Authors: Friedman Eric , Pawlowski Peter , Cieslewicz John
Published: June 2014

A user-defined function (UDF) is a powerful database feature that allows users to customize database functionality. Though useful, present UDFs have numerous limitations, including
install-time
specification of input and output schema and poor ability to parallelize execution. We present a new approach to implementing a UDF, which we call SQL/MapReduce (SQL/MR), that overcomes many of these limitations. We leverage ideas from the MapReduce programming paradigm to provide users with a straightforward API through which they can implement a UDF in the language of their choice. Moreover, our approach allows maximum flexibility as the output schema of the UDF is specified by the function itself at
query plan-time
. This means that a SQL/MR function is polymorphic. It can process arbitrary input because its behavior as well as output schema are dynamically determined by information available at query plan-time, such as the function's input schema and arbitrary user-provided parameters. This also increases reusability as the same SQL/MR function can be used on inputs with many different schemas or with different user-specified parameters.

In this paper we describe the motivation for this new approach to UDFs as well as the implementation within Aster Data Systems'
n
Cluster database. We demonstrate that in the context of massively parallel, shared-nothing database systems, this model of computation facilitates highly scalable computation within the database. We also include examples of new applications that take advantage of this novel UDF framework.
Oracle SecureFiles
Authors: Mukherjee Niloy , Ganesh Amit , Djegaradjane Vinayagam , Muthulingam Sujatha , Zhang Wei , Kunchithapadam Krishna , Lynn Scott , Aleti Bharath , Shergill Kam , Wang Shaoyu
Published: June 2014

Digital unstructured data volumes across enterprise, Internet and multimedia applications are predicted to surpass 6.023x10
23
(Avogadro's number) bits a year in the next fifteen years. This poses tremendous scalability challenges for data management solutions in the coming decades. Filesystems seem to be preferred by data management application designers for providing storage solutions for such unstructured data volumes.

Oracle SecureFiles is emerging as the database solution to break the performance barrier that has kept unstructured content out of database management systems and to provide advanced filesystem functionality, while letting applications fully leverage the strengths of the RDBMS from transactions to partitioning to rollforward recovery. A set of preliminary performance results was presented at the 34th International Conference on Very Large Data Bases (VLDB 2008). It was claimed that SecureFiles would scale maximally as physical storage systems scale up. We legitimize our claims on SecureFiles scalability through this paper, presenting the scalability aspects of SecureFiles through a performance evaluation of I/O bound filesystem like operations on one of the latest high performance cluster of servers and storage.

We are presenting benchmark results that we believe represent a world record database insertion rate for any published result - at over 4.4GB/S using a cluster of seven servers. For 100 byte rows, that represents an insertion rate of 45 billion records a second in relational terms. In terms of unstructured data storage, the scale represents an insertion rate of more than 3.7 million 100 MB high-resolution multimedia videos a day.
AgreementMaker
Authors: Cruz Isabel F. , Antonelli Flavio Palandri , Stroe Cosmin
Published: June 2014

We present the AgreementMaker system for matching real-world schemas and ontologies, which may consist of hundreds or even thousands of concepts. The end users of the system are sophisticated domain experts whose needs have driven the design and implementation of the system: they require a responsive, powerful, and extensible framework to perform, evaluate, and compare matching methods. The system comprises a wide range of matching methods addressing different levels of granularity of the components being matched (conceptual vs. structural), the amount of user intervention that they require (manual vs. automatic), their usage (stand-alone vs. composed), and the types of components to consider (schema only or schema and instances). Performance measurements (recall, precision, and runtime) are supported by the system, along with the weighted combination of the results provided by those methods. The AgreementMaker has been used and tested in practical applications and in the Ontology Alignment Evaluation Initiative (OAEI) competition. We report here on some of its most advanced features, including its extensible architecture that facilitates the integration and performance tuning of a variety of matching methods, its capability to evaluate, compare, and combine matching results, and its user interface with a control panel that drives all the matching methods and evaluation strategies.
Linkage Query Writer
Authors: Hassanzadeh Oktie , Xin Reynold , Miller Renée J. , Kementsietsidis Anastasios , Lim Lipyeow , Wang Min
Published: June 2014

We present Linkage Query Writer (LinQuer), a system for generating SQL queries for semantic link discovery over relational data. The LinQuer framework consists of (a) LinQL, a language for specification of linkage requirements; (b) a web interface and an API for translating LinQL queries to standard SQL queries; (c) an interface that assists users in writing LinQL queries. We discuss the challenges involved in the design and implementation of a declarative and easy to use framework for discovering links between different data items in a single data source or across different data sources. We demonstrate different steps of the linkage requirements specification and discovery process in several real world scenarios and show how the LinQuer system can be used to create high-quality linked data sources.
Mashup by surfing a web of data APIs
Authors: Chen Huajun , Lu Bin , Ni Yuan , Xie Guotong , Zhou Chunying , Mi Jinhua , Wu Zhaohui
Published: June 2014

We present sMash, a system for facilitating users to mashup Web data. The aspects emphasized by the demo are: (1) how to help novice users master data APIs and relationships amongst them easily; (2) how to inspire various users to build more amazing Web data mashups. First, a real-life data API network is constructed and visualized to enable users to surf and mashup. Second, two kinds of recommendations are generated dynamically based on a comprehensive analysis of the network, user's traces and a repository of mashups to provide navigation.
Lahar demonstration
Authors: Letchner Julie , Ré Christopher , Balazinska Magdalena , Philipose Matthai
Published: June 2014

Lahar is a warehousing system for
Markovian streams
---a common class of uncertain data streams produced via inference on probabilistic models. Example Markovian streams include text inferred from speech, location streams inferred from GPS or RFID readings, and human activity streams inferred from sensor data. Lahar supports OLAP-style queries on Markovian stream archives by leveraging novel approximation and indexing techniques that efficiently manipulate stream probabilities.

This demonstration allows users to interactively query a warehouse of imprecise text streams inferred automatically from audio podcasts. Through this interaction, the demo introduces users to the challenges of Markovian stream processing as well as technical contributions developed to address these challenges.
WOLVES
Authors: Sun Peng , Liu Ziyang , Natarajan Sivaramakrishnan , Davidson Susan B. , Chen Yi
Published: June 2014

Workflow views abstract groups of tasks in a workflow into composite tasks, and are used for simplifying provenance analysis, workflow sharing and reuse. An
unsound
view does not preserve the dataflow between tasks in the workflow, and can therefore cause incorrect provenance analysis. In this demo we present WOLVES, a system that efficiently identifies and corrects unsound workflow views with minimal changes (
view correction
). Since the view correction problem is NP-hard, WOLVES allows the user to choose between two forms of local optimality, strong and weak. Efficient time algorithms achieving these optimalities are implemented in WOLVES.
Tolkien
Authors: Satish Arjun , Jain Ramesh , Gupta Amarnath
Published: June 2014

Since the dawn of human civilization, stories have been a popular medium of communication, both synchronously and asynchronously. Technically, a story is a time-ordered coherent sequence of events. In many applications, heterogeneous data is collected and organized so appropriate stories could be told. In this paper, we present a system that helps in generation of stories using a large database of events with associated multimodal data, called eventbase. We define storytelling as a two step process in which a storyteller can retrieve appropriate events and associated data, and then those are further filtered using preferences of the viewer. We develop this model using a measure of interestingness based on attributes of selected events and the preferences. Using an event system developed in our laboratory, we demonstrate the story telling process in Tolkien as one that generates multiple queries to select coherent interesting events to form a story.
PDiffView
Authors: Bao Zhuowei , Cohen-Boulakia Sarah , Davidson Susan B. , Girard Pierrick
Published: June 2014

Scientific workflow systems are becoming increasingly important for managing in-silico experiments. Such experiments are typically specified as directed flow graphs, in which the nodes represent
modules
and edges represent
data flow
between the modules. Each execution (a.k.a. run) of an experiment may vary the parameters and data inputs to the modules in the specification; furthermore, alternative paths of the workflow may be followed. In this process, the scientist's goal is to identify parameter settings and approaches which lead to good final results. Comparing workflow executions of the same specification and understanding the difference between them is thus of paramount importance for understanding the provenance of final results [4].
Answering web questions using structured data
Authors: Pereira Fernando , Rajaraman Anand , Sarawagi Sunita , Tunstall-Pedoe William , Weikum Gerhard , Halevy Alon
Published: June 2014

The question of which role structured data can play in Web search has been raised from the early days of the Web. On the one hand, structured data can be used to answer factual queries. On the other, large amounts of structured data can be used to better organize web-content and therefore to improve search on a wide range of queries.
Database architecture evolution
Authors: Manegold Stefan , Kersten Martin L. , Boncz Peter
Published: June 2014

The holy grail for database architecture research is to find a solution that is
Scalable & Speedy
, to run on anything from small ARM processors up to globally distributed compute clusters,
Stable & Secure
, to service a broad user community,
Small & Simple
, to be comprehensible to a small team of programmers,
Self-managing
, to let it run out-of-the-box without hassle.

In this paper, we provide a trip report on this quest, covering both past experiences, ongoing research on hardware-conscious algorithms, and novel ways towards self-management specifically focused on column store solutions.
Data fusion
Authors: Dong Xin Luna , Naumann Felix
Published: June 2014

The amount of information produced in the world increases by 30% every year and this rate will only go up. With advanced network technology, more and more sources are available either over the Internet or in enterprise intranets. Modern data management applications, such as setting up Web portals, managing enterprise data, managing community data, and sharing scientific data, often require integrating available data sources and providing a uniform interface for users to access data from different sources; such requirements have been driving fruitful research on data integration over the last two decades [11, 13].
Information theory for data management
Authors: Srivastava Divesh , Venkatasubramanian Suresh
Published: June 2014

We are awash in data. The explosion in computing power and computing infrastructure allows us to generate multitudes of data, in differing formats, at different scales, and in inter-related areas. Data management is fundamentally about the harnessing of this data to extract information, discovering good representations of the information, and analyzing information sources to glean structure. Data management generally presents us with cost-benefit tradeoffs. If we store more information, we get better answers to queries, but we pay the price in terms of increased storage. Conversely, reducing the amount of information we store improves performance at the cost of decreased accuracy for query results.
The ability to quantify information gain or loss
can only improve our ability to design good representations, storage mechanisms, and analysis tools for data.
Believe it or not
Authors: Gatterbauer Wolfgang , Balazinska Magdalena , Khoussainova Nodira , Suciu Dan
Published: June 2014

We propose a database model that allows users to annotate data with
belief statements
. Our motivation comes from scientific database applications where a community of users is working together to assemble, revise, and curate a shared data repository. As the community accumulates knowledge and the database content evolves over time, it may contain
conflicting information
and members can
disagree
on the information it should store. For example, Alice may believe that a tuple should be in the database, whereas Bob disagrees. He may also insert the reason why he thinks Alice believes the tuple should be in the database, and explain what he thinks the correct tuple should be instead.

We propose a formal model for
Belief Databases
that interprets users' annotations as belief statements. These annotations can refer both to the base data and to other annotations. We give a formal semantics based on a fragment of multi-agent epistemic logic and define a query language over belief databases. We then prove a key technical result, stating that every belief database can be encoded as a
canonical Kripke structure
. We use this structure to describe a relational representation of belief databases, and give an algorithm for translating queries over the belief database into standard relational queries. Finally, we report early experimental results with our prototype implementation on synthetic data.
Comparing stars
Authors: Zeng Zhiping , Tung Anthony K. H. , Wang Jianyong , Feng Jianhua , Zhou Lizhu
Published: June 2014

Graph data have become ubiquitous and manipulating them based on similarity is essential for many applications. Graph edit distance is one of the most widely accepted measures to determine similarities between graphs and has extensive applications in the fields of pattern recognition, computer vision etc. Unfortunately, the problem of graph edit distance computation is NP-Hard in general. Accordingly, in this paper we introduce three novel methods to compute the upper and lower bounds for the edit distance between two graphs in polynomial time. Applying these methods, two algorithms AppFull and AppSub are introduced to perform different kinds of graph search on graph databases. Comprehensive experimental studies are conducted on both real and synthetic datasets to examine various aspects of the methods for bounding graph edit distance. Result shows that these methods achieve good scalability in terms of both the number of graphs and the size of graphs. The effectiveness of these algorithms also confirms the usefulness of using our bounds in filtering and searching of graphs.
Schema-based independence analysis for XML updates
Authors: Benedikt Michael , Cheney James
Published: June 2014

Query-update independence analysis is the problem of determining whether an update affects the results of a query. Query-update independence is useful for avoiding recomputation of materialized views and may have applications to access control and concurrency control. This paper develops static analysis techniques for query-update independence problems involving core XQuery queries and updates with a snapshot semantics (based on the W3C XQuery Update Facility proposal). Our approach takes advantage of schema information, in contrast to previous work on this problem. We formalize our approach, sketch a proof of correctness, and report on the performance and accuracy of our implementation.
Tagging stream data for rich real-time services
Authors: Nehme Rimma V. , Rundensteiner Elke A. , Bertino Elisa
Published: June 2014

In recent years, data streams have become ubiquitous as technology is improving and the prices of portable devices are falling, e.g., sensor networks, location-based services. Most data streams transmit only data tuples based on which continuous queries are evaluated. In this paper, we propose to enrich data streams with a new type of metadata called
streaming tags
or short
tick-tags
. The fundamental premise of tagging is that users can label data using uncontrolled vocabulary, and these tags can be exploited in a wide variety of applications, such as data exploration, data search, and to produce "enriched" with additional semantics, thus more informative query results. In this paper we focus primarily on the problem of continuous query processing with streaming tags and tagged objects, and address the
tick-tag
semantic issues as well as efficiency concerns. Our main contributions are as follows. First, we specify a general and flexible
Stream Tag Framework
(or short STF) that supports a
stream-centric
approach to tagging, and where
tick-tags
, attached to streaming objects are treated as first-class citizens. Second, under STF, users can query tags
explicitly
as well as
implicitly
by outputting the tags of the base data together with query results. Finally, we have implemented STF in a prototype Data Stream Management System, and through a set of performance experiments, we show that the cost of stream tagging is small and the approach is scalable to a large percentage of tagged objects.
A wavelet transform for efficient consolidation of sensor relations with quality guarantees
Authors: Stern Mirco , Buchmann Erik , Böhm Klemens
Published: June 2014

Answering queries with a low selectivity in wireless sensor networks is a challenging problem. A simple tree-based data collection is communication-intensive and costly in terms of energy. Prior work has addressed the problem by approximating query results based on models of sensor readings. This cuts communication effort if the accuracy requirements are loose, e.g., if the temperature is required within ±0.5°C. For more accuracy, the models need frequent updates, and the communication costs quickly increase. In addition, sophisticated models incur substantial training costs. We propose a query-processing scheme that efficiently consolidates sensor data based on wavelet synopses. The difficulty is that the synopsis has to be constructed incrementally during data collection to ensure efficiency. Our core contribution is to show how to distribute the construction of wavelet synopses in sensor networks. In addition, our approach provides strict error guarantees. We evaluate our distributed wavelet compaction on real-world and on synthetic sensor data. Our solution reduces communication costs by more than a factor of five compared to state-of-the-art approaches. Further, our error guarantees for which efficient data consolidation is possible are better than theirs by more than an order of magnitude.
HAMSTER
Authors: Nandi Arnab , Bernstein Philip A.
Published: June 2014

We address the problem of unsupervised matching of schema information from a large number of data sources into the schema of a data warehouse. The matching process is the first step of a framework to integrate data feeds from third-party data providers into a structured-search engine's data warehouse. Our experiments show that traditional schema-based and instance-based schema matching methods fall short. We propose a new technique based on the search engine's clicklogs. Two schema elements are matched if the distribution of keyword queries that cause click-throughs on their instances are similar. We present experiments on large commercial datasets that show the new technique has much better accuracy than traditional techniques.
Cooperative update exchange in the Youtopia system
Authors: Kot Łucja , Koch Christoph
Published: June 2014

Youtopia is a platform for collaborative management and integration of relational data. At the heart of Youtopia is an update exchange abstraction: changes to the data propagate through the system to satisfy user-specified mappings. We present a novel change propagation model that combines a deterministic chase with human intervention. The process is fundamentally cooperative and gives users significant control over how mappings are repaired. An additional advantage of our model is that mapping cycles can be permitted without compromising correctness.

We investigate potential harmful interference between updates in our model; we introduce two appropriate notions of serializability that avoid such interference if enforced. The first is very general and related to classical final-state serializability; the second is more restrictive but highly practical and related to conflict-serializability. We present an algorithm to enforce the latter notion. Our algorithm is an optimistic one, and as such may sometimes require updates to be aborted. We develop techniques for reducing the number of aborts and we test these experimentally.
Thread cooperation in multicore architectures for frequency counting over multiple data streams
Authors: Das Sudipto , Antony Shyam , Agrawal Divyakant , El Abbadi Amr
Published: June 2014

Many real-world data stream analysis applications such as
network monitoring, click stream analysis
, and others require combining multiple streams of data arriving from multiple sources. This is referred to as
multi-stream analysis
. To deal with high stream arrival rates, it is desirable that such systems be capable of supporting very high processing throughput. The advent of multicore processors and powerful servers driven by these processors calls for efficient parallel designs that can effectively utilize the parallelism of the multicores, since performance improvement is possible only through effective parallelism. In this paper, we address the problem of parallelizing
multi-stream analysis
in the context of multicore processors. Specifically, we concentrate on parallelizing frequent elements, top-
k
, and frequency counting over multiple streams. We discuss the challenges in designing an efficient parallel system for multi-stream processing. Our evaluation and analysis reveals that traditional "contention" based locking results in excessive overhead and wait, which in turn leads to severe performance degradation in modern multicore architectures. Based on our analysis, we propose a "cooperation" based locking paradigm for efficient parallelization of frequency counting. The proposed "cooperation" based paradigm removes waits associated with synchronization, and allows replacing locks by much cheaper atomic synchronization primitives. Our implementation of the proposed paradigm to parallelize a well known frequency counting algorithm shows the benefits of the proposed "cooperation" based locking paradigm when compared to the traditional "contention" based locking paradigm. In our experiments, the proposed "cooperation" based design outperforms the traditional "contention" based design by a factor of 2--5.5X for synthetic zipfian data sets.
Streams on wires
Authors: Mueller Rene , Teubner Jens , Alonso Gustavo
Published: June 2014

Taking advantage of many-core, heterogeneous hardware for data processing tasks is a difficult problem. In this paper, we consider the use of FPGAs for data stream processing as coprocessors in many-core architectures. We present
Glacier
, a component library and compositional compiler that transforms continuous queries into logic circuits by composing library components on an operator-level basis. In the paper we consider selection, aggregation, grouping, as well as windowing operators, and discuss their design as modular elements.

We also show how significant performance improvements can be achieved by inserting the FPGA into the system's data path (
e.g.
, between the network interface and the host CPU). Our experiments show that queries on the FPGA can process streams at more than one million tuples per second and that they can do this directly from the network, removing much of the overhead of transferring the data to a conventional CPU.
Locking key ranges with unbundled transaction services
Authors: Lomet David , Mokbel Mohamed F.
Published: June 2014

To adapt database technology to new environments like cloud platforms or multi-core hardware, or to try anew to provide an extensible database platform, it is useful to separate transaction services from data management elements that need close physical proximity to data. With "generic" transactional services of concurrency control and recovery in a separate
transactional
component (TC), indexing, cache and disk management, now in a
data
component (DC), can be simplified and tailored more easily to the platform or to a data type extension with a special purpose index. This decomposition requires that details of the DC's management of data be hidden from the TC. Thus, locking and logging need to be "logical", which poses a number of problems. One problem is the handling of locking for ranges of keys. Locks need to be taken at the TC prior to the records and their keys being known to the TC. We describe generic two approaches for dealing with this. (1) Make a "speculative" visit" to the DC to learn key values. (2) Lock a "covering resource" first, then learn and lock key values and ultimately release the covering resource lock. The "table" is the only logical (and hence known to the TC) covering resourse in the traditional locking hierarchy, but using it limits concurrency. Concurrency is improved with the introduction of new partition resources. We show how partitions as covering resources combine high concurrency with low locking overhead. Using partitions is sufficiently effective to consider adapting it for a traditional database kernel.
Efficient rewriting of XPath queries using Query Set Specifications
Authors: Cautis Bogdan , Deutsch Alin , Onose Nicola , Vassalos Vasilis
Published: June 2014

We study the problem of querying XML data sources that accept only a limited set of queries, such as sources accessible by Web services which can implement very large (potentially infinite) families of XPath queries. To compactly specify such families of queries we adopt the Query Set Specifications [14], a formalism close to context-free grammars.

We say that query
Q
is
expressible
by the specification
P
if it is equivalent to some expansion of
P
.
Q
is
supported
by
P
if it has an equivalent rewriting using some finite set of
P
's expansions. We study the complexity of expressibility and support and identify large classes of XPath queries for which there are efficient (PTIME) algorithms. Our study considers both the case in which the XML nodes in the results of the queries lose their original identity and the one in which the source exposes persistent node ids.
Lazy-Adaptive Tree
Authors: Agrawal Devesh , Ganesan Deepak , Sitaraman Ramesh , Diao Yanlei , Singh Shashi
Published: June 2014

Flash memories are in ubiquitous use for storage on sensor nodes, mobile devices, and enterprise servers. However, they present significant challenges in designing tree indexes due to their fundamentally different read and write characteristics in comparison to magnetic disks.

In this paper, we present the Lazy-Adaptive Tree (LA-Tree), a novel index structure that is designed to improve performance by minimizing accesses to flash. The LA-tree has three key features: 1) it amortizes the cost of node reads and writes by performing update operations in a lazy manner using cascaded buffers, 2) it dynamically adapts buffer sizes to workload using an online algorithm, which we prove to be optimal under the cost model for raw NAND flashes, and 3) it optimizes index parameters, memory management, and storage reclamation to address flash constraints. Our performance results on raw NAND flashes show that the LA-Tree achieves 2x to 12x gains over the
best
of alternate schemes across a range of workloads and memory constraints. Initial results on SSDs are also promising, with 3x to 6x gains in most cases.
SIMD-scan
Authors: Willhalm Thomas , Popovici Nicolae , Boshmaf Yazan , Plattner Hasso , Zeier Alexander , Schaffner Jan
Published: June 2014

The availability of huge system memory, even on standard servers, generated a lot of interest in main memory database engines. In data warehouse systems, highly compressed column-oriented data structures are quite prominent. In order to scale with the data volume and the system load, many of these systems are highly distributed with a shared-nothing approach. The fundamental principle of all systems is a full table scan over one or multiple compressed columns. Recent research proposed different techniques to speedup table scans like intelligent compression or using an additional hardware such as graphic cards or FPGAs. In this paper, we show that utilizing the embedded Vector Processing Units (VPUs) found in standard superscalar processors can speed up the performance of mainmemory full table scan by factors. This is achieved without changing the hardware architecture and thereby without additional power consumption. Moreover, as on-chip VPUs directly access the system's RAM, no additional costly copy operations are needed for using the new SIMD-scan approach in standard main memory database engines. Therefore, we propose this scan approach to be used as the standard scan operator for compressed column-oriented main memory storage. We then discuss how well our solution scales with the number of processor cores; consequently, to what degree it can be applied in multi-threaded environments. To verify the feasibility of our approach, we implemented the proposed techniques on a modern Intel multi-core processor using Intel® Streaming SIMD Extensions (Intel® SSE). In addition, we integrated the new SIMD-scan approach into SAP® Netweaver® Business Warehouse Accelerator. We conclude with describing the performance benefits of using our approach for processing and scanning compressed data using VPUs in column-oriented main memory database systems.
Turbo-charging estimate convergence in DBO
Authors: Dobra Alin , Jermaine Chris , Rusu Florin , Xu Fei
Published: June 2014

DBO is a database system that utilizes randomized algorithms to give statistically meaningful estimates for the final answer to a multi-table, disk-based query from start to finish during query execution. However, DBO's "time 'til utility" (or "TTU"; that is, the time until DBO can give a useful estimate) can be overly large, particularly in the case that many database tables are joined in a query, or in the case that a join query includes a very selective predicate on one or more of the tables, or when the data are skewed. In this paper, we describe
Turbo DBO
, which is a prototype database system that can answer multi-table join queries in a scalable fashion, just like DBO. However, Turbo DBO often has a much lower TTU than DBO. The key innovation of Turbo DBO is that it makes use of novel algorithms that look for and remember "partial match" tuples in a randomized fashion. These are tuples that satisfy some of the boolean predicates associated with the query, and can possibly be grown into tuples that actually contribute to the final query result at a later time.
Composable, scalable, and accurate weight summarization of unaggregated data sets
Authors: Cohen Edith , Duffield Nick , Kaplan Haim , Lund Carsten , Thorup Mikkel
Published: June 2014

Many data sets occur as
unaggregated data sets
, where multiple data points are associated with each key. In the
aggregate view
of the data, the
weight
of a key is the sum of the weights of data points associated with the key. Examples are measurements of IP packet header streams, distributed data streams produced by events registered by sensor networks, and Web page or multimedia requests to context distribution servers. We aim to combine sampling and aggregation to provide accurate and efficient summaries of the aggregate view. However, data points are scattered in time or across multiple servers and hence aggregation is subject to resource constraints on the size of summaries that can be stored or transmitted.

We develop a summarization framework for unaggregated data where summarization is a scalable and composable operator, and as such, can be tailored to meet resource constraints. Our summaries support unbiased estimates of the weight of subpopulations of keys specified using arbitrary selection predicates. While we prove that under such scenarios there is no variance optimal scheme, our estimators have the desirable properties that the variance is progressively closer to the minimum possible when applied to a "more" aggregated data set. An extensive evaluation using synthetic and real data sets shows that our summarization framework outperforms all existing schemes for this fundamental problem, even for the special and well-studied case of data streams.
Improving OLTP scalability using speculative lock inheritance
Authors: Johnson Ryan , Pandis Ippokratis , Ailamaki Anastasia
Published: June 2014

Transaction processing workloads provide ample request level concurrency which highly parallel architectures can exploit. However, the resulting heavy utilization of core database services also causes resource contention within the database engine itself and limits scalability. Meanwhile, many database workloads consist of short transactions which access only a few database records each, often with stringent response time requirements. Performance of these short transactions is determined largely by the amount of overhead the database engine imposes for services such as logging, locking, and transaction management.

This paper highlights the negative scalability impact of database locking, an effect which is especially severe for short transactions running on highly concurrent multicore hardware. We propose and evaluate Speculative Lock Inheritance, a technique where hot database locks pass directly from transaction to transaction, bypassing the lock manager bottleneck. We implement SLI in the Shore-MT storage manager and show that lock inheritance fundamentally improves scalability by decoupling the number of simultaneous requests for popular locks from the number of threads in the system, eliminating contention within the lock manager even as core counts continue to increase. We achieve this effect with only minor changes to the lock manager and without changes to consistency or other application-visible effects.
A unified approach to ranking in probabilistic databases
Authors: Li Jian , Saha Barna , Deshpande Amol
Published: June 2014

The dramatic growth in the number of application domains that naturally generate probabilistic, uncertain data has resulted in a need for efficiently supporting complex querying and decision-making over such data. In this paper, we present a unified approach to ranking and top-k query processing in probabilistic databases by viewing it as a multi-criteria optimization problem, and by deriving a set of
features
that capture the key properties of a probabilistic dataset that dictate the ranked result. We contend that a single, specific ranking function may not suffice for probabilistic databases, and we instead propose two
parameterized ranking functions
, called
PRF
ω
and
PRF

e

, that generalize or can approximate many of the previously proposed ranking functions. We present novel
generating functions
-based algorithms for efficiently ranking large datasets according to these ranking functions, even if the datasets exhibit complex correlations modeled using
probabilistic and/xor trees
or
Markov networks
. We further propose that the parameters of the ranking function be learned from user preferences, and we develop an approach to learn those parameters. Finally, we present a comprehensive experimental study that illustrates the effectiveness of our parameterized ranking functions, especially
PRF

e

, at approximating other ranking functions and the scalability of our proposed algorithms for exact or approximate ranking.