Single-photon cameras (SPCs) have emerged as a promising new technology for high-resolution 3D imaging. A single-photon 3D camera determines the round-trip time of a laser pulse by precisely capturing the arrival of individual photons at each camera pixel. Constructing photon-timestamp histograms is a fundamental operation for a single-photon 3D camera. However, in-pixel histogram processing is computationally expensive and requires large amount of memory per pixel. Digitizing and transferring photon timestamps to an off-sensor histogramming module is bandwidth and power hungry. Can we estimate distances without explicitly storing photon counts? Yes-here we present an online approach for distance estimation suitable for resource-constrained settings with limited bandwidth, memory and compute. The two key ingredients of our approach are (a) processing photon streams using race logic, which maintains photon data in the time-delay domain, and (b) constructing count-free equi-depth histograms as opposed to conventional equi-width histograms. Equi-depth histograms are a more succinct representation for "peaky" distributions, such as those obtained by an SPC pixel from a laser pulse reflected by a surface. Our approach uses a binner element that converges on the median (or, more generally, to another $k$k-quantile) of a distribution. We cascade multiple binners to form an equi-depth histogrammer that produces multi-bin histograms. Our evaluation shows that this method can provide at least an order of magnitude reduction in bandwidth and power consumption while maintaining similar distance reconstruction accuracy as conventional histogram-based processing methods.

Users often want to augment and enrich entities in their datasets with relevant information from external data sources. As many external sources are accessible only via keyword-search interfaces, a user usually has to manually formulate a keyword query that extract relevant information for each entity. This approach is challenging as many data sources contain numerous tuples, only a small fraction of which may contain entity-relevant information. Furthermore, different datasets may represent the same information in distinct forms and under different terms (e.g., different data source may use different names to refer to the same person). In such cases, it is difficult to formulate a query that precisely retrieves information relevant to an entity. Current methods for information enrichment mainly rely on lengthy and resource-intensive manual effort to formulate queries to discover relevant information. However, in increasingly many settings, it is important for users to get initial answers quickly and without substantial investment in resources (such as human attention). We propose a progressive approach to discovering entity-relevant information from external sources with minimal expert intervention. It leverages end users' feedback to progressively learn how to retrieve information relevant to each entity in a dataset from external data sources. Our empirical evaluation shows that our approach learns accurate strategies to deliver relevant information quickly.

This panel considers the role of the database research community in addressing humanity's greatest challenges. Are we an innovation engine, tool providers, or are we standing on the side while other research communities take the lead?

Streaming applications from cluster monitoring to algorithmic trading deploy Kleene queries to detect and aggregate event trends. Rich event matching semantics determine how to compose events into trends. The expressive power of state-of-the-art streaming systems remains limited since they do not support many of these semantics. Worse yet, they suffer from long delays and high memory costs because they maintain aggregates at a fine granularity. To overcome these limitations, our Coarse-Grained Event Trend Aggregation (Cogra) approach supports a rich variety of event matching semantics within one system. Better yet, Cogra incrementally maintains aggregates at the coarsest granularity possible for each of these semantics. In this way, Cogra minimizes the number of aggregates -- reducing both time and space complexity. Our experiments demonstrate that Cogra achieves up to six orders of magnitude speed-up and up to seven orders of magnitude memory reduction compared to state-of-the-art approaches.

Streaming systems evaluate massive workloads of event sequence aggregation queries. State-of-the-art approaches suffer from long delays caused by not sharing intermediate results of similar queries and by constructing event sequences prior to their aggregation. To overcome these limitations, our Shared Online Event Sequence Aggregation (Sharon) approach shares intermediate aggregates among multiple queries while avoiding the expensive construction of event sequences. Our Sharon optimizer faces two challenges. One, a sharing decision is not always beneficial. Two, a sharing decision may exclude other sharing opportunities. To guide our Sharon optimizer, we compactly encode sharing candidates, their benefits, and conflicts among candidates into the Sharon graph. Based on the graph, we map our problem of finding an optimal sharing plan to the Maximum Weight Independent Set (MWIS) problem. We then use the guaranteed weight of a greedy algorithm for the MWIS problem to prune the search of our sharing plan finder without sacrificing its optimality. The Sharon optimizer is shown to produce sharing plans that achieve up to an 18-fold speed-up compared to state-of-the-art approaches.

Streaming applications from algorithmic trading to traffic management deploy Kleene patterns to detect and aggregate arbitrarily-long event sequences, called event trends. State-of-the-art systems process such queries in two steps. Namely, they first construct all trends and then aggregate them. Due to the exponential costs of trend construction, this two-step approach suffers from both a long delays and high memory costs. To overcome these limitations, we propose the Graph-based Real-time Event Trend Aggregation (GRETA) approach that dynamically computes event trend aggregation without first constructing these trends. We define the GRETA graph to compactly encode all trends. Our GRETA runtime incrementally maintains the graph, while dynamically propagating aggregates along its edges. Based on the graph, the final aggregate is incrementally updated and instantaneously returned at the end of each query window. Our GRETA runtime represents a win-win solution, reducing both the time complexity from exponential to quadratic and the space complexity from exponential to linear in the number of events. Our experiments demonstrate that GRETA achieves up to four orders of magnitude speed-up and up to 50--fold memory reduction compared to the state-of-the-art two-step approaches.

Distributed consistency is perhaps the most-discussed topic in distributed systems today. Coordination protocols can ensure consistency, but in practice they cause undesirable performance unless used judiciously. Scalable distributed architectures avoid coordination whenever possible, but under-coordinated systems can exhibit behavioral anomalies under fault, which are often extremely difficult to debug. This raises significant challenges for distributed system architects and developers. In this article, we present B lazes , a cross-platform program analysis framework that (a) identifies program locations that require coordination to ensure consistent executions, and (b) automatically synthesizes application-specific coordination code that can significantly outperform general-purpose techniques. We present two case studies, one using annotated programs in the Twitter Storm system and another using the Bloom declarative language.

Sensing devices generate tremendous amounts of data each day, which include large quantities of multi-dimensional measurements. These data are expected to be immediately available for real-time analytics as they are streamed into storage. Such scenarios pose challenges to state-of-the-art indexing methods, as they must not only support efficient queries but also frequent updates. We propose here a novel indexing method that ingests multi-dimensional observational data in real time. This method primarily guarantees extremely high throughput for data ingestion, while it can be continuously refined in the background to improve query efficiency. Instead of representing collections of points using Minimal Bounding Boxes as in conventional indexes, we model sets of successive points as line segments in hyperspaces, by exploiting the intrinsic value continuity in observational data. This representation reduces the number of index entries and drastically reduces "over-coverage" by entries. Experimental results show that our approach handles real-world workloads gracefully, providing both low-overhead indexing and excellent query efficiency.

Prior work proposed "Data Near Here" (DNH), a data search engine for scientific archives that is modeled on Internet search engines. DNH performs a periodic, asynchronous scan of each dataset in an archive, extracting lightweight features that are combined to form a dataset summary. During a search, DNH assesses the similarity of the search terms to the summary features and returns to the user, at interactive timescales, a ranked list of datasets for further exploration and analysis. We will demonstrate the search capabilities and ancillary metadata-browsing features for an archive of observational oceanographic data. While comparing search terms to complete datasets might seem ideal, interactive search speed would be impossible with archives of realistic size. We include an analysis showing that our summary-based approach gives a reasonable approximation of such a "complete dataset" similarity measure.

