This paper identifies a problem with databases that support metadata. Previous research has proposed annotating values stored in a database with metadata, such as time, security, privacy, and quality. The metadata influences how a value is used. For example, sequenced temporal semantics proscribes comparing a value to one alive at a different time. But when values stored in a database are pulled into the realm of a programming language from a database through an API, web service, or in a user-defined function, a step-down transformation of the data occurs. The transformation strips the metadata, changing the semantics of the value. The metadata is discarded because a programming language process a scalar value, not one annotated with metadata. This metadata-related impedance mismatch between databases and programming languages limits the real-world adoption of databases that support metadata.

JSON keyword search searches the current versions of documents in a collection. However, JSON documents change over time due to edits. Some applications, such as data forensics and auditing, need to search past versions of documents and for changes to documents. This paper introduces a system called Temporal JSON Keyword Search (TJKS) for search in a collection of JSON documents that vary over time. TJKS lets users control which temporal slice, or part of the history, can be searched using a temporal search semantics; we support both of the major temporal semantics: sequenced and nonsequenced search. This paper presents the semantics of temporal JSON keyword search, discusses an efficient implementation, and evaluates the implementation. Our extensions are largely orthogonal to specific keyword search techniques, so this research provides a blueprint for extending keyword search to include time and potentially other kinds of metadata.

DBMS performance is dependent on many parameters, such as index selection, cache size, physical layout, and data partitioning. Some combinations of these parameters can lead to optimal performance for a given workload but selecting an optimal or near-optimal combination is challenging, especially for large databases with complex workloads. Among the hundreds of parameters, index selection is arguably the most critical parameter for performance. We propose a self-administered framework, called the Multiple Type and Attribute Index Selector (MANTIS), that automatically selects near-optimal indexes. The framework advances the state-of-the-art index selection by considering both multi-attribute and multiple types of indexes within a bounded storage size constraint, a combination not previously addressed. MANTIS combines supervised and reinforcement learning, a Deep Neural Network recommends the type of index for a given workload while a Deep Q-Learning network recommends the multi-attribute aspect. MANTIS is sensitive to storage cost constraints and incorporates noisy rewards in its reward function for better performance. Our experimental evaluation shows that MANTIS outperforms the current state-of-art methods by an average of 9.53% [email protected]

A whole farm carbon model estimates the emissions of greenhouse gasses (GHGs) based on information for a farm. We analyzed two models, Holos whole-farm and COMET-Farm, by running the models on random inputs and building predictive models from the runs. Holos estimates GHG emissions for a particular year based on crop and animal agriculture input, while COMET-farm adds past and future farm management practices. Users of the models must manually enter farm data through a graphical user interface (GUI), which is a good method for a single farm, but makes it infeasible to calculate GHG emissions over hundreds to thousands of farms. So we automated the interface and generated random farm scenarios within ranges given by experts. We scraped the estimated carbon footprint from thousands of runs of the models and used algorithms to build predictive models that have high accuracy. By reverse engineering the whole-farm carbon models we were able to determine which farm management practices in each whole farm carbon model have the biggest impact on GHG emissions. This can help farmers and rural planners change farm management practices to decrease GHG emissions.

Despite a decade of research on XML keyword search (XKS), demonstration of a high quality XKS system has still eluded the information retrieval community. Existing XKS engines primarily suffer from two limitations. First, although the smallest lowest common ancestor (SLCA) algorithm (or a variant, e.g., ELCA) is widely accepted as a meaningful way to identify subtrees containing the query keywords, SLCA typically performs poorly on documents with missing elements, i.e., (sub)elements that are optional, or appear in some instances of an element type but not all. Second, since keyword search can be ambiguous with multiple possible interpretations, it is desirable for an XKS engine to automatically expand the original query by providing a classification of different possible interpretations of the query w.r.t. the original results. However, existing XKS systems do not support such result-based query expansion. We demonstrate ASTERIX, an innovative XKS engine that addresses these limitations.

Visual graph interfaces improve the usability of graph databases by making it easier for users to formulate queries. Recently, a variety of interactive query formulation-based techniques (e.g., blending of visual query construction and processing, visual query suggestions) have been proposed to enhance query performance and usability. Comprehensive user studies are needed to exhaustively and systematically evaluate performance of the proposed techniques, but, unfortunately, user studies are expensive and time consuming. To reduce the cost and time needed, we present a novel synthetic visual subgraph query simulator called VISUAL. VISUAL realistically simulates subgraph query construction without requiring human users. It can automatically generate test subgraph queries having different user-specified characteristics by utilizing the underlying indexes and simulate their formulation based on different query formulation sequences. A key feature of this simulator is that it is built on top of an HCI-inspired, extensible quantitative model which enables us to model the visual query formulation process quantitatively. Our experimental study demonstrates the effectiveness of VISUAL in accurately simulating visual subgraph queries.

Visual query interfaces make it easy for scientists and other nonexpert users to query a data collection. Heretofore, visual query interfaces have been statically-constructed, independent of the data. In this paper we outline a vision of a different kind of interface, one that is built (in part) from the data. In our data-driven approach, the visual interface is dynamically constructed and maintained. A data-driven approach has many benefits such as reducing the cost in constructing and maintaining an interface, superior support for query formulation, and increased portability of the interface. We focus on graph databases, but our approach is applicable to several other kinds of databases such as JSON and XML.

The usability of visual querying schemes for tree and graph-structured data can be greatly enhanced by providing feedback during query construction, but feedback at inopportune times can hamper query construction. In this paper, we rethink the traditional way of providing feedback. We describe a novel vision of interruption-sensitive query feedback where relevant notifications are delivered quickly but at an appropriate moment when the mental workload of the user is low. Though we focus on one class of query feedback, namely empty result detection, where a user is notified when a partially constructed visual query yields an empty result, our new paradigm is applicable to other kinds of feedback. We present a framework called iSERF that bridges the classical database problem of empty-result detection with intelligent notification management from the domains of HCI and psychology. Instead of immediate notification, iSERF considers the structure of query formulation tasks and breakpoints when reasoning about when to notify the user. We present an HCI-inspired model to quantify the performance bounds that iSERF must abide by for checking for an empty result in order to ensure interruption-sensitive notification at optimal breakpoints. We implement this framework in the context of visual XML query formulation and highlight its effectiveness empirically.

XQuery programs can be hard to write and port to new data collections because the path expressions in a query aredependenton the hierarchy of the data. We propose to demonstrate a system to liberate query writers from this dependence. Aplug-and-play querycontains a specification of what data the query needs in order to evaluate. We implementedvirtual eXist-dbto support plug-and-play XQuery queries. Our system adds avirtualDocfunction that lets a programmer sketch the hierarchy needed by the query, which may well be different than what the data has, and logically (not physically) transforms the data (with information loss guarantees) to the hierarchy specified by thevirtualDoc.The demonstration will consist of a sequence of XQuery queries using a virtual hierarchy, including queries suggested by the audience. We will also demonstrate a GUI tool to construct a virtual hierarchy.

Prefix-based numbering is a popular method for numbering nodes in a hierarchy. But prefix-based numbering breaks down when a node's location within a hierarchy changes, such as when XML data is queried after being transformed by an XSLT program or when data is reformatted in the return clause of an inner FLWR expression in a nested XQuery program. A query on transformed data cannot be evaluated as efficiently since the extant prefix-based node numbers cannot be used (unless the data is materialized and then renumbered, which can be expensive). In this paper we present a novel strategy to virtually transform the data without instantiating and renumbering. Our method, which we call virtual prefix-based numbering, couples each prefix-based node number with a level array that locates the node in the numbering space of the virtual hierarchy. The virtual numbering space preserves the property that location-based relationships between nodes can be determined by comparing (virtual) numbers.

Keyword search for smallest lowest common ancestors (SLCAs) in XML data has been widely accepted as a meaningful way to identify matching nodes where their subtrees contain an input set of keywords. Although SLCA and its variants (e.g.,MLCA) perform admirably in identifying matching nodes, surprisingly, they perform poorly for searches on irregular schemas that have missing elements, that is, (sub)elements that are optional, or appear in some instances of an element type but not all (e.g., a "population" subelement in a "city" element might be optional, appearing when the population is known and absent when the population is unknown). In this paper, we generalize the SLCA search paradigm to support queries involving missing elements. Specifically, we propose a novel property called optionality resilience that specifies the desired behaviors of an XML keyword search (XKS) approach for queries involving missing elements. We present two variants of a novel algorithm called MESSIAH (Missing Element-conSciouS hIgh-quality SLCA searcH), which are optionality resilient to irregular documents. MESSIAH logically transforms an XML document to a minimal full document where all missing elements are represented as empty elements, i.e., the irregular schema is made "regular", and then employs efficient strategies to identify partial and complete full SLCA nodes (SLCA nodes in the full document) from it. Specifically, it generates the same SLCA nodes as any state-of-the-art approach when the query does not involve missing elements but avoids irrelevant results when missing elements are involved. Our experimental study demonstrates the ability of MESSIAH to produce superior quality search results.

A limitation of XQuery is that a programmer has to be familiar with the shape of the data to query it effectively. And if that shape changes, or if the shape is other than what the programmer expects, the query may fail. One way to avoid this limitation is to transform the data into a desired shape. A data transformation is a rearrangement of data into a new shape. In this paper, we present the semantics and implementation of XMorph 2.0, a shape-polymorphic data transformation language for XML. An XMorph program can act as a query guard. The guard both transforms data to the shape needed by the query and determines whether and how the transformation potentially loses information, a transformation that loses information may lead to a query yielding an inaccurate result. This paper describes how to use XMorph as a query guard, gives a formal semantics for shape-to-shape transformations, documents how XMorph determines how a transformation potentially loses information, and describes the XMorph implementation.

If past versions of XML documents are retained, what of the various integrity constraints defined in XML Schema on those documents? This paper describes how to interpret such constraints as sequenced constraints, applicable at each point in time. We also consider how to add new variants that apply across time, so-called nonsequenced constraints. Our approach supports temporal documents that vary over both valid and transaction time, whose schema can vary over transaction time. We do this by replacing the schema with a (possibly time-varying) temporal schema and replacing the document with a temporal document, both of which are upward compatible with conventional XML and with conventional tools like XMLLINT, which we have extended to support the temporal constraints introduced here.

Timeseries can be similar in shape but differ in length. For example, the sound waves produced by the same word spoken twice have roughly the same shape, but one may be shorter in duration. Stream data mining, approximate querying of image and video databases, data compression, and near duplicate detection are applications that need to be able to classify or cluster such timeseries, and to search for and rank timeseries that are similar to a chosen timeseries. We demonstrate software for clustering and performing similarity search in databases of timeseries data, where the timeseries have high and variable dimensionality. Our demonstration uses Timeseries Sensitive Hashing (TSH)[3] to index the timeseries. TSH adapts Locality Sensitive Hashing (LSH), which is an approximate algorithm to index data points in a d-dimensional space under some (e.g., Euclidean) distance function. TSH, unlike LSH, can index points that do not have the same dimensionality. As examples of the potential of TSH, the demonstration will index and classify timeseries from an image database and timeseries describing human motion extracted from a video stream and a motion capture system.

A data sieve filters a data stream to harvest data of interest and summarizes the harvested data in a multidimensional database (MDB). To build the data sieve, a designer supplies a list of filters. Each filter consists of a filter unit and category for each dimension. The filter unit specifies a pattern (a regular expression) to match as the data stream is filtered. The filter category is the system of measurement in which occurrences of that pattern are counted or otherwise aggregated. Since filtering discards some of the data, incomplete regions within the MDB are created. The missing data complicates querying. While a query on the filtered data can be automatically analysed to determine if sufficient information has been filtered to satisfy it, a better query construction strategy is to prevent users from formulating unsatisfiable queries. To aid users in formulating only satisfiable queries, the GUI for a data sieve needs to color or otherwise display regions of complete, partially complete, and missing data. As a user constructs a query, choosing categories and units, the displayed incomplete regions shift and change, curtailing future choices. For instance, if a user selects a spatial unit of Australia, the display for a temporal category of days may need to be colored as incomplete since no filters would satisfy both selections. We describe an algorithm that uses bit strings to create and maintain the display of incomplete information in a data sieve in real-time.

In this paper we apply the aspect-oriented programming (AOP) paradigm to the relational algebra. AOP is a way to add support for cross-cutting concerns to existing code without directly modifying that code. Data, like code, also has cross-cutting concerns such as versioning, privacy, and reliability. AOP techniques can be used to weave metadata around an application's data. The metadata imbues the data with additional semantics that must be observed in constraint and query processing. In this paper we show how to modify the relational algebra to process data woven together with metadata. We also analyze the overhead on evaluating an aspect-enhanced query.

Data has cross-cutting concerns such as versioning, privacy, and reliability. In this paper we sketch support such concerns by adapting the aspect-oriented programming (AOP) paradigm to data. Our goal, shared by AOP, is to re-engineer applications to support cross-cutting concerns without directly modifying the application's data or queries. We propose modeling a cross-cutting data concern as a data aspect. A data aspect weaves metadata around an application's data and queries, imbuing them with additional semantics for constraint and query processing.

We present a novel approach to mining dependency rules that explain the scenes present during a video sequence. The approach first characterizes activities based on their most important events. Next, an HMM-based approach finds the mixture components that best describe the clustering dependencies between events and activities in video data. The dependencies among activities are taken as association patterns with temporal precedence and analyzed using their co-occurrence relationships in time windows. This technique is meant to understand the multiple actions taken in a video or to predict future occurrences of certain activities.

By imposing a single hierarchy on data, XML makes queries brittle in the sense that a query might fail to produce the desired result if it is executed on the same data organized in a different hierarchy, or if the hierarchy evolves during the lifetime of an application. This paper presents a new transformation language, called XMorph, which supports more flexible querying. XMorph is a shape polymorphic language, that is, a single XMorph query can extract and transform data from differently-shaped hierarchies. The XMorph data shredder distills XML data into a graph of closest relationships, which are exploited by the query evaluation engine to produce a result in the shape specified by an XMorph query.

XMorph is a new, shape polymorphic, domain-specific XML query language. A query in a shape polymorphic language adapts to the shape of the input, freeing the user from having to know the input's shape and making the query applicable to a wide variety of differently shaped inputs. An XMorph query specifies the shape of the output. The XMorph query engine transforms the input to the desired shape by shredding an XML document to a graph of closest relationships, and performing a closeness preserving transformation. We plan to demonstrate XMorph using a Java applet, which can also be used by the audience during the demonstration, to evaluate various XMorph queries. The applet will show the output, the shapes generated by the query, and report on potential data loss in a transformation.

XML query languages use directional path expressions to locate data in an XML data collection. They are tightly coupled to the structure of a data collection, and can fail when evaluated on the same data in a different structure. This paper extends path expressions with a new non-directional axis called the rank-distance axis. Given a context node and two positive integers α and β, the rank-distance axis returns those nodes that are ranked between α and β in terms of closeness from the context node in any direction. This paper shows how to evaluate the rank-distance axis in a tree-unaware XML database. A tree-unaware implementation does not invade the database kernel to support XML queries, instead it uses an existing RDBMS such as Microsoft's SQL server as a back-end and provides a front-end layer to translate XML queries to SQL. This paper presents an overview of an algorithm that translates queries with a rank-distance axis to SQL.

In data integration applications, a join matches elements that are common to two data sources. Often, however, elements are represented slightly different in each source, so an approximate join must be used. For XML data, most approximate join strategies are based on some ordered tree matching technique. But in data-centric XML the order is irrelevant: two elements should match even if their subelement order varies. In this paper we give a solution for the approximate join of unordered trees. Our solution is based on windowed pq-grams. We develop an efficient technique to systematically generate windowed pq-grams in a three-step process: sorting the unordered tree, extending the sorted tree with dummy nodes, and computing the windowed pq-grams on the extended tree. The windowed pq-gram distance between two sorted trees approximates the tree edit distance between the respective unordered trees. The approximate join algorithm based on windowed pq-grams is implemented as an equality join on strings which avoids the costly computation of the distance between every pair of input trees. Our experiments with synthetic and real world data confirm the analytic results and suggest that our technique is both useful and scalable.

Motivated by the increasing need to analyze complex, uncertain multidimensional data this paper proposes probabilistic OLAP queries that are computed using probability distributions rather than atomic values. The paper describes how to create probability distributions from base data, and how the distributions can be subsequently used in pre-aggregation. Since the probability distributions can become large, we show how to achieve good time and space efficiency by approximating the distributions. We present the results of several experiments that demonstrate the effectiveness of our methods. The work is motivatedwith a real-world case study, based on our collaboration with a leading Danish vendor of location-based services. This paper is the first to consider the approximate processing of probabilistic OLAP queries over probability distributions.

Path expressions are the principal means of locating data in a hierarchical model. But path expressions are brittle because they often depend on the structure of data and break if the data is structured differently. The structure of data could be unfamiliar to a user, may differ within a data collection, or may change over time as the schema evolves. This paper proposes a novel construct that locates related nodes in an instance of an XML data model, independent of a specific structure. It can augment many XPath expressions and can be seamlessly incorporated in XQuery or XSLT.

This paper presents a transaction-time HTTP server, called TTApache that supports document versioning. A document often consists of a main file formatted in HTML or XML and several included files such as images and stylesheets. A change to any of the files associated with a document creates a new version of that document. To construct a document version history, snapshots of the document's files are obtained over time. Transaction times are associated with each file version to record the version's lifetime. The transaction time is the system time of the edit that created the version. Accounting for transaction time is essential to supporting audit queries that delve into past document versions and differential queries that pinpoint differences between two versions. TTApache performs automatic versioning when a document is read thereby removing the burden of versioning from document authors. Since some versions may be created but never read, TTApache distinguishes between known and assumed versions of a document. TTApache has a simple query language to retrieve desired versions. A browser can request a specific version, or the entire history of a document. Queries can also rewrite links and references to point to current or past versions. Over time, the version history of a document continually grows. To free space, some versions can be vacuumed. Vacuuming a version however changes the semantics of requests for that version. This paper presents several policies for vacuuming versions and strategies for accounting for vacuumed versions in queries.

This paper presents a novel strategy for temporal coalescing. Temporal coalescing merges the temporal extents of value-equivalent tuples. A temporal extent is usually coalesced offline and stored since coalescing is an expensive operation. But the temporal extent of a tuple with now, times at different granularities, or incomplete times cannot be determined until query evaluation. This paper presents a strategy to partially coalesce temporal extents by identifying regions that are potentially covered. The covered regions can be used to evaluate temporal predicates and constructors on the coalesced extent. Our strategy uses standard relational database technology. We quantify the cost using the Oracle DBMS.

Transaction time is the time of database transactions that create, modify, or destroy facts. It is used to record when facts exist in a database. Accounting for transaction time is essential to supporting audit queries that delve into past database states and differential queries that pinpoint differences between two states. In a web context, transaction time is a problematic concept because there are no transactions. Browsers and other consumers of web data can observe snapshots of resources like XML documents but are rarely active participants in their creation or destruction. This paper presents the TTXPath data model and query language. TTXPath extends XPath with support for transaction time. XPath is a specification language for locations in an XML document. It serves as the basis for XML query languages like XSLT and XQuery, XPath has no temporal semantics. To construct a TTXPath data model, snapshots of an XML document are obtained over time by an observer The snapshots are then merged and transaction times are associated with each edge and node. The TTXPath query language extends XPath with a transaction-time axis to enable a query to access past or future states, and with constructs to extract and compare times. TTXPath maximally reuses XPath hence the changes needed to support transaction time are minimal and TTXPath is fully backwards compatible with XPath.

Granularity is an integral feature of temporal data. For instance, a person's age is commonly given to the granularity of years and the time of their next airline flight to the granularity of minutes. A granularity creates a discrete image, in terms of granules, of a (possibly continuous) time-line. We present a formal model for granularity in temporal operations that is integrated with temporal indeterminacy, or "don't know when" information. We also minimally extend the syntax and semantics of SQL-92 to support mixed granularities. This support rests on two operations, scale and cast, that move times between granularities, e.g., from days to months. We demonstrate that our solution is practical by showing how granularities can be specified in a modular fashion, and by outlining a time- and space-efficient implementation. The implementation uses several optimization strategies to mitigate the expense of accommodating multiple granularities.

Online analytical processing (OLAP) technologies are being used widely, but the lack of effective means of handling data imprecision, which occurs when exact values are not known precisely or are entirely missing, represents a major obstacle in applying these technologies in many domains. The paper develops techniques for handling imprecision that aim to maximally reuse existing OLAP modeling constructs such as dimension hierarchies and granularities. With imprecise data available in the database, queries are tested to determine whether or not they may be answered precisely given the available data; if not, alternative queries unaffected by the imprecision are suggested. When processing queries affected by imprecision, techniques are proposed that take into account the imprecision in the grouping of the data, in the subsequent aggregate computation, and in the presentation of the imprecise result to the user. The approach is capable of exploiting existing OLAP query processing techniques such as pre-aggregation, yielding an effective approach with low computational overhead and that may be implemented using current technology.

In valid-time indeterminacy it is known that an event stored in a database did in fact occur, but it is not known exactly when . In this paper we extend the SQL data model and query language to support valid-time indeterminacy. We represent the occurrence time of an event with a set of possible instants, delimiting when the event might have occurred, and a probability distribution over that set. We also describe query language constructs to retrieve information in the presence of indeterminacy. These constructs enable users to specify their credibility in the underlying data and their plausibility in the relationships among that data. A denotational semantics for SQL's select statement with optional credibility and plausibility constructs is given. We show that this semantics is reliable, in that it never produces incorrect information, is maximal, in that if it were extended to be more informative, the results may not be reliable, and reduces to the previous semantics when there is no indeterminacy. Although the extended data model and query language provide needed modeling capabilities, these extensions appear initially to carry a significant execution cost. A contribution of this paper is to demonstrate that our approach is useful and practical. An efficient representation of valid-time indeterminacy and efficient query processing algorithms are provided. The cost of support for indeterminacy is empirically measured, and is shown to be modest. Finally, we show that the approach is general, by applying it to the temporal query language constructs being proposed for SQL3.

Although “ now ” is expressed in SQL and CURRENT_TIMESTAMP within queries, this value cannot be stored in the database. How ever, this notion of an ever-increasing current-time value has been reflected in some temporal data models by inclusion of database-resident variables, such as “ now ” “ until-changed, ” “**,” “@,” and “-”. Time variables are very desirable, but their used also leads to a new type of database, consisting of tuples with variables, termed a variable database.

In valid-time indeterminacy, it is known that an event stored in a temporal database did in fact occur, but it is not known exactly when the event occurred. An extension of the tuple-timestamped temporal data model, called the possible chronons data model, is presented to support valid-time indeterminacy. In the possible chronons data model, each event is represented with a set of possible chronons, delimiting when the event might have occurred and a probability distribution over the set. The TQuel query language is extended using constructs that specify the user's credibility in the underlying valid-time data and the user's plausibility in the relationships among that data. A formal tuple calculus semantics is outlined, and it is shown that this semantics reduces to the determinate semantics on determinate data.>