Open Science is a fundamentally new philosophy about the goals, methods, and business models of scientific research and scholarly communication. The motivation for research remains the same, as Open Science continues to honor scientific curiosity and societal or industrial challenges as its primary drivers. Open Science methodologies, however, continue to spotlight individual researchers for their achievements, but also promote common good. They are motivated by the following needs: increase researchers' collaboration, accountability, and transparency; democratize researchers' and the general public's access to knowledge around the world; reconceive of what constitutes a publication to include data, software, and other artifacts beyond traditional papers; elevate the importance of research results' reproducibility; and increase society's trust to the scientific community. Open Science affects every single stage of the research lifecycle significantly. Naturally, the scientific community and the extended ecosystem around it (university administrators, research funders, journal publishers, conference organizers, ...) need ample time to move towards the new mentality. In preparation for this change, this panel exposes the key dimensions of Open Science to the database community, highlights the various choices offered in each dimension, and debates their advantages and disadvantages and the way forward.

Modern data applications in areas such as text mining, document analysis, and data science, involve complex algorithms and logic that cannot be expressed in SQL. Therefore, SQL databases employ user-defined functions (UDFs) to extend their supported functionality. However, this comes at a significant performance cost as UDFs routinely become the bottleneck in query execution. To deal with this problem, we present QFusor, an optimizer plugin for UDF queries in relational databases. QFusor minimizes the performance overheads introduced by the impedance mismatch between the UDF and SQL execution environments by employing techniques such as vectorization, parallelization, tracing JIT compilation, and operator fusion for various types of UDF (scalar, aggregate, table UDFs) and relational operators. QFusor follows a pluggable, engine-agnostic design and can work with several popular SQL databases offering a significant boost in their UDF query performance.

Serverless cloud-based warehousing systems enable users to create materialized views in order to speed up predictable and repeated query workloads. Incremental view maintenance (IVM) minimizes the time needed to bring a materialized view up-to-date. It allows the refresh of a materialized view solely based on the base table changes since the last refresh. In serverless cloud-based warehouses, IVM uses computations defined as SQL scripts that update the materialized view based on updates to its base tables. However, the scripts set up for materialized views with inner joins are not optimal in the presence of foreign key constraints. For instance, for a join of two tables, the state of the art IVM computations use a UNION ALL operator of two joins - one computing the contributions to the join from updates to the first table and the other one computing the remaining contributions from the second table. Knowing that one of the join keys is a foreign-key would allow us to prune all but one of the UNION ALL branches and obtain a more efficient IVM script. In this work, we explore ways of incorporating knowledge about foreign key into IVM in order to speed up its performance. Experiments in Redshift showed that the proposed technique improved the execution times of the whole refresh process up to 2 times, and up to 2.7 times the process of calculating the necessary changes that will be applied into the materialized view.

The diversity and complexity of modern data management applications led to the extension of the relational paradigm with syntactic and semantic support for User-Defined Functions (UDFs). Although well-established in traditional DBMS settings, UDFs have become even more central in many applications spanning data science, data analytics, etc. Still, a critical limitation of UDFs, which to some extent has turned data scientists towards NoSQL systems, is the impedance mismatch between their evaluation and relational processing. We present YeSQL, an SQL extension with rich UDF support along with a pluggable architecture to easily integrate it with either server-based or embedded database engines. We currently support UDFs written in Python, which are fully integrated with relational queries as scalar functions, aggregators, or table returning functions. Key novel characteristics of YeSQL include easy implementation of complex algorithms, tracing JIT compilation of Python UDFs, and seamless integration with a database engine. Our demonstration will showcase (a) the usability and expressiveness of our approach, and (b) that our techniques of minimizing context switching between the relational engine and the Python VM are very effective and achieve significant speedups in common, practical use cases.

The diversity and complexity of modern data management applications have led to the extension of the relational paradigm with syntactic and semantic support for User-Defined Functions (UDFs). Although well-established in traditional DBMS settings, UDFs have become central in many application contexts as well, such as data science, data analytics, and edge computing. Still, a critical limitation of UDFs is the impedance mismatch between their evaluation and relational processing. In this paper, we present YeSQL, an SQL extension with rich UDF support along with a pluggable architecture to easily integrate it with either server-based or embedded database engines. YeSQL currently supports Python UDFs fully integrated with relational queries as scalar, aggregator, or table functions. Key novel characteristics of YeSQL include easy implementation of complex algorithms and several performance enhancements, including tracing JIT compilation of Python UDFs, parallelism and fusion of UDFs, stateful UDFs, and seamless integration with a database engine. Our experimental analysis showcases the usability and expressiveness of YeSQL and demonstrates that our techniques of minimizing context switching between the relational engine and the Python VM are very effective and achieve significant speedups up to 68x in common, practical use cases compared to earlier approaches and alternative implementation choices.

State-of-the-art OLAP systems tend to use columnar data representations, as these are both suitable for analytics and amenable to compression. Local dictionary value encoding has been shown to achieve high compression rates for string columns while still allowing fast filtered scans. In this paper, we argue that the effectiveness and efficiency of local dictionary compression is limited by data repetition across file blocks and by dictionary look-ups inside each block during filtered scan execution. To address this problem, we introduce an adaptive compression technique that is based on differential dictionaries and targets both storage efficiency and query performance. The proposed scheme reduces dramatically the need to store repeated values across different file blocks and significantly accelerates read operations by reducing the time needed for dictionary look-ups. A preliminary set of experiments has given very promising results, showing that, in many cases, the proposed new dictionary compression scheme is much more efficient than existing techniques, occasionally up to an order of magnitude.