Before scientists can analyze, publish, or share their data, they often need to determine how their datasets are related. Determining relationships helps scientists identify the most complete version of a dataset, detect versions of datasets that complement each other, and determine multiple datasets that overlap. In previous work, we showed how observable relationships between two datasets help scientists recall their original derivation connection. While that work helped with identifying relationships between two datasets, it is infeasible for scientists to use it for finding relationships between all possible pairs in a large collection of datasets. In order to deal with larger numbers of datasets, we are extending our methodology with a relationship-prediction system, ReDiscover, a tool to identify pairs from a collection of datasets that are most likely related and the relationship between them. We report on the initial design of ReDiscover, which uses machine-learning methods such as Conditional Random Fields and Support Vector Machines to the relationship-discovery problem. Our preliminarily evaluation shows that ReDiscover predicted relationships with an average accuracy of 87%.

This paper presents BigDAWG, a reference implementation of a new architecture for "Big Data" applications. Such applications not only call for large-scale analytics, but also for real-time streaming support, smaller analytics at interactive speeds, data visualization, and cross-storage-system queries. Guided by the principle that "one size does not fit all", we build on top of a variety of storage engines, each designed for a specialized use case. To illustrate the promise of this approach, we demonstrate its effectiveness on a hospital application using data from an intensive care unit (ICU). This complex application serves the needs of doctors and researchers and provides real-time support for streams of patient data. It showcases novel approaches for querying across multiple storage engines, data visualization, and scalable real-time analytics.

In this paper, we propose a new approach, called Query from Examples (QFE), to help non-expert database users construct SQL queries. Our approach, which is designed for users who might be unfamiliar with SQL, only requires that the user is able to determine whether a given output table is the result of his or her intended query on a given input database. To kick-start the construction of a target query Q , the user first provides a pair of inputs: a sample database D and an output table R which is the result of Q on D. As there will be many candidate queries that transform D to R , QFE winnows this collection by presenting the user with new database-result pairs that distinguish these candidates. Unlike previous approaches that use synthetic data for such pairs, QFE strives to make these distinguishing pairs as close to the original ( D,R ) pair as possible. By doing so, it seeks to minimize the effort needed by a user to determine if a new database-result pair is consistent with his or her desired query. We demonstrate the effectiveness and efficiency of our approach using real datasets from SQLShare, a cloud-based platform designed to help scientists utilize RDBMS technology for data analysis.

Stream processing addresses the needs of real-time applications. Transaction processing addresses the coordination and safety of short atomic computations. Heretofore, these two modes of operation existed in separate, stove-piped systems. In this work, we attempt to fuse the two computational paradigms in a single system called S-Store. In this way, S-Store can simultaneously accommodate OLTP and streaming applications. We present a simple transaction model for streams that integrates seamlessly with a traditional OLTP system, and provides both ACID and stream-oriented guarantees. We chose to build S-Store as an extension of H-Store - an open-source, in-memory, distributed OLTP database system. By implementing S-Store in this way, we can make use of the transaction processing facilities that H-Store already provides, and we can concentrate on the additional features that are needed to support streaming. Similar implementations could be done using other main-memory OLTP platforms. We show that we can actually achieve higher throughput for streaming workloads in S-Store than an equivalent deployment in H-Store alone. We also show how this can be achieved within H-Store with the addition of a modest amount of new functionality. Furthermore, we compare S-Store to two state-of-the-art streaming systems, Esper and Apache Storm, and show how S-Store can sometimes exceed their performance while at the same time providing stronger correctness guarantees.

The past decade has seen a dramatic increase in the amount of data captured and made available to scientists for research. This increase amplifies the difficulty scientists face in finding the data most relevant to their information needs. In prior work, we hypothesized that Information Retrieval-style ranked search can be applied to data sets to help a scientist discover the most relevant data amongst the thousands of data sets in many formats, much like text-based ranked search helps users make sense of the vast number of Internet documents. To test this hypothesis, we explored the use of ranked search for scientific data using an existing multi-terabyte observational archive as our test-bed. In this paper, we investigate whether the concept of varying relevance, and therefore ranked search, applies to numeric data-that is, are data sets are enough like documents for Information Retrieval techniques and evaluation measures to apply? We present a user study that demonstrates that data set similarity resonates with users as a basis for relevance and, therefore, for ranked search. We evaluate a prototype implementation of ranked search over data sets with a second user study and demonstrate that ranked search improves a scientist's ability to find needed data.

Reducing data movement between desktop analytic systems and server-based data management systems is an important resource-management challenge. The system presented in this paper automatically minimizes data movement in these “hybrid” analytic systems through rewrite-based query-transformation techniques pioneered in relational database query optimization. We evaluate different classes of transformations both in terms of query improvement and optimization time.

Distributed consistency is perhaps the most discussed topic in distributed systems today. Coordination protocols can ensure consistency, but in practice they cause undesirable performance unless used judiciously. Scalable distributed architectures avoid coordination whenever possible, but undercoordinated systems can exhibit behavioral anomalies under fault, which are often extremely difficult to debug. This raises significant challenges for distributed system architects and developers. In this paper we present BLAZES, a cross-platform program analysis framework that (a) identifies program locations that require coordination to ensure consistent executions, and (b) automatically synthesizes application-specific coordination code that can significantly outperform general-purpose techniques. We present two case studies, one using annotated programs in the Twitter Storm system, and another using the Bloom declarative language.

It seems inevitable that the datasets associated with a research project proliferate over time: collaborators may extend datasets with new measurements and new attributes, new experimental runs result in new files with similar structures, and subsets of data are extracted for independent analysis. As these "residual" datasets begin to accrete over time, scientists can lose track of the derivation history that connects them, complicating data sharing, provenance tracking, and scientific reproducibility. In this paper, focusing on data in spreadsheets, we consider how observable relationships between two datasets can help scientists recall their original derivation connection. For instance, if dataset A is wholly contained in dataset B, B may be a more recent version of A and should be preferred when archiving or publishing.

Hybrid data analysis systems integrate an analytic tool and a data management tool. While hybrid systems have benefits, in order to be effective data movement between the two hybrid components must be minimized. Through experimental results we demonstrate that under workloads whose inputs vary in size, shape, and location, automation is the only practical way to manage data movement in hybrid systems.

First-generation streaming systems did not pay much attention to state management via ACID transactions (e.g., [3, 4]). S-Store is a data management system that combines OLTP transactions with stream processing. To create S-Store, we begin with H-Store, a main-memory transaction processing engine, and add primitives to support streaming. This includes triggers and transaction workflows to implement push-based processing, windows to provide a way to bound the computation, and tables with hidden state to implement scoping for proper isolation. This demo explores the benefits of this approach by showing how a naïve implementation of our benchmarks using only H-Store can yield incorrect results. We also show that by exploiting push-based semantics and our implementation of triggers, we can achieve significant improvement in transaction throughput. We demo two modern applications: (i) leaderboard maintenance for a version of "American Idol", and (ii) a city-scale bicycle rental scenario.

Huge amounts of data are being generated by sensing devices every day, recording the status of objects and the environment. Such observational data is widely used in scientific research. As the capabilities of sensors keep improving, the data produced are drastically expanding in precision and quantity, making it a write-intensive domain. Log-structured storage is capable of providing high write throughput, and hence is a natural choice for managing large-scale observational data. In this paper, we propose an approach to indexing and querying observational data in log-structured storage. Based on key traits of observational data, we design a novel index approach called the CR-index (Continuous Range Index), which provides fast query performance without compromising write throughput. It is a lightweight structure that is fast to construct and often small enough to reside in RAM. Our experimental results show that the CR-index is superior in handling observational data compared to other indexing techniques. While our focus is scientific data, we believe our index will be effective for other applications with similar properties, such as process monitoring in manufacturing.

Companies are increasingly moving their data processing to the cloud, for reasons of cost, scalability, and convenience, among others. However, hosting multiple applications and storage systems on the same cloud introduces resource sharing and heterogeneous data processing challenges due to the variety of resource usage patterns employed, the variety of data types stored, and the variety of query interfaces presented by those systems. Furthermore, real clouds are never perfectly symmetric - there often are differences between individual processors in their capabilities and connectivity. In this paper, we introduce a federation framework to manage such heterogeneous clouds. We then use this framework to discuss several challenges and their potential solutions.

Hybrid systems for analyzing big data integrate an analytic tool and a dedicated data-management platform. The necessary movement of data between the components of a hybrid system can lead to performance problems, if that movement is not managed effectively. We present Agrios, a hybrid analytic system for array-structured data, integrating R and SciDB. Agrios minimizes data movement between the two components of the hybrid, using techniques repurposed from relational database query optimization.

In recent years there has been interest in achieving application-level consistency criteria without the latency and availability costs of strongly consistent storage infrastructure. A standard technique is to adopt a vocabulary of commutative operations; this avoids the risk of inconsistency due to message reordering. Another approach was recently captured by the CALM theorem, which proves that logically monotonic programs are guaranteed to be eventually consistent. In logic languages such as Bloom, CALM analysis can automatically verify that programs achieve consistency without coordination.

A facility for merging equivalent data streams can support multiple capabilities in a data stream management system (DSMS), such as query-plan switching and high availability. One can logically view a data stream as a temporal table of events, each associated with a lifetime (time interval) over which the event contributes to output. In many applications, the "same" logical stream may present itself physically in multiple physical forms, for example, due to disorder arising in transmission or from combining multiple sources, and modifications of earlier events. Merging such streams correctly is challenging when the streams may differ physically in timing, order, and composition. This paper introduces a new stream operator called Logical Merge (LMerge) that takes multiple logically consistent streams as input and outputs a single stream that is compatible with all of them. LMerge can handle the dynamic attachment and detachment of input streams. We present a range of algorithms for LMerge that can exploit compile-time stream properties for efficiency. Experiments with Stream Insight, a commercial DSMS, show that LMerge is sometimes orders-of-magnitude more efficient than enforcing determinism on inputs, and that there is benefit to using specialized algorithms when stream variability is limited. We also show that LMerge and its extensions can provide performance benefits in several real-world applications.

Compared to centuries of physics and millennia of mathematics, the 50-year-history of computer science and information management research makes us the toddlers of the scientific community. Yet during our brief existence, we've revolutionized the world and, not content with that, gone on to build and study virtual worlds. We have justly taken pride in our accomplishments, and developed our own unique way of conducting research, unlike other scientific and engineering fields. But cracks have appeared in this edifice we have built. The conference system that served us so well for our first 50 years is falling apart. Our ever-increasing population competes ever more energetically for a finite set of resources. Other scientific and engineering disciplines still think that our field equates to programming, and look down on us. While we may also look down on them, it is undeniably true that high-energy physicists get many more research dollars per capita than we do, and our computer science colleagues wonder whether all the data management problems haven't already been solved. Other departments have started to teach courses that overlap our turf. Are we our own worst enemies? Why doesn't everyone understand how important our research is? Do we have to abandon the conference system? Must we become more like the stodgy old fields of science and engineering? Or can we find our own way?

Current pattern-detection proposals for streaming data recognize the need to move beyond a simple regular-expression model over strictly ordered input. We continue in this direction, relaxing restrictions present in some models, removing the requirement for ordered input, and permitting stream revisions (modification of prior events). Further, recognizing that patterns of interest in modern applications may change frequently over the lifetime of a query, we support updating of a pattern specification without blocking input or restarting the operator. Our new pattern operator (called AFA) is a streaming adaptation of a non-deterministic finite automaton (NFA) where additional schema-based user-defined information, called a register , is accessible to NFA transitions during execution. AFAs support dynamic patterns, where the pattern itself can change over time. We propose clean order-agnostic pattern-detection semantics for AFAs, with new algorithms that allow a very efficient implementation, while retaining significant expressiveness and supporting native handling of out-of-order input, stream revisions, dynamic patterns, and several optimizations. Experiments on Microsoft StreamInsight show that we achieve event rates of more than 200K events/sec (up to 5x better than simpler schemes). Our dynamic patterns give up to orders-of-magnitude better throughput than solutions such as operator restart, and our other optimizations are very effective, incurring low memory and latency.

Applications typically have some local understanding of a database schema, a virtual database that may differ significantly from the actual schema of the data where it is stored. Application engineers often support a virtual database using custom-built middleware because the available solutions, including updatable views, are unable to express necessary capabilities. We propose an alternative means of mapping a virtual database to a physical database that guarantees they remain synchronized under data or schema updates against the virtual schema. One constructs a mapping by composing channel transformations (CTs) that encapsulate atomic transformations --- including complex transformations such as pivoting --- with known updatability properties. Applications, query interfaces, and any other services can behave as if the virtual database is the implemented schema. We describe how CTs translate queries, DML, and DDL, and the properties that are necessary for such translation to be correct. We describe two example CTs in detail, and evaluate an implementation of channels for completeness and performance.

In this demo, we present the Microsoft Complex Event Processing (CEP) Server, Microsoft CEP for short. Microsoft CEP is an event stream processing system featured by its declarative query language and its multiple consistency levels of stream query processing. Query composability, query fusing, and operator sharing are key features in the Microsoft CEP query processor. Moreover, the debugging and supportability tools of Microsoft CEP provide visibility of system internals to users. Web click analysis has been crucial to behavior-based online marketing. Streams of web click events provide a typical workload for a CEP server. Meanwhile, a CEP server with its processing capabilities plays a key role in web click analysis. This demo highlights the features of Microsoft CEP under a workload of web click events.

Multiple researchers have proposed cyclic query plans for evaluating iterative queries over streams or rapidly changing input. The Declarative Networking community uses cyclic plans to evaluate Datalog programs that track reachability and other graph traversals on networks. Cyclic query plans can also evaluate pattern-matching and other queries based on event sequences. An issue with cyclic queries over dynamic inputs is knowing when the query result has progressed to a certain point in the input, since the number of iterations is data dependent. One option is a "strictly staged" computation, where the query plan quiesces between inputs. This option introduces significant latency, and may also "underload" inter-operator buffers. An alternative is to settle for soft guarantees, such as "eventual consistency". Such imprecision can make it difficult, for example, to know when to purge state from stateful operators. We propose a third option in which cyclic queries run continuously, but detect progress "on the fly" by means of a Flying Fixed-Point (FFP) operator. FFP sits on the cyclic loop and circulates speculative predictions on forward progress, which it then validates. FFP is always able to track progress for a class of queries we term strongly convergent . A key advantage of FFP is that it works with existing algebra operators, thereby inheriting their capabilities, such as windowing and dealing with out-of-order input. Also, for stream systems that explicitly model input-event lifetimes, we know exactly which values are in the query result at each point in time. A key implementation decision is the method for speculating. Using the high-water mark of data events minimizes the number of speculative punctuations. Probing operators on the cyclic loop to determine their external progress circulates many more speculative messages, but tracks actual output progress more closely. We show how a hybrid approach limits predictions while coming close the progress-tracking ability of Probing.

In CIDR 2009, we presented a collection of requirements for SciDB, a DBMS that would meet the needs of scientific users. These included a nested-array data model, science-specific operations such as regrid, and support for uncertainty, lineage, and named versions. In this paper, we present an overview of SciDB's key features and outline a demonstration of the first version of SciDB on data and operations from one of our lighthouse users, the Large Synoptic Survey Telescope (LSST).

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.

Many stream-processing systems enforce an order on data streams during query evaluation to help unblock blocking operators and purge state from stateful operators. Such in-order processing (IOP) systems not only must enforce order on input streams, but also require that query operators preserve order. This order-preserving requirement constrains the implementation of stream systems and incurs significant performance penalties, particularly for memory consumption. Especially for high-performance, potentially distributed stream systems, the cost of enforcing order can be prohibitive. We introduce a new architecture for stream systems, out-of-order processing (OOP), that avoids ordering constraints. The OOP architecture frees stream systems from the burden of order maintenance by using explicit stream progress indicators, such as punctuation or heartbeats, to unblock and purge operators. We describe the implementation of OOP stream systems and discuss the benefits of this architecture in depth. For example, the OOP approach has proven useful for smoothing workload bursts caused by expensive end-of-window operations, which can overwhelm internal communication paths in IOP approaches. We have implemented OOP in two stream systems, Gigascope and NiagaraST. Our experimental study shows that the OOP approach can significantly outperform IOP in a number of aspects, including memory, throughput and latency.

To address increasing traffic congestion and its associated consequences, traffic managers are turning to intelligent transportation management. The latte project is extending data stream technology to handle queries that combine live streams with large data archives, motivated by needs in the Intelligent Transportation Systems (ITS) domain. In particular, we focus on queries that combine live data streams with large data archives. We demonstrate such stream-archive queries via the travel-time estimation problem. The demonstration uses the new latte system which has been developed using the NiagaraST stream processing system and the PORTAL transportation data archive.

Many systems and strategies have been proposed for processing nonterminating data streams. Each approach has advantages and disadvantages, including the kinds of queries that can be executed. We present a framework for characterizing the kinds of queries that can be executed over streams based on a notion of compact sets from topology. We first apply our framework to queries over punctuated data streams. Previous work on punctuations focused primarily on the behavior of individual query operators. We use our framework to determine if an entire query can benefit from punctuations available from stream sources. We then consider other common strategies proposed in the literature for executing queries over streams, and we discuss how our framework can characterize the kinds of queries each strategy can answer.

Web applications called mash-ups combine information of varying granularity from different, possibly disparate, sources. We describe Mash-o-matic, a utility that can extract, clean, and combine disparate information fragments, and automatically generate data for mash-ups and the mash-ups themselves. As an illustration, we generate a mash-up that displays a map of a university campus, and outline the potential benefits of using Mash-o-matic. Mash-o-matic exploits superimposed information (SI), which is new information and structure created in reference to fragments of existing information. Mashomatic is implemented using middleware called the Superimposed Pluggable Architecture for Contexts and Excerpts (SPARCE), and a query processor for SI and referenced information, both parts of our infrastructure to support SI management. We present a high-level description of the mash-up production process and discuss in detail how Mash-o-matic accelerates that process.

The most acute information management challenges today stem from organizations relying on a large number of diverse, interrelated data sources, but having no means of managing them in a convenient, integrated, or principled fashion. These challenges arise in enterprise and government data management, digital libraries, "smart" homes and personal information management. We have proposed dataspaces as a data management abstraction for these diverse applications and DataSpace Support Platforms (DSSPs) as systems that should be built to provide the required services over dataspaces. Unlike data integration systems, DSSPs do not require full semantic integration of the sources in order to provide useful services. This paper lays out specific technical challenges to realizing DSSPs and ties them to existing work in our field. We focus on query answering in DSSPs, the DSSP's ability to introspect on its content, and the use of human attention to enhance the semantic relationships in a dataspace.

We demonstrate a Web service and client application for querying and visualizing datasets defined over a topological grid structure. The context for our interest in gridded datasets is CORIE, an environmental observation and forecasting system designed to support scientific and industrial interests in the Columbia River estuary. The CORIE system both measures and simulates the physical properties of the estuary, generating 5GB of data and thousands of data products for each simulation run, including visualizations, aggregated results and derived datasets. In the current production CORIE system, "canned" visualizations are produced eagerly for every run. Users cannot customize their data products nor access the data directly, inhibiting data sharing. The term e-science is used to connote global, distributed collaboration enabled by sharing of both data and compute resources.

A windowed query operator breaks a data stream into possibly overlapping subsets of data and computes a result over each. Many stream systems can evaluate window aggregate queries. However, current stream systems suffer from a lack of an explicit definition of window semantics. As a result, their implementations unnecessarily confuse window definition with physical stream properties. This confusion complicates the stream system, and even worse, can hurt performance both in terms of memory usage and execution time. To address this problem, we propose a framework for defining window semantics, which can be used to express almost all types of windows of which we are aware, and which is easily extensible to other types of windows that may occur in the future. Based on this definition, we explore a one-pass query evaluation strategy, the Window-ID (WID) approach, for various types of window aggregate queries. WID significantly reduces both required memory space and execution time for a large class of window definitions. In addition, WID can leverage punctuations to gracefully handle disorder. Our experimental study shows that WID has better execution-time performance than existing window aggregate query evaluation options that retain and reprocess tuples, and has better latency-accuracy tradeoffs for disordered input streams compared to using a fixed delay for handling disorder.

People often impose new interpretations onto existing information. In the process, they work with information in two layers: a base layer, where the original information resides, and a superimposed layer, where only the new interpretations reside. Abstractions defined in the Superimposed Pluggable Architecture for Contexts and Excerpts (SPARCE) ease communication between the two layers. SPARCE provides three key abstractions for superimposed information management: mark, context, and excerpt. We demonstrate two applications, RIDPad and Schematics Browser, for use in the appeal process of the US Forest Service (USFS).

In our research on superimposed information management, we have developed applications where information elements in the superimposed layer serve to annotate, comment, restructure, and combine selections from one or more existing documents in the base layer. Base documents tend to be unstructured or semi-structured (HTML pages, Excel spreadsheets, and so on) with marks delimiting selections. Selections in the base layer can be programmatically accessed via marks to retrieve content and context. The applications we have built to date allow creation of new marks and new superimposed elements (that use marks), but they have been browse-oriented and tend to expose the line between superimposed and base layers. Here, we present a new access capability, called bilevel queries, that allows an application or user to query over both layers as a whole. Bi-level queries provide an alternative style of data integration where only relevant portions of a base document are mediated (not the whole document) and the superimposed layer can add information not present in the base layer. We discuss our framework for superimposed information management, an initial implementation of a bi-level query system with an XML Query interface, and suggest mechanisms to improve scalability and performance.

As most current query processing architectures are already pipelined, it seems logical to apply them to data streams. However, two classes of query operators are impractical for processing long or infinite data streams. Unbounded stateful operators maintain state with no upper bound in size and, so, run out of memory. Blocking operators read an entire input before emitting a single output and, so, might never produce a result. We believe that a priori knowledge of a data stream can permit the use of such operators in some cases. We discuss a kind of stream semantics called punctuated streams. Punctuations in a stream mark the end of substreams allowing us to view an infinite stream as a mixture of finite streams. We introduce three kinds of invariants to specify the proper behavior of operators in the presence of punctuation. Pass invariants define when results can be passed on. Keep invariants define what must be kept in local state to continue successful operation. Propagation invariants define when punctuation can be passed on. We report on our initial implementation and show a strategy for proving implementations of these invariants are faithful to their relational counterparts.

Applications that process data streams are becoming common. These applications are often queries over streams, so it seems natural to use a database management system instead of a custom application. However, some traditional relational operators are not conducive to stream processing. We propose embedding punctuations into data streams. A punctuation is a predicate that describes a subset of tuples. It informs a stream processor that no tuples exist after that punctuation that satisfy its predicate.

Abstract Digital libraries allow information access to be integrated into work processes rather than separated from them, but also have the potential to overwhelm users with excessive or irrelevant information, impairing their performance rather than improving it. With the opportunity to create new models of what a library is and how it can be used comes the challenge of improving our understanding of its patrons, their work, and the circumstances under which they perform it. In this article we offer an overview of our experiences using observational methods to learn about one class of users, expert clinicians treating patients in hospital settings. We describe the evolution of our understanding of the users and their informational tasks, and how this evolving understanding is guiding our efforts to create digital library technology. The multidisciplinary composition of our team has enriched our observations and improved the validity of our analysis and interpretations. The multiple observation methods we have employed, including “think‐aloud” scenarios in the laboratory, participant observation in the field, key informant interviews, and focus group sessions, have enabled us to enrich the data set, gain greater insight, and verify findings with informants. The relatively tight cycle of observation, analysis, development, and repeat observation has enabled us to iteratively and more rapidly refine our “user model” and “task model,” improving, we hope, the usefulness of the technologies we are developing.

What do you do to make sense of a mass of information on a given topic? Paradoxically, you likely add yet more information to the pile: annotations, underlining, bookmarks, cross-references, etc. We want to build digital information systems for managing such added or superimposed information and support applications that create and manipulate it. We find that requirements for a superimposed information system can be quite different from those for a traditional database management system: a lightweight implementation, multi-model information structures, "schema-later" data entry, interacting with data that is "outside the box" (controlled by other applications), and support, rather than removal, of redundancy. We report on SLIMPad (Superimposed Layer Information Manager scratchPad), a superimposed application which was inspired by the "bundling" of information elements from disparate sources we observed in a medical setting. We propose an architecture for superimposed applications and information management. Our prototype components to implement the architecture give flexibility in structuring superimposed information, and also encapsulate addressing, at a sub-document granularity, into a variety of base information sources.

System R's bottom-up query optimizer architecture forms the basis of most current commercial database managers. The paper compares the performance of top-down and bottom-up optimizers, using the measure of the number of plans generated during optimization. Top down optimizers are superior according to this measure because they can use upper and lower bounds to avoid generating groups of plans. Early during the optimization of a query, a top-down optimizer can derive upper bounds for the costs of the plans it generates. These bounds are not available to typical bottom-up optimizers since such optimizers generate and cost all subplans before considering larger containing plans. These upper bounds can be combined with lower bounds, based solely on logical properties of groups of logically equivalent subqueries, to eliminate entire groups of plans from consideration. We have implemented such a search strategy, in a top-down optimizer called Columbia. Our performance results show that the use of these bounds is quite effective, while preserving the optimality of the resulting plans. In many circumstances this new search strategy is even more effective than heuristics such as considering only left deep plans.

Resolving object references, or reference materialization, is a fundamental operation in object query evaluation. Existing reference materialization techniques fall into two categories: pointer-based and value-based. We identify several drawbacks of existing techniques and propose a hybrid technique that combines the advantages of each category. This technique relaxes the limitations of value-based techniques, while preserving much of their performance advantage over pointer-based techniques; it performs well in those cases where no existing algorithm is applicable or efficient. The hybrid technique shows even stronger performance advantages when moving from single-valued to collection-valued attributes. We present algebraic transformations to enable the hybrid technique in a rule-based query optimizer. Initial experimental results using a commercial object-oriented database show that the hybrid approach achieves significant speedup over current algorithms in many cases. The initial motivation for our work was the optimization and evaluation of object-oriented query languages, particularly OQL. However, the key features we have concentrated on, namely references and collection-valued attributes, are present in object-relational products and the SQL:1999 proposal.

The λ-DB project at the University of Texas at Arlington aims at developing frameworks and prototype systems that address the new query optimization challenges for object-oriented and object-relational databases, such as query nesting, multiple collection types, methods, and arbitrary nesting of collections. We have already developed a theoretical framework for query optimization based on an effective calculus, called the monoid comprehension calculus [4]. The system reported here is a fully operational ODMG 2.0 [2] OODB management system, based on this framework. Our system can handle most ODL declarations and can process most OQL query forms. λ-DB is not ODMG compliant. Instead it supports its own C++ binding that provides a seamless integration between OQL and C++ with low impedance mismatch. It allows C++ variables to be used in queries and results of queries to be passed back to C++ programs. Programs expressed in our C++ binding are compiled by a preprocessor that performs query optimization at compile time, rather than run-time, as it is proposed by ODMG. In addition to compiled queries, λ-DB provides an interpreter that evaluates ad-hoc OQL queries at run-time.

The Relational Model first came into vogue in the early 1980's. It was based on the simplifying idea that all data could be modeled as mathematical relations (tables in "normal form"). Permissible operations on this table data structure were specified by the relation algebra and calculus. The Relational Model led to years of research in areas such as query languages, query optimization, transaction models, and database design methodologies. This research has dominated DBMS conferences for the last fifteen years and has also lead to major products offerings in wide-spread use in the computer industry today.While the Relational revolution was happening in the DBMS community there was a minority opinion emerging from the object community. This minority opinion surfaced in heated debates and panels at DBMS conferences where it was often pitted against "relational purists." The object proponents wanted to discuss storing and retrieving complex objects and relationships in databases while the relational purists insisted on maintaining "mathematical purity and simplicity". These panels were often some of the most acrimonious (and entertaining) at these conferences and many thought there was no way to bridge the chasm between the two schools of thought.However times changes and so do the realities of the commercial world. Object languages such as C++, Smalltalk, and Java have become de facto standards. The Internet and the PC have increased the demand for complex data types. And the relational model is evolving to accommodate these realities.All of the major RDBMS vendors have announced plans for, or are already shipping, Object-Relational DBMS (ORDBMS) products. A natural question for the object community is how well these new products will address the well-known "impedance mismatch" between a pure object model and the relational model. For example, how does one make Java, Smalltalk, or C++ objects persist using an ORDBMS? Can one search for these objects in the database using their methods?The vendors for ORDBMS are claiming well-known OO features in their implementations, such as extensible data types, inheritance, object identity, and object language bindings. This panel will allow the major vendors to explain how those features match up with the kinds of object models that OO developers are accustomed to. The panel will consist of representatives from three of the major ORDBMS vendors as well as a representative of "pure object think". The vendor representatives will each present a brief overview of the object-related features of their products and will explain why OO programmers are going to have an easier time with these ORDBMSs. This will be followed by counterpoint discussion from the pure object thinker.

Query optimizers often limit the search space for join orderings, for example by excluding Cartesian products in subplans or by restricting plan trees to left-deep vines. Such exclusions are widely assumed to reduce optimization effort while minimally affecting plan quality. However, we show that searching the complete space of plans is more affordable than has been previously recognized, and that the common exclusions may be of little benefit.We start by presenting a Cartesian product optimizer that requires at most a few seconds of workstation time to search the space of bushy plans for products of up to 15 relations. Building on this result, we present a join-order optimizer that achieves a similar level of performance, and retains the ability to include Cartesian products in subplans wherever appropriate. The main contribution of the paper is in fully separating join-order enumeration from predicate analysis, and in showing that the former problem in particular can be solved swiftly by novel implementation techniques. A secondary contribution is to initiate a systematic approach to the benchmarking of join-order optimization, which we apply to the evaluation of our method.

No abstract available.

We define a standard of effectiveness for a database calculus relative to a query language. Effectiveness judges suitability to serve as a processing framework for the query language, and comprises aspects of coverage, manipulability and efficient evaluation. We present the monoid calculus, and argue its effectiveness for object-oriented query languages, exemplified by OQL of ODMG-93. The monoid calculus readily captures such features as multiple collection types, aggregations, arbitrary composition of type constructors and nested query expressions. We also show how to extend the monoid calculus to deal with vectors and arrays in more expressive ways than current query languages do, and illustrate how it can handle identity and updates.

This paper addresses problems of data management and interoperability for computational science applications. We recount efforts to design and implement a framework for computational experiment management that encapsulates computationally intensive programs in an object-oriented database. The mechanism we designed and implemented, dubbed "computational proxy", is defined, and a conceptual design for it rendered. We also describe the functional components of the proxy, i.e. the ability to start up and control application invocations and to capture experimental results into the database. We specifically address applications in computational chemistry, but believe our work is applicable to other computational sciences.>

Object-oriented databases (OODBs) are in many ways a better match for scientific data management than conventional record-oriented database systems. User-defined datatypes reduce the encoding going from a scientific domain to the database. Direct support for complex objects is useful for capturing hierarchical structures, such as molecules. OODBs generally have collection types, such as lists and arrays, that are a better basis than sets for the dimensional data common in scientific applications. Their inherent extensibility seems a good match for handling new kinds of metadata, and having behavior definable in the database permits transparent access to existing data in multiple formats via a common object model. We describe our experiences with using BODBs for scientific data, in the domains of computational chemistry, and materials science. We deal with areas that need improvement for OODBs to support scientific applications.>

Scientific applications are infrequent users of commercial database management systems. We feel that a key reason is they do not offer good support for ordered data structures, such as multidimensional arrays, that are needed for natural representation of many scientific data types. In this papers, we lay out issues in database support of ordered structures, consider possible approaches along with their advantages and shortcomings, and direct the reader to the wide variety of prior work outside the data management field that might be successfully applied in this endeavor.

Although obJect-oriented database systems offer advantages over relational or record-oriented database systems, such as modelmg facll]tles for complex objects, they are cnticlzed for poor performance and query capabilities on set-oriented applications The unacceptable performance IS due m part to the ob]ect-at-a-time processing typically used by object-oriented database systems.We believe that improved performance of ob]ectoriented database systems depends partially on the efficient and se[ectxve retrveval of sets of complex objects from secondary storage.In this report, we present the method of complex object retrlevai and assembly used in the Volcano query processing system and the Revelation project.We also present experimental results comparing set-oriented versus obJect-at-a-t]me complex object assembly

Object-oriented database servers are beginning to appear on the commercial market in response to a demand by application developers for increased modeling power in database systems. Before these new servers can enhance the productivity of application designers, systems designers must provide simple interfaces to them from both procedural and object-oriented languages. This paper first describes a successful interface between an object server and two procedural languages (C and Pascal). Because C and Pascal do not support the object-oriented paradigm application, designers using these languages must deal with database objects in less than natural ways. Fortunately, workstations supporting object-oriented languages have the potential for interacting with database objects in a much more integrated manner. To integrate these object-oriented workstations with an object server, we provide a design framework based on the notion of workstation agent objects representing principal objects in the database. We distinguish two types of agents: proxies , which forward most messages to the principal objects, and deputies , which can cache state for their principal and act with more autonomy. The interaction of cache, transaction, and message management strategies makes the implementation of deputies a nontrivial problem. The agent metaphor is being used currently to integrate an object server with a Smalltalk-8O™ workstation.

The tree-locking protocol proposed by Silberschatz and Kedem5guarantees transaction schedules that are both serializable and deadlock-free. The tree-locking protocol assumes the existence of a partial order defined over all of the objects in a database. Requiring all transactions to be tree-locked with respect to this single partial order limits the degree of concurrency obtainable in a database system by increasing the potential for conflict between transactions. In this paper we define a new locking protocol that is derived from the tree-locking protocol, but allows a changing set of partial orders to be defined over the objects in a database. We call this protocol dynamic tree-locking.

QUICKTALK is a dialect of Smalltalk-80 that can be compiled directly into native machine code, instead of virtual machine bytecodes. The dialect includes “hints” on the class of method arguments, instance variables, and class variables. We designed the dialect to describe primitive Smalltalk methods. QUICKTALK achieves improved performance over bytecodes by eliminating the interpreter loop on bytecode execution, by reducing the number of message send/returns via binding some target methods at compilation, and by eliminating redundant class checking. We identify changes to the Smalltalk-80 system and compiler to support the dialect, and give performance measurements.

We describe the results of developing the GemStone object-oriented database server, which supports a model of objects similar to that of Smalltalk-80. We begin with a summary of the goals and requirements for the system: an extensible data model that captures behavioral semantics, no artificial bounds on the number or size of database objects, database amenities (concurrency, transactions, recovery, associative access, authorization) and an interactive development environment. Object-oriented languages, Smalltalk in particular, answer some of these requirements. We discuss satisfying the remaining requirements in an object oriented context, and report briefly on the status of the development efforts. This paper is directed at an audience familiar with object-oriented languages and their implementation, but perhaps unacquainted with the difficulties and techniques of database system development. It updates the original report on the project [CM], and expands upon a more recent article [MDP].

Several methods for implementing database queries expressed as logical rules are given and they are compared for efficiency. One method, called “magic sets,” is a general algorithm for rewriting logical rules so that they may be implemented bottomUP (= forward chaining) in a way that cuts down on the irrelevant facts that are generated. The advantage of this scheme is that by working bottom-up, we can take advantage of efficient methods for doing massive joins. Two other methods are ad hoc ways of implementing “linear” rules, i.e., rules where at most one predicate in any body is recursive. These methods are

Article Free Access Share on Relaxing the universal relation scheme assumption Authors: Jacob Stein View Profile , David Maier View Profile Authors Info & Claims PODS '85: Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systemsMarch 1985 Pages 76–84https://doi.org/10.1145/325405.325415Published:25 March 1985Publication History 7citation83DownloadsMetricsTotal Citations7Total Downloads83Last 12 Months12Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Users of a relational database must explicitly navigate between relations in order to establish a connection among a set of attributes spanning several relation schemes. While a universal scheme interface to a relational database provides users with automatic navigation, it usually imposes on the database a unique role assumption. This assumption requires every attribute name to represent a unique role in the database, so that connections among sets of attributes are unambiguous.

In universal scheme interfaces to relational databases, an attribute name must represent a unique role in the database, so that the connection among a set of attributes is unambiguous. A drawback to this requirement is that several attributes can represent the same underlying class of of entities, but the relationship among those attributes is not captured in the database scheme. As our method for relating attributes uses natural joins, some semantically meaningful.

To overcome limitations in the modeling power of existing database systems and provide a better tool for database application programming, Servio Logic Corporation is developing a computer system to support a set-theoretic data model in an object-oriented programming environment We recount the problems with existing models and database systems We then show how features of Smalltalk, such such as operational semantics, its type hierarchy, entity identity and the merging of programming and data language, solve many of those problems Nest we consider what Smalltalk lacks as a database system secondary storage management, a declarative semantics, concurrency, past states To address these shortcomings, we needed a formal data model We introduce the GemStone data model, and show how it helps to define path expressions, a declarative semantics and object history in the OPAL language We summarize similar approaches, and give a brief overview of the GemStone system implementation

Article Correcting faults in write-once memory Share on Authors: Danny Dolev View Profile , David Maier View Profile , Ilarry Mairson View Profile , Jeffrey Ullman View Profile Authors Info & Claims STOC '84: Proceedings of the sixteenth annual ACM symposium on Theory of computingDecember 1984 Pages 225–229https://doi.org/10.1145/800057.808685Online:01 December 1984Publication History 2citation230DownloadsMetricsTotal Citations2Total Downloads230Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The universal relation model aims at achieving complete access-path independence in relational databases by relieving the user of the need for logical navigation among relations. We clarify the assumptions underlying it and explore the approaches suggested for implementing it. The essential idea of the universal relation model is that access paths are embedded in attribute names. Thus attribute names must play unique “roles.” Furthermore, it assumes that for every set of attributes there is a basic relationship that the user has in mind. The user's queries refer to these basic relationships rather than to the underlying database. Two fundamentally different approaches to the universal relation model have been taken. According to the first approach, the user's view of the database is a universal relation or many universal relations, about which the user poses queries. The second approach sees the model as having query-processing capabilities that relieve the user of the need to specify the logical access path. Thus, while the first approach gives a denotational semantics to query answering, the second approach gives it an operational semantics. We investigate the relationship between these two approaches.

Manifestations of the "universal relation assumption" can be seen either as definitions of a one-relation user view of data, or as algorithms for answering queries about arbitrary sets of attributes. In this paper we explore equivalences between these two points of view. We show that if the user's view is the representative instance, then our ability to answer queries about the universal relation, by applying relational algebra to the actual database, is equivalent to a "boundedness" condition on the dependencies of the database scheme. Further, whenever this condition holds, there is a finite union of lossless tableau mappings that produces the desired relation.

We discuss the philosophy, history and theory of window functions. Window functions (sometimes called connections) are a means to treat a relational database as a semantic whole, rather than as an arbitrary collection of relations. Simply stated, a window function maps a database state and a relation scheme to a relation over the scheme. Window functions are the basis for all existing universal scheme interfaces. We present an assumption inherent in universal scheme interfaces, the unique role assumption.Window functions have evolved along two paths, giving rise to computational definitions and weak instance definitions. We examine several examples of each type of window function, with special attention to the association-object window function of PIQUE. We then look at properties we feel a reasonable window function should satisfy, notably the containment condition and faithfulness. We also define implicit objects, which are relation schemes that a window function treats in a special manner, and which are useful for describing the behavior of window functions.

We develop a theory of relations that are constructed by the union and selection operations from fragment relations. Algorithms for inserting and deleting from relations that are composed of physical fragments are discussed, and we show when such insertions and deletions are meaningful. We also show how to find an access set for a relation, that is, a set of fragments sufficient to produce the relation, and we apply the test to the question of how the fragmentation of relations interacts with a query on the relation, showing that a selection on the relation can be implemented by retrieving a set of physical fragments that forms an access set for another particular relation.

A class of database schemes, called acychc, was recently introduced.It is shown that this class has a number of desirable properties.In particular, several desirable properties that have been studied by other researchers m very different terms are all shown to be eqmvalent to acydicity.In addition, several equivalent charactenzauons of the class m terms of graphs and hypergraphs are given, and a smaple algorithm for determining acychclty is presented.Also given are several eqmvalent characterizations of those sets M of multivalued dependencies such that M is the set of muRlvalued dependencies that are the consequences of a given join dependency.Several characterizations for a conflict-free (in the sense of Lien) set of muluvalued dependencies are provided.

Template dependencies (TD’s) are a class of data dependencies that include multivalued and join dependencies and embedded versions of these. A collection of techniques, examples and results about TD’s are presented. The principal results are: 1) Finite implication (implication over relations with a finite number of tuples) is distinct from unrestricted implication for TD’s. 2) There are, for TD’s over three or more attributes, infinite chains of increasingly weaker and increasingly stronger full TD’s. 3) However, there are weakest (nontrivial) and strongest full TD’s over any given set of attributes. 4) Over two attributes, there are only three distinct TD’s. 5) There is no weakest (not necessarily full) TD over any set of three or more attributes. 6) There is a finite relation that obeys every strictly partial TD but no full TD. 7) The conjunction of each finite set of full TD’s is equivalent to a single full TD. However, the conjunction of a finite set of (not necessarily full) TD’s is not necessarily equivalent to a single TD and the disjunction of a finite set of full TD’s is not necessarily equivalent to a single TD. 8) There is a finite set of TD’s with an infinite Armstrong relation but no finite Armstrong relation. 9) A necessary and sufficient condition for the existence of finite Armstrong relations for sets of TD’s can be formulated in terms of the implication structure of TD’s.

The universal relation concept is intended to provide the database user with a simplified model in which he can compose queries without regard to the underlying structure of the relations in the database. Frequently, the lossless join criterion provides the query interpreter with the clue needed to interpret the query as the user intended. However, some examples exist where interpretation by the lossless-join rule runs contrary to our intuition. To handle some of these cases, we propose a concept called maximal objects , which modifies the universal relation concept in exactly those situations where it appears to go awry—when the underlying relational structure has “cycles.” We offer examples of how the maximal object concept provides intuitively correct interpretations. We also consider how one might construct maximal objects mechanically from purely syntactic structural information—the relation schemes and functional dependencies—about the database.

Although a great deal of research effort has been expended in support of natural language (NL) database querying, little effort has gone to NL database update. One reason for this state of affairs is that in NL querying, one can tie nouns and stative verbs in the query to database objects (relation names, attributes and domain values). In many cases this correspondence seems sufficient to interpret NL queries. NL update seems to require database counterparts for active verbs, such as "hire," "schedule" and "enroll," rather than for stative entities. There seem to be no natural candidates to fill this role.We suggest a database counterpart for active verbs, which we call verbgraphs. The verbgraphs may be used to support NL update. A verbgraph is a structure for representing the various database changes that a given verb might describe. In addition to describing the variants of a verb, they may be used to disambiguate the update command. Other possible uses of verbgraphs include, specification of defaults, prompting of the user to guide but not dictate user interaction and enforcing a variety of types of database integrity constraints.

Article Free Access Share on Using write-once memory for database storage Author: David Maier SUNY at Stony Brook SUNY at Stony BrookView Profile Authors Info & Claims PODS '82: Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systemsMarch 1982 Pages 239–246https://doi.org/10.1145/588111.588151Published:29 March 1982Publication History 18citation283DownloadsMetricsTotal Citations18Total Downloads283Last 12 Months22Last 6 weeks9 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We demonstrate a sense in which the equivalence between blocks (subgraphs without articulation points) and biconnected components (subgraphs in which there are two edge-disjoint paths between any pair of nodes) that holds in ordinary graph theory can be generalized to hypergraphs. The result has an interpretation for relational databases that the universal relations described by acyclic join dependencies are exactly those for which the connections among attributes are defined uniquely. We also exhibit a relationship between the process of Graham reduction [6] of hypergraphs and the process of tableau reduction [1] that holds only for acyclic hypergraphs.

One of the main goals of database systems, relational systems in particular, is to provide a degree of physical data independence for users and programs. Users should not need to know the exact physical storage structures to use the database, and should be protected from changes in those structures. We attempt to go a step further, to logical data independence. We want an interface to a relational database where a user need not be concerned with how the data has been partitioned into various relations. The natural relation schemes to be used, from a semantic point of view, may be decomposed in the database for normalization or redundancy reasons. Our approach essentially loads all the semantics onto the attributes. In our query language tuple variables are not bound to specific relations. Rather, the system uses the set of attributes, say X, that appear in a query with a tuple variable, say t, to combine the database relations to form a single relation with scheme X over which t ranges. We describe our method for constructing such a relation given the associated set of attributes X. When tuple variables are bound implicitly, the logical connectives 'and', 'or', and 'not' take on 'semantic overtones' since they can affect the binding. We discuss the motivation behind the chosen semantics for these connectives. Our goal is a powerful, yet concise, query language with natural semantics.

We propose a universal relation scheme database model based on the assumption that there is a unique connection among any set of attributes in a relational database. We use the notion of object ([Sc],[MU]) to give a database designer the ability to control how connections in the database are to be made. We show how semantic considerations that follow naturally from the unique connection assumption constrain how objects and the underlying base relations must be syntactically related. We illustrate and motivate our definitions and constraints with several simple examples.

The problem of finding a minimum-cost, augmented-set basis is NP-complete. In this paper we show that this problem is not approximable. That is, if ${\text{P}} \ne {\text{NP}}$, then no constants c and d exist so that $A \leqq c{\text{ASB}} + d$, where A is the cost provided by a polynomial-time approximation algorithm and ASB is the optimal cost. We also provide a brief characterization of the cost functions for which this result remains valid. The proof technique used in the augmented-set basis problem is applied directly to other NP-complete problems, such as several graph augmentation and deletion problems, to show that they are also not approximable.

There is a class of database descriptions, involving one “acyclic” join dependency and a collection of functional dependencies, and nothing else, that appears powerful enough to describe most any real-world body of data in relational database terms. Further, this class has many desirable properties. Some properties make operations like updates and the selection of joins to implement a query over a universal relation especially easy. Other properties of interest were studied by other researchers who described the same class in radically different terms, and found desirable properties in their own contexts. It is the purpose of this paper to define the class formally, to give its important properties and the equivalences with the other classes mentioned, and to explain the importance of each property. This paper is intended to summarize the results that will appear in more detail in [FMU] and [BFMY].

It iS shown that testing whether a dependency o is unpiled by a set ~ of functional and join dependencies is NP-hard if o is a join dependency, but it reqmres only O(l u Ill ~ II) time ff o Is either a funcuonal or a multivalued dependency ( j U [ is the number of elements in the set of all the attributes U, and II ~ II as the space required to write down ~).The fact that inferring join dependencies is NP-hard follows from the followmg stronger result.It is proved that if ~ is a set of one jom dependency and several funcuonal dependencies, then testing whether Z implies a join dependency o is NP-complete By combming this result with a recent result of Beeri and Var& ~t can be proved that if 2 is a set of one join dependency and several multivalued dependencies, then testing whether ~ unphes a join dependency o Is NP-hard It is also shown that the problem of deciding whether a JD-rule can be applied to a tableau T and the problem of testing whether a relation r does not obey a join dependency are NP-complete.The first problem is NP-complete even if T can be obtamed from a tableau corresponding to a join dependency by applying some FD-rules.As a result, It follows that deciding whether the join of several relations obtained by projecUon from a umversal instance is not equal to the universal instance is NP-complete.Finally, it is proved that there is no umversal constant n such that for every set of multlvalued dependencies ~ and a join dependency o that is not unpiled by ~, there is a relation with no more than n tuples in which holds but o fails.

Numerous algonthms concernmg relahonal databases use a cover for a set of funcUonal dependencies as all or part of their input Examples are Been and Bernsteln's synthesis algorithm and the tableau modtfication algorithm of Aho et al The performance of these algorahms may depend on both the number of funcuonal dependencies m the cover and the total size of the cover Starting with a smaller cover wdl make such algorithms run faster After Bernstem, many researchers beheve that the problem of finding a minimum cover is NPcomplete It as shown here that minimum covers can be found m polynomial time, using the nouon of dwect determmatwn The proofdetads the structure ofmmtmum covers, refining the structure Bernstem and Been show for nonredundant covers The kernel algorithm of Lewis, Sekino, and TIng is improved using these results

We present a computation method---the chase---for testing implication of data dependencies by a set of data dependencies. The chase operates on tableaux similar to those of Aho, Sagiv, and Ullman. The chase includes previous tableau computation methods as special cases. By interpreting tableaux alternately as mappings or as templates for instances, we can test implication of functional and join dependencies. This information is useful in determining when a relational database scheme accurately represents the information it is intended to. The chase can also be used to test equivalence of database schemes and as part of the test of whether the relation schemes in a database scheme are independent components.

Numerous algorithms concerning relational databases use a cover for a set of functional dependencies as all or part of their input. Examples are Bernstein and Beeri's synthesis algorithm [BB] and the tableau modification algorithm of Aho, Beeri, and Ullman [ABU]. The performance of these algorithms may depend both on the number of functional dependencies in the cover and the total size of the cover. Starting with a smaller cover will make such algorithms run faster. After Bernstein [Be75], many researchers believe the problem of finding a minimum cover is NP-complete. We show that minimum covers can be found in polynomial time, using the notion of direct determination. The proof details the structure of minimum covers, refining the structure Bernstein and Beeri show for non-redundant covers [BB]. The kernel algorithm of Lewis, Sekino, and Ting [LST] is improved using these results.

We present a space efficient method for computing ancestor information in trees, specifically, whether one node is an ancestor of another and the lowest common ancestor of two nodes. We show the method is tunable to specific applications, and compare it to other methods. Finally, we apply our procedures to the problem of finding negative cycles in sparse graphs.

Presented is a computation method—the chase —for testing implication of data dependencies by a set of data dependencies. The chase operates on tableaux similar to those of Aho, Sagiv, and Ullman. The chase includes previous tableau computation methods as special cases. By interpreting tableaux alternately as mappings or as templates for relations, it is possible to test implication of join dependencies (including multivalued dependencies) and functional dependencies by a set of dependencies.

The complexity of finding the Longest Common Subsequence (LCS) and the Shortest Common Supersequence (SCS) of an arbRrary number of sequences IS considered We show that the yes/no version of the LCS problem is NP-complete for sequences over an alphabet of size 2, and that the yes/no SCS problem is NPcomplete for sequences over an alphabet of size 5 KEY WORDS AND PHRASES computational complexity, NP-completeness, longest common subsequence, shortest common supersequence CR CATEGORIES 5 23, 5 39 DefinitionsGiven a finite sequence S = sl, s2, ..., sin, we define a subsequence S' of S to be any sequence which consists of S with between 0 and m terms deleted (e.g.ac, ad, and abcd are all subsequences of abcd).We write S' < S if S' is a subsequence of S. We also say that S is a supersequence of S', and write S > S'.Given a set R = {$1, $2 ..... Sp} of sequences, we speak of a Longest Common Subsequence of R, LCS(R), as a longest sequence S such that S < S, for i = 1 ..... p.For example, abe = LCS((ababe, cabe, abdde} ).Actually, LCS(R) is a set of subsequences, since there may be more than one sequence fitting the definition.Since we will be mamly concerned with the length of any (and every) LCS(R), when we write LCS(R) we will mean a single representaUve of this set.Simdarly, a Shortest Common Supersequence of R, SCS(R), is a shortest sequence S' such that S' > S,, I = 1 ..... p.For example, SCS({abbb, bab, bba} ) = abbab.The yes~no LCS (SCS)problem is: Given an integer k and a listing of the sequences in R, is ILCS(R)[ --> k (ISCS(R)I .~k), where IsI is the number of terms in sequence S?Whenever we refer to the LCS and SCS problems in this paper, we will mean the yes/no versions.We define the alphabet of R, X(R), to be the finite set of values the terms of sequences S1, $2 ..... Sp take on.Clearly IX(R) I -< ml + m2 + + rap, where m, = [ S,I.We also use I I to denote the cardinality of a set; the context will distinguish the usage. Threading SchemesIt is convenient to think of the LCS and SCS problems in terms of threading beads.We think of a sequence as a row of beads and the matching process as threading the beads m a certain manner.Suppose we have three sequences $1 = bybrr, $2 --yyrrbr, and $3 = byrry.We represent them as rows of beads:General permission to make fair use in teaching or research of all or part of this material is granted to individual readers and to nonprofit hbrarles acting for them provided that ACM's copyright noUce is given and that reference is made to the pubhcatlon, to ItS date of msue, and to the fact that reprinting prlwleges were granted by permission of the Association for Computing Machinery To otherwise reprint a figure, table, other substantial excerpt, or the entire work requires specific permission as does repubhcatlon, or systematic or muluple reproduction

We present a method for computing ancestor information in trees. We show the method is tunable to specific applications, and compare it to other methods. Finally, we apply our procedures to the problem of finding negative cycles in sparse graphs.