Text-to-SQL systems allow users to explore relational databases by posing free-form queries, alleviating the need for using structured languages, such as SQL. Although numerous systems have been developed so far, existing system evaluations lack in rigour. In this work, we build a text-to-SQL benchmark that covers different classes of queries, and we evaluate the effectiveness of several systems in the field. To evaluate system efficiency, we measure execution time and resource consumption for the different query classes. Our comprehensive evaluation aims at filling in a big gap in understanding the capabilities and boundaries of existing systems and it reveals several open challenges.

Knowledge Graphs (KGs) are collections of interconnected and annotated entities that have become powerful assets for data integration, search enhancement, and other industrial applications. Knowledge Graphs such as DBPEDIA may contain billion of triple relations and are intensively queried with millions of queries per day. A prominent approach to enhance query answering on Knowledge Graph databases is View Materialization, ie., the materialization of an appropriate set of computations that will improve query performance. We study the problem of view materialization and propose a view selection methodology for processing query workloads with more than a million queries. Our approach heavily relies on subgraph pattern mining techniques that allow to create efficient summarizations of massive query workloads while also identifying the candidate views for materialization. In the core of our work is the correspondence between the view selection problem to that of Maximizing a Nondecreasing Submodular Set Function Subject to a Knapsack Constraint . The latter leads to a tractable view-selection process for native triple stores that allows a (1 - e ---1 )-approximation of the optimal selection of views. Our experimental evaluation shows that all the steps of the view-selection process are completed in a few minutes, while the corresponding rewritings accelerate 67.68% of the queries in the DBPEDIA query workload. Those queries are executed in 2.19% of their initial time on average.

We argue that most recommendation approaches can be abstracted as a graph exploration problem. In particular, we describe a graph-theoretic framework with two primary parts: (a) a recommendation graph, modeling all the elements of an (application) domain from a recommendation perspective, including the subjects and objects of recommendations as well as the relationships between them; (b) a set of path operations, inferring new edges, i.e., implicit or unknown relationships, by traversing and combining paths on the graph. The resulting path algebra model provides an abstraction and a common foundation that is beneficial to three aspects of recommendations: (a) expressive power - expression and subsequent use of several significantly different, existing but also novel recommendation approaches is reduced to parameterizing a unique model; (b) usability - by capturing part of the recommendation mechanisms in the underlying path algebra semantics, specification of recommendation approaches becomes easier and less tedious; (c) processing speed - implementing recommender systems on top of graph engines opens up the door for several optimizations that speed up execution. We demonstrate the above benefits by expressing several categories of recommendation approaches in the path algebra model and benchmarking some of them in a recommender system implemented on top of Neo4J, a widely used graph system.

Query containment is a fundamental operation used to expedite query processing in view materialisation and query caching techniques. Since query containment has been shown to be NP-complete for arbitrary conjunctive queries on RDF graphs, we introduce a simpler form of conjunctive queries that we name f-graph queries. We first show that containment checking for f-graph queries can be solved in polynomial time. Based on this observation, we propose a novel indexing structure, named mv-index, that allows for fast containment checking between a single f-graph query and an arbitrary number of stored queries. Search is performed in polynomial time in the combined size of the query and the index. We then show how our algorithms and structures can be extended for arbitrary conjunctive queries on RDF graphs by introducing f-graph witnesses, i.e., f-graph representatives of conjunctive queries. F-graph witnesses have the following interesting property, a conjunctive query for RDF graphs is contained in another query only if its corresponding f-graph witness is also contained in it. The latter allows to use our indexing structure for the general case of conjunctive query containment. This translates in practice to microseconds or less for the containment test against hundreds of thousands of queries that are indexed within our structure.

Elasticity makes cloud computing an attractive platform for executing complex large-scale expensive dataflows, as it enables different trade-offs between execution time and monetary cost, by varying the number of resources to be provisioned. With cloud providers offering heterogeneous types of resources with different performance and price characteristics, the problem of identifying the various trade-offs available is a great challenge, as the number of possible alternative configurations increases significantly compared to a homogeneous environment, which is itself already computationally difficult. This paper proposes a novel algorithm for dataflow scheduling on heterogeneous clouds that identifies solutions (schedules) close to the optimal pareto front, by exploring the search space in an efficient way. The results of an experimental comparison with the state of the art show that, in several cases, the proposed algorithm provides a richer, more diverse set of solutions, several of which are characterized by significantly better time-money trade-offs.

In the database community Polystores is an emerging and promising approach for data federation that aims at designing a unified querying layer over multiple data models. In the Semantic Web community a similar in spirit approach of Ontology-Based Data Access (OBDA) has been recently proposed, attracted a lot of attention, and proved its success in several industrial scenarios. In this paper we discuss a semantic approach to building polystores using the OBDA paradigm. We also present our system Optique that is utilized in an industrial application of performing turbine diagnostics in Siemens.

Big Data applications require real-time processing of complex computations on streaming and static information. Applications such as the diagnosis of power generating turbines require the integration of high velocity streaming and large volume of static data from multiple sources. In this paper we study various optimisations related to efficiently processing of streaming and static information. We introduce novel indexing structures for stream processing, a query-planner component that decides when their creation is beneficial, and we examine precomputed summarisations on archived measurements to accelerate streaming and static information processing. To put our ideas into practise, we have developed ExaStream, a data stream management system that is scalable, has declarative semantics, supports user defined functions, and allows efficient execution of complex analytical queries on streaming and static data. Our work is accompanied by an empirical evaluation of our optimisation techniques.

Real-time processing of data coming from multiple heterogeneous data streams and static databases is a typical task in many industrial scenarios such as diagnostics of large machines. A complex diagnostic task may require a collection of up to hundreds of queries over such data. Although many of these queries retrieve data of the same kind, such as temperature measurements, they access structurally different data sources. In this work we show how Semantic Technologies implemented in our system optique can simplify such complex diagnostics by providing an abstraction layer---ontology---that integrates heterogeneous data. In a nutshell, optique allows complex diagnostic tasks to be expressed with just a few high-level semantic queries. The system can then automatically enrich these queries, translate them into a collection with a large number of low-level data queries, and finally optimise and efficiently execute the collection in a heavily distributed environment. We will demo the benefits of optique on a real world scenario from Siemens.

Earth-Science data are composite, multi-dimensional and of significant size, and as such, continue to pose a number of ongoing problems regarding their management. With new and diverse information sources emerging as well as rates of generated data continuously increasing, a persistent challenge becomes more pressing: To make the information existing in multiple heterogeneous resources readily available. The widespread use of the XML data-exchange format has enabled the rapid accumulation of semi-structured metadata for Earth-Science data. In this paper, we exploit this popular use of XML and present the means for querying metadata emanating from multiple sources in a succinct and effective way. Thereby, we release the user from the very tedious and time consuming task of examining individual XML descriptions one by one. Our approach, termed Meta-Array Data Search (MAD Search), brings together diverse data sources while enhancing the user-friendliness of the underlying information sources. We gather metadata using different standards and construct an amalgamated service with the help of tools that discover and harvest such metadata; this service facilitates the end-user by offering easy and timely access to all metadata. The main contribution of our work is a novel query language termed xWCPS, that builds on top of two widely-adopted standards: XQuery and the Web Coverage Processing Service (WCPS). xWCPS furnishes a rich set of features regarding the way scientific data can be queried with. Our proposed unified language allows for requesting metadata while also giving processing directives. Consequently, the xWCPS-enabled MAD Search helps in both retrieval and processing of large data sets hosted in an heterogeneous infrastructure. We demonstrate the effectiveness of our approach through diverse use-cases that provide insights into the syntactic power and overall expressiveness of xWCPS. We evaluate MAD Search in a distributed environment that comprises five high-volume array-databases whose sizes range between 20 and 100 GB and so, we ascertain the applicability and potential of our proposal.

This paper presents Logos, a system that provides natural language translations for relational queries expressed in SQL. Our translation mechanism is based on a graph-based approach to the query translation problem. We represent various forms of structured queries as directed graphs and we annotate the graph edges with template labels using an extensible template mechanism. Logos uses different graph traversal strategies for efficiently exploring these graphs and composing textual query descriptions. The audience may interactively explore Logos using various database schemata and issuing either sample or ad hoc queries.

Scheduling data processing workflows (dataflows) on the cloud is a very complex and challenging task. It is essentially an optimization problem, very similar to query optimization, that is characteristically different from traditional problems in two aspects: Its space of alternative schedules is very rich, due to various optimization opportunities that cloud computing offers; its optimization criterion is at least two-dimensional, with monetary cost of using the cloud being at least as important as query completion time. In this paper, we study scheduling of dataflows that involve arbitrary data processing operators in the context of three different problems: 1) minimize completion time given a fixed budget, 2) minimize monetary cost given a deadline, and 3) find trade-offs between completion time and monetary cost without any a-priori constraints. We formulate these problems and present an approximate optimization framework to address them that uses resource elasticity in the cloud. To investigate the effectiveness of our approach, we incorporate the devised framework into a prototype system for dataflow evaluation and instantiate it with several greedy, probabilistic, and exhaustive search algorithms. Finally, through several experiments that we have conducted with the prototype elastic optimizer on numerous scientific and synthetic dataflows, we identify several interesting general characteristics of the space of alternative schedules as well as the advantages and disadvantages of the various search algorithms. The overall results are quite promising and indicate the effectiveness of our approach.

Many applications offer a form-based environment for nai¿ve users for accessing databases without being familiar with the database schema or a structured query language. User interactions are translated to structured queries and executed. However, as a user is unlikely to know the underlying semantic connections among the fields presented in a form, it is often useful to provide her with a textual explanation of the query. In this paper, we take a graph-based approach to the query translation problem. We represent various forms of structured queries as directed graphs and we annotate the graph edges with template labels using an extensible template mechanism. We present different graph traversal strategies for efficiently exploring these graphs and composing textual query descriptions. Finally, we present experimental results for the efficiency and effectiveness of the proposed methods.

The eight papers in this special section were selected from the 93 long papers presented at the 25th IEEE International Conference on Data Engineering (ICDE 2009), held in Shanghai, China, on 29 March-2 April 2009.

People's preferences are expressed at varying levels of granularity and detail as a result of partial or imperfect knowledge. One may have some preference for a general class of entities, for example, liking comedies, and another one for a fine-grained, specific class, such as disliking recent thrillers with Al Pacino. In this article, we are interested in capturing such complex, multi-granular preferences for personalizing database queries and in studying their impact on query results. We organize the collection of one's preferences in a preference network (a directed acyclic graph), where each node refers to a subclass of the entities that its parent refers to, and whenever they both apply, more specific preferences override more generic ones. We study query personalization based on networks of preferences and provide efficient algorithms for identifying relevant preferences, modifying queries accordingly, and processing personalized queries. Finally, we present results of both synthetic and real-user experiments, which: (a) demonstrate the efficiency of our algorithms, (b) provide insight as to the appropriateness of the proposed preference model, and (c) show the benefits of query personalization based on composite preferences compared to simpler preference representations.

In the classical database world, information access has been based on a paradigm that involves structured, schema-aware, queries and tabular answers. In the current environment, however, where information prevails in most activities of society, serving people, applications, and devices in dramatically increasing numbers, this paradigm has proved to be very limited. On the query side, much work has been done on moving towards keyword queries over structured data. In our previous work, we have touched the other side as well, and have proposed a paradigm that generates entire databases in response to keyword queries. In this paper, we continue in the same direction and propose synthesizing textual answers in response to queries of any kind over structured data. In particular, we study the transformation of a dynamically-generated logical database subset into a narrative through a customizable, extensible, and templatebased process. In doing so, we exploit the structured nature of database schemas and describe three generic translation modules for different formations in the schema, called unary, split, and join modules. We have implemented the proposed translation procedure into our own database front end and have performed several experiments evaluating the textual answers generated as several features and parameters of the system are varied. We have also conducted a set of experiments measuring the effectiveness of such answers on users. The overall results are very encouraging and indicate the promise that our approach has for several applications.

Open Agoras of information are distributed environments of independent systems, where seeking for information is similar to real-life searching for material goods. Interaction with these systems may occur in several unconventional modalities, user behavior may be personalized and context-dependent, system reaction may be unpredictable, and the information produced as a result may also be personalized and context-dependent, negotiable and of uncertain origin or quality. This paper explores open Agoras of information and identifies some technical challenges that they raise.

In large federations of autonomous database systems, automatic distribution of the query workload to those systems is a critical issue. We examine this problem under the perspective of microeconomics theory and show how the latter can be used to construct an efficient decentralized mechanism that maximizes system throughput. In particular, we introduce a solution that is based on the notion of query markets. We examine the properties of these markets and show that they result in Pareto-optimal allocations of resources to queries. An extensive set of experiments with both a simulator and an actual implementation on top of a commercial DBMS demonstrate significant improvements in the overall system throughput when our technique is used.

As a large fraction of available information resides in databases, the need for facilitating access for the large majority of users becomes increasingly more important. Precis queries are free-form queries that generate entire multi-relation databases, which are logical subsets of existing ones. A logical subset contains not only items directly related to the given query selections but also items implicitly related to them in various ways with the purpose of providing to the user much greater insight into the original data. This paper is concerned with the definition and generation of logical database subsets based on precis queries under a generalized perspective that removes several restrictions of previous work and handles queries containing multiple terms combined using the operators AND, OR, and NOT.

No abstract available.

Wide spread use of database systems in modern society has brought the need to provide inexperienced users with the ability to easily search a database with no specific knowledge of a query language. Several recent research efforts have focused on supporting keyword-based searches over relational databases. This paper presents an alternative proposal and introduces the idea of précis queries. These are free-form queries whose answer (a précis) is a synthesis of results, containing not only information directly related to the query selections but also information implicitly related to them in various ways. Our approach to précis queries includes two additional novelties: (a) queries do not generate individual relations but entire multi-relation databases; and (b) query results are personalized to user-specific and/or domain requirements. We develop a framework and system architecture for supporting such queries in the context of a relational database system and describe algorithms that implement the required functionality. Finally, we present a set of experimental results that evaluate the proposed algorithms and show the potential of this work.

Large-scale distributed environments, where each node is completely autonomous and offers services to its peers through external communication, pose significant challenges to query processing and optimization. Autonomy is the main source of the problem, as it results in lack of knowledge about any particular node with respect to the information it can produce and its characteristics, for example, cost of production or quality of produced results. In this article, inspired by e-commerce technology, we recognize queries as commodities and model query optimization as a trading negotiation process. Subquery answers and subquery operator execution jobs are traded between nodes until deals are struck with some nodes for all of them. Such trading may also occur recursively, in the sense that some nodes may play the role of intermediaries between other nodes (subcontracting). We identify the key parameters of the overall framework and suggest several potential alternatives for each one. In comparison to trading negotiations for e-commerce, query optimization faces unique new challenges that stem primarily from the fact that queries have a complex structure and can be broken into smaller parts. We address these challenges through a particular instantiation of our framework focusing primarily on the optimization algorithms run on “buying” and “selling” nodes, the evaluation metrics of the queries, and the negotiation strategy. Finally, we present the results of several experiments that demonstrate the performance characteristics of our approach compared to those of traditional query optimization.

Conventional data management occurs primarily in centralized servers or in well-interconnected distributed systems. These are removed from their end users, who interact with the systems mostly through static devices to obtain generic services around main-stream applications: banking, retail, business management, etc. Several recent advances in technologies, however, give rise to a new breed of applications, which change altogether the user experience and sense of data management. Very soon several such systems will be in our pockets, many more in our homes, the kitchen appliances, our clothes, etc. How would these systems operate? Many system and user aspects must be approached in novel ways, while several new issues come up and need to be addressed for the first time. Highlights include personalization, privacy, information trading, annotation, new interaction devices and corresponding interfaces, visualization, etc. In this talk, we take a close look at and give a very personal guided tour to this emerging world of data management, offering some thoughts on how the new technical challenges might be approached.

Query personalization is the process of dynamically enhancing a query with related user preferences stored in a user profile with the aim of providing personalized answers. The underlying idea is that different users may find different things relevant to a search due to different preferences. Essential ingredients of query personalization are: (a) a model for representing and storing preferences in user profiles, and (b) algorithms for the generation of personalized answers using stored preferences. Modeling the plethora of preference types is a challenge. In this paper, we present a preference model that combines expressivity and concision. In addition, we provide efficient algorithms for the selection of preferences related to a query, and an algorithm for the progressive generation of personalized results, which are ranked based on user interest. Several classes of ranking functions are provided for this purpose. We present results of experiments both synthetic and with real users (a) demonstrating the efficiency of our algorithms, (b) showing the benefits of query personalization, and (c) providing insight as to the appropriateness of the proposed ranking functions.

Personalization is a powerful mechanism that helps users to cope with the abundance of information on the Web. Database query personalization achieves this by dynamically constructing queries that return results of high interest to the user. This, however, may conflict with other constraints on the query execution time and/or result size that may be imposed by the search context, such as the device used, the network connection, etc. For example, if the user is accessing information using a mobile phone, then it is desirable to construct a personalized query that executes quickly and returns a handful of answers. Constrained Query Personalization (CQP) is an integrated approach to database query answering that dynamically takes into account the queries issued, the user's interest in the results, response time, and result size in order to build personalized queries. In this paper, we introduce CQP as a family of constrained optimization problems, where each time one of the parameters of concern is optimized while the others remain within the bounds of range constraints. Taking into account some key (exact or approximate) properties of these parameters, we map CQP to a state search problem and provide several algorithms for the discovery of optimal solutions. Experimental results demonstrate the effectiveness of the proposed techniques and the appropriateness of the overall approach.

As information becomes available in increasing amounts to a wide spectrum of users, the need for a shift towards a more user-centered information access paradigm arises. We develop a personalization framework for database systems based on user profiles and identify the basic architectural modules required to support it. We define a preference model that assigns to each atomic query condition a personal degree of interest and provide a mechanism to compute the degree of interest in any complex query condition based on the degrees of interest in the constituent atomic ones. Preferences are stored in profiles. At query time, personalization proceeds in two steps: (a) preference selection and (b) preference integration into the original user query. We formulate the main personalization step, i.e. preference selection, as a graph computation problem and provide an efficient algorithm for it. We also discuss results of experimentation with a prototype query personalization system.

Twig queries represent the building blocks of declarative query languages over XML data. A twig query describes a complex traversal of the document graph and generates a set of element tuples based on the intertwined evaluation (i.e., join) of multiple path expressions. Estimating the result cardinality of twig queries or, equivalently, the number of tuples in such a structural (path-based) join, is a fundamental problem that arises in the optimization of declarative queries over XML. It is crucial, therefore, to develop concise synopsis structures that summarize the document graph and enable such selectivity estimates within the time and space constraints of the optimizer. We propose novel summarization and estimation techniques for estimating the selectivity of twig queries with complex XPath expressions over tree-structured data. Our approach is based on the XSKETCH model, augmented with new types of distribution information for capturing complex correlation patterns across structural joins. Briefly, the key idea is to represent joins as points in a multidimensional space of path counts that capture aggregate information on the contents of the resulting element tuples. We develop a systematic framework that combines distribution information with appropriate statistical assumptions in order to provide selectivity estimates for twig queries over concise XSKETCH synopses and we describe an efficient algorithm for constructing an accurate summary for a given space budget. Implementation results with both synthetic and real-life data sets verify the effectiveness of our approach and demonstrate its benefits over earlier techniques.

The rapid adoption of XML as the standard for data representation and exchange foreshadows a massive increase in the amounts of XML data collected, maintained, and queried over the Internet or in large corporate data-stores. Inevitably, this will result in the development of on-line decision support systems, where users and analysts interactively explore large XML data sets through a declarative query interface (e.g., XQuery or XSLT). Given the importance of remaining interactive, such on-line systems can employ approximate query answers as an effective mechanism for reducing response time and providing users with early feedback. This approach has been successfully used in relational systems and it becomes even more compelling in the XML world, where the evaluation of complex queries over massive tree-structured data is inherently more expensive. In this paper, we initiate a study of approximate query answering techniques for large XML databases. Our approach is based on a novel, conceptually simple, yet very effective XML-summarization mechanism: TreeSketch synopses. We demonstrate that, unlike earlier techniques focusing solely on selectivity estimation, our TreeSketch synopses are much more effective in capturing the complete tree structure of the underlying XML database. We propose novel construction algorithms for building

The last decade has seen unprecedented advances in network and distributed-system technologies, which have opened up the way for the construction of global-scale systems based on completely new conceptions of computation and sharing of resources. The dream of integrating unlimited levels of processing power, unlimited amounts of information, and an unlimited variety of services, and offering the entire package in a reliable and seamless fashion to widely distributed users is quickly becoming reality. Scientific applications will be among the first to take advantage of such environments, as the demands of current and future experimental studies for intensive computation and processing of very large amounts of information are pressing. GRID technologies are at the forefront of these developments. While much has been written about computation in the GRID environment, data management has received less attention in the literature. Nevertheless, the GRID offers tremendous opportunities for large-scale distributed data management and at the same time poses major technical challenges in the area as well. The goal of this panel discussion is to identify these opportunities and challenges and examine whether the positive aspects of the GRID outweigh the negative ones or vice versa. In this direction, the panelists are called to answer some of the following questions: Is there new research to be done on data management over the GRID? Are there any new problems that arise from managing data over the GRID? For example, are there new problems with respect to security or heterogeneous information integration? Do classical problems require new solutions or do conventional approaches work well in the GRID environment? For example, how does one address issues of concurrency control, recovery, query processing and optimization? How does the GRID compare with other architectures, e.g., peer-to-peer, with respect to data management? Is the existing distributed computing infrastructure developed for the GRID, e.g., Condor, Globus, or Unicore, adequate for supporting the required data management functionality? Are there any particular difficulties when dealing with management of scientific data over the GRID compared to other kinds of data? How does workflow management interact with data management over the GRID?.

In this paper, we introduce dynamic histograms, which are constructed and maintained incrementally. We develop several dynamic histogram construction algorithms and show that they come close to static histograms in quality. Our experimental study covers a wide range of datasets and update patterns, including histogram maintenance in a shared-nothing environment. Building upon the insights offered by the dynamic algorithms, we also propose a new static histogram construction algorithm that is very fast and generates histograms that are close in quality to the highly accurate (but expensive to construct!) V-Optimal histograms. 1 Introduction The cost of executing a relational operator is a function of the sizes of the tuple streams that are input to the operator, which for intermediate operators are in turn determined by selectivities of the previous operators. The more complex a query is, the more important it is to have precise intermediate size estimates. Otherwise, errors in ...

Bitmap indexes are useful in processing complex queries in decision support systems, and they have been implemented in several commercial database systems. A key design parameter for bitmap indexes is the encoding scheme, which determines the bits that are set to 1 in each bitmap in an index. While the relative performance of the two existing bitmap encoding schemes for simple selection queries of the form “v1 ≤ A ≤ v2” is known (specifically, one of the encoding schemes is better for processing equality queries; i.e., v1 = v2, while the other is better for processing range queries; i.e., v1 < v2), it remains an open question whether these two encoding schemes are indeed optimal for their respective query classes in the sense that there is no other encoding scheme with better space-time tradeoff. In this paper, we establish a number of optimality results for the existing encoding schemes; in particular, we prove that neither of the two known schemes is optimal for the class of two-sided range queries. We also propose a new encoding scheme and prove that it is optimal for that class. Finally, we present an experimental study comparing the performance of the new encoding scheme with that of the existing ones as well as four hybrid encoding schemes for both simple selection queries and the more general class of membership queries of the form “A ∈ {v1, v2, .…, vk}”. These results demonstrate that the new encoding scheme has an overall better space-time performance than existing schemes.

It is almost twenty years after the 1st SSDBM was held in Berkeley (then called Workshop on Statistical Database Management). It is almost ten years after the first of a few workshops organized by the National Science Foundation on scientific databases. How many of the original challenges have been accomplished? How many are still here with us and need serious attention? What are the new challenges that have emerged that were not put on the table until recently?

Multimedia applications require a guaranteed level of service for accessing Continuous Media (CM) data, such asvideo and audio. To obtain such guarantees, the database server where the data is residing must employ an admission control scheme to limit the number of clients that can be served concurrently. We investigate the problem of on-line admission control where the decision on whether to accept or reject a request must be made without any knowledge about future requests. Employing competitive analysis techniques, we address the problem in its most general form with the following key contributions: (1) we prove a tight upper bound on the competitive ratio of the conventional Work-Conserving (WC) policy, showing that it is within a factor 1+ of the 1; optimal clairvoyant strategy that knows the entire request

Bitmap indexing has been touted as a promising approach for processing complex adhoc queries in read-mostly environments, like those of decision support systems. Nevertheless, only few possible bitmap schemes have been proposed in the past and very little is known about the space-time tradeoff that they offer. In this paper, we present a general framework to study the design space of bitmap indexes for selection queries and examine the disk-space and time characteristics that the various alternative index choices offer. In particular, we draw a parallel between bitmap indexing and number representation in different number systems, and define a space of two orthogonal dimensions that captures a wide array of bitmap indexes, both old and new. Within that space, we identify (analytically or experimentally) the following interesting points: (1) the time-optimal bitmap index; (2) the space-optimal bitmap index; (3) the bitmap index with the optimal space-time tradeoff (knee); and (4) the time-optimal bitmap index under a given disk-space constraint. Finally, we examine the impact of bitmap compression and bitmap buffering on the space-time tradeoffs among those indexes. As part of this work, we also describe a bitmap-index-based evaluation algorithm for selection queries that represents an improvement over earlier proposals. We believe that this study offers a useful first set of guidelines for physical database design using bitmap indexes.

In several working environments, production involves repeated executions of certain procedures. A workflow describes the individual tasks performed in these procedures and their interrelationships. Current workflow management systems (WFMSs) use a database management system (DBMS) to store task descriptions, and implement all workflow functionality in modules that run on top of the DBMS. Motivated by scientific workflows, we propose a much more DBMS-centric architecture, in which conventional database technology provides much of the desired scientific WFMS functionality. A key element of our approach is viewing the workflow as a web of data objects interconnected with active links that carry process descriptions. The workflow is fully defined as a database schema, and its execution is the gradual buildup of an instance of this schema through the active object links. For our work, we use the modeling and querying tools of Horse, the object-oriented DBMS that we have developed in the context of the Zoo Desktop Experiment Management Environment.

The notion of when two schemas are equivalent is fimdamental to database design, schema integration, and data model translation.An important notion of schema equivalence, query equivalence was introduced in [3], and used to evaluate the correctness of schema transformations.The logically equivalent notion of calculous equivalence, as well as three progressively weaker notions of schema equivalence were introduced in 1984 by Hull [9, lo], who showed that two schemas with no dependencies are equivalent (under all four notions of equivalence) if and only if they are identical (up to renaming and re-ordering of attributes and relations).Hull also conjectured that the same result holds for schemas with primary keys.In this work, we resolve the conjecture in the affirmative for the case of query equivalence based on mappings using conjunctive relational queries with equality selections.'This is a Massive Digital Data Systems (MDDS) project sponsored by the Advanced Research and Development Committee of the Community Management Staff.

DIAS

We have studied the needs of a wide range of experimental disciplines, developed solutions to some of the basic problems in experiment management and made significant progress towards implementing a simple desktop experiment management environment (DEME) called Zoo. Our work has proceeded in a tight loop between developing generic experiment management technology that is implemented in a generic tool, installing customized enhancements of the tool that constitute full systems [complete customized desktop experiment management systems (CDEMSs)] in laboratories of interest, and using the provided feedback to guide our research directions. In this paper, we first outline the overall architecture of Zoo and then discuss a particular experiment.

Scheduling query execution plans is an important component of query optimization in parallel database systems. The problem is particularly complex in a shared-nothing execution environment, where each system node represents a collection of time-shareable resources (e.g., CPU(s), disk(s), etc.) and communicates with other nodes only by message-passing. Significant research effort has concentrated on only a subset of the various forms of intra-query parallelism so that scheduling and synchronization is simplified. In addition, most previous work has focused its attention on one-dimensional models of parallel query scheduling, effectively ignoring the potential benefits of resource sharing. In this paper, we develop an approach that is more general in both directions, capturing all forms of intra-query parallelism and exploiting sharing of multi-dimensional resource nodesamong concurrent plan operators. This allows scheduling a set of independent query tasks (i.e., operator pipelines) to ...

Many commercial database systems maintain histograms to summarize the contents of relations and permit efficient estimation of query result sizes and access plan costs. Although several types of histograms have been proposed in the past, there has never been a systematic study of all histogram aspects, the available choices for each aspect, and the impact of such choices on histogram effectiveness. In this paper, we provide a taxonomy of histograms that captures all previously proposed histogram types and indicates many new possibilities. We introduce novel choices for several of the taxonomy dimensions, and derive new histogram types by combining choices in effective ways. We also show how sampling techniques can be used to reduce the cost of histogram construction. Finally, we present results from an empirical study of the proposed histogram types used in selectivity estimation of range predicates and identify the histogram types that have the best overall performance. 1 Introduction...

The problem of translating database objects into a flat format to be written out in a flat Ascii file or, conversely, translating the contents of a file into a complex database object arises in several applications. It is especially important in scientific database applications, where file-based communication with external programs (e.g., visualization packages or model simulations) is very common. We introduce Frog, a visual tool that can be used to specify translations between database objects and flat files, requiring no programming by the user. The tool can deal with objects of arbitrary complexity, without the object complexity being directly reflected in the complexity of the corresponding visual interaction. Based on the visual actions of the user, the tool stores enough information in a map-file, whose contents are used at run-time by another tool, Turtle, to translate any chosen database object into the appropriate file layout. The tool has been developed as part of the ZOO desktop experiment management environment and has been used by a few experimental scientists with success.

Many current database systems use histograms to approximate the frequency distribution of values in the attributes of relations and based on them estimate query result sizes and access plan costs. In choosing among the various histograms, one has to balance between two conflicting goals: optimality, so that generated estimates have the least error, and practicality, so that histograms can be constructed and maintained efficiently. In this paper, we present both theoretical and experimental results on several issues related to this trade-off. Our overall conclusion is that the most effective approach is to focus on the class of histograms that accurately maintain the frequencies of a few attribute values and assume the uniform distribution for the rest, and choose for each relation the histogram in that class that is optimal for a self-join query.

Conjwzctiuequeries are queries over a relational database and are at the core of relational query

When we, humans, talk to each other we have no trouble disambiguating what another person means, although our statements are almost never meticulously specified down to very last detail. We “fill in the gaps” using our common-sense knowledge about the world. We present a powerful mechanism that allows users of object-oriented database systems to specify certain types of ad-hoc queries in a manner closer to the way we pose questions to each other. Specifically, the system accepts as input queries with incomplete, and therefore ambiguous, path expressions. From them, it generates queries with fully-specified path expressions that are consistent with those given as input and capture what the user most likely meant by them. This is achieved by mapping the problem of path expression disambiguation to an optimal path computation (in the transitive closure sense) over a directed graph that represents the schema. Our method works by exploiting the semantics of the kinds of relationships in the schema and requires no special knowledge about the contents of the underlying database, i.e., it is domain independent. In a limited set of experiments with human subjects, the proposed mechanism was very successful in disambiguating incomplete path expressions.

We describe the design and implementation of BERMUDA, which is a loosely coupled system interfacing Prolog to the Britton-Lee Intelligent Database Machine (IDM-500). BERMUDA allows multiple concurrent Prolog processes, possibly running on different machines, to share a database. In addition, it preserves the semantics of Prolog programs and makes the use of the database system transparent to the user. We discuss several architectural issues faced by such systems and the approach adopted for each one in BERMUDA. We also present the performance results of a variety of experiments with the system. These include single-user benchmarks of BERMUDA against stand-alone Prolog and stand-alone IDM, detailed profiling of the costs of the modules of BERMUDA that shows the overhead imposed by the interface, and multiuser benchmarks of BERMUDA that show how the system behaves under heavier load. These experiments demonstrate the effectiveness of loosely coupled systems in general and of BERMUDA specifically. They also help in the identification of some aspects of the design and implementation of BERMUDA that could be improved.>

Many current relational database systems use some form of histograms to approximate the frequency distribution of values in the attributes of relations and on this basis estimate query result sizes and access plan costs.The errors that exist in the histogram approximations directly 01993

Several graph-based algorithms have been proposed in the literature to compute the transitive closure of a directed graph. We develop two new algorithms (Basic_TC and Gobal_DFTC) and compare the performance of their implementations in a disk-based environment with a well-known graph-based algorithm proposed by Schmitz. Our algorithms use depth-first search to traverse a graph and a technique called marking to avoid processing some of the arcs in the graph. They compute the closure by processing nodes in reverse topological order, building descendent sets by adding the descendent sets of children. While the details of these algorithms differ considerably, one important difference among them is the time at which descendent set additions are performed. Basic_TC, results in superior performance. The first reason is that early additions result in larger descendent set sizes on the average over the duration of the execution, thereby causing more I/O; very often this turns out to more than offset the gains of not having to fetch certain sets again to add them. The second reason is that information collected in the first pass can be used to apply several optimizations in the second pass. To the extent possible, we also adapt these algorithms to perform path computations. Again, our performance comparison confirms the trends seen in reachability queries. Taken in conjunction with another performance study our results indicate that all graph-based algorithms significantly outperform other types of algorithms such as Seminaive and Warren.

In this paper, we identify some of the fundamental issues that must be addressed in designing a desktop Experiment Management System (EMS). We develop an abstraction of the set of activities performed by scientists throughout the course of an experimental study, and based on that abstraction we propose an EMS architecture that can support all such activities. The proposed EMS architecture is centered around the extensive use of conceptual schemas, which express the structure of information in experimental studies. Schemas are called to play new roles that are not usually found in traditional database systems. We provide a detailed exposition of these new roles and describe certain characteristics that the data model of the EMS must have in order for schemas expressed in it to successfully play these roles. Finally, we present the specifics of our own effort to develop an EMS, focusing on the main features of the data model of the system, which we have developed based on the needs of experiment management.

This paper examines the idea of incorporating machine learning algorithms into a database system for monitoring its stream of incoming queries and generating hierarchies with the most important concepts expressed in those queries. The goal is for these hierarchies to provide valuable input to the database administrator for dynamically modifying the physical and external schemas of a database for improved system performance and user productivity. The criteria for choosing the appropriate learning algorithms are analyzed, and based on them, two such algorithms, UNIMEM and COBWEB, are selected as the most suitable ones for the task. Standard UNIMEM and COBWEB implementations have been modified to support queries as input. Based on the results of experiments with these modified implementations, the whole approach appears to be quite promising, expecially if the concept hierarchy from which the learning algorithms start their processing is initialized with some of the most obvious concepts captured in the database.

yannisQcs.wise.edu Query optimizers of current relational database systems use several statistics maintained by the system on the contents of the database to decide on the most efficient access plan for a given query. These statistics contain errors that transitively affect many estimates derived by the optimizer. We present a formal framework based on which the principles of this error propagation can be studied. Within this framework, we obtain several ana-lytic results on how the error propagates in general, as well as in the extreme and average cases. We also pro-vide results on guarantees that the database system can make based on the statistics that it maintains. Finally, we discuss some promising approaches to controlling the error propagation and derive several interesting proper-ties of them. 1

We present a combination of analytical and experimental results that shed some light into the shape of the cost function of the strategy spaces that query optimizers must deal with.These are the space that includes only left-deep trees and the space that includes koth deep and bushy trees.We conclude that the cost functions of both spaces essentially form a "well" but of a distinctly different quality.Based on this result, we discuss how Iterative Improvement, Simulated Annealing, and Two Phase Optimization perform on these spaces.We conclude that the space of both deep and bushy trees is easier to optimize than the space of left-deep trees alone.

Query optimization for relational database systems is a combinatorial optimization problem, which makes exhaustive search unacceptable as the query size grows. Randomized algorithms, such as Simulated Annealing (SA) and Iterative Improvement (II), are viable alternatives to exhaustive search. We have adapted these algorithms to the optimization of project-select-join queries. We have tested them on large queries of various types with different databases, concluding that in most cases SA identifies a lower cost access plan than II. To explain this result, we have studied the shape of the cost function over the solution space associated with such queries and we have conjectured that it resembles a 'cup' with relatively small variations at the bottom. This has inspired a new Two Phase Optimization algorithm, which is a combination of Simulated Annealing and Iterative Improvement. Experimental results show that Two Phase Optimization outperforms the original algorithms in terms of both output quality and running time.

In the majority of research work done on logic programming and deductive databases, it is assumed that the set of rules defined by the user is consistent, i.e., that no contradictory facts can be inferred by the rules. In this paper, we address the problem of resolving conflicts of rules that assign values to virtual attributes. We devise a general framework for the study of the problem, and we propose an approach that subsumes all previously suggested solutions. Moreover, it suggests several additional solutions, which very often capture the semantics of the data more accurately than the known approaches. Finally, we address the issue of how to index rules so that conflicts are resolved efficiently, i.e., only one of the applicable rules is processed at query time.

As the size and complexity of processing and manufacturing systems increases, the need for Database Management Systems (DBMS) that meet the special needs of studies that experiment with such systems becomes more current. System analysts who study the performance of modern processing systems have to manipulate large amounts of data in order to profile the behavior of the system. They have to identify the relationship between the properties of a compound system and a wide spectrum of performance metrics. In a recent study in which we have analyzed a set of distributed concurrency control algorithms, we performed more than 1400 simulation experiments. Each experiment was characterized by more than 6000 input parameters and generated more than 400 output values. It is thus clear that powerful means for defining the structure and properties of complex systems are needed, as well as efficient tools to retrieve the data accumulated in the course of the study. We are currently engaged in an effort to develop and implement the DELAB simulation laboratory that aims to provide such means and tools for simulation studies.

Query optimizers of future database management systems are likely to face large access plan spaces in their task. Exhaustively searching such access plan spaces is unacceptable. We propose a query optimization algorithm based on simulated annealing, which is a probabilistic hill climbing algorithm. We show the specific formulation of the algorithm for the case of optimizing complex non-recursive queries that arise in the study of linear recursion. The query answer is explicitly represented and manipulated within the closed semiring of linear relational operators. The optimization algorithm is applied to a state space that is constructed from the equivalent algebraic forms of the query answer. A prototype of the simulated annealing algorithm has been built and few experiments have been performed for a limited class of relational operators. Our initial experience is that, in general, the algorithm converges to processing strategies that are very close to the optimal. Moreover, the traditional processing strategies (e.g., the semi-naive evaluation) have been found to be, in general, suboptimal.