In the context of using big data to improve healthcare and life sciences and with a specific focus on drug discovery, we consider the problem of formulating biomedical mechanism-of-action (MOA) hypotheses that can explain how specific drugs treat specific diseases. Our aim is to enable scalable mining and interpretation of MOA hypotheses enabling drug discovery and repurposing on large-scale biomedical knowledge graphs (KGs).The approach that we introduce to address this problem centers on expert-guided generation of candidate MOA hypotheses in the form of regular-path KG patterns between the KG nodes for the entities of interest, such as drugs and diseases. We call those patterns that represent promising candidate MOAs functional path patterns (FPPs), and call the proposed approach FPP-Hunter. The results of a drug-disease case study that we have conducted with the biomedical KG ROBOKOP suggest that the proposed approach has the potential to address scalability challenges in forming promising MOA hypotheses using large-scale KGs, in drug repurposing and potentially beyond.

Knowledge graphs (KGs), with their flexible and expressive data model, are frequently used for management of large-scale data and knowledge in data-intensive domains, including business, healthcare, and biomedicine. In particular, the KG data representation enables extraction from KGs of various knowledge and insights, with a number of applications to date. One type of knowledge that can be extracted from KGs is relational knowledge, which is expressed as paths between pairs of KG nodes and can provide real-world explanations for domain connections between the entities or concepts of interest. In this paper we focus on the problem of ranking path-based explanations for KG queries in ways that would rank higher the paths that make more sense in the user-provided semantic context, effectively and efficiently on large-scale KGs.Toward addressing the problem, we introduce an approach called Semantics-Aware Path Ranking Algorithm (SAPRA). The SAPRA approach is designed to scale to very large KGs. It is broadly applicable to KG data and queries in a range of domains, leveraging the properties of entities and relationships within the given KG to recommend paths that most closely align with the user-provided semantic context. To further enhance the accuracy of the semantic interpretation of the user queries, SAPRA can adapt its behavior based on feedback from domain experts. SAPRA accepts as inputs KG queries and the associated semantic context in their purely syntactic form, which makes the approach domain agnostic. We report the results of an experimental evaluation of our implementation of SAPRA on the biomedical KGs ROBOKOP and DRKG. The results show promise for better path-ranking effectiveness and efficiency of the proposed approach against the state of the art on large-scale KGs, in the biomedical domain and potentially beyond.

In large-scale multidisciplinary consortia endeavors that address problems of research, industry, and public-good significance, it is typically a priority to integrate the heterogeneous data contributed by the consortia participants into a unified data representation. Knowledge graphs (KGs) are a typical choice for the data model of the resulting data repositories. To overcome potential issues with terminology misalignment, consortia commonly dedicate resources to the development of shared languages (vocabularies), with the intent of enabling diverse participants to understand and build on each other’s work. Our research focus in this paper is on the challenge of automating integration into unified KGs of diverse data that potentially use different terminology, with the help of the available shared languages to resolve terminology clashes.To address the challenge, we introduce a data-integration workflow called INTEGRATE-KG that is domain agnostic, yet domain aware through opportunities for the involvement of humans-in-the-loop. A key feature of the approach is in its use of the synonyms available for the shared languages to automate semantics-level terminology alignment across the individual data contributions after they have been submitted for integration. INTEGRATE-KG also includes a module for automatically enriching the available shared languages, with opportunities for domain experts to provide semantic corrections and feedback. We present the workflow, report on our experiences with applying it to experimental, survey, and shared-language data on phosphorus sustainability, and provide suggestions for involving domain experts in INTEGRATE-KG as humans-in-the-loop.

Knowledge graphs (KGs), with their flexible encoding of heterogeneous data, have been increasingly used in a variety of applications. At the same time, domain data are routinely stored in formats such as spreadsheets, text, or figures. Storing such data in KGs can open the door to more complex types of analytics, which might not be supported by the data sources taken in isolation. Giving domain experts the option to use a predefined automated workflow for integrating heterogeneous data from multiple sources into a single unified KG could significantly alleviate their data-integration time and resource burden, while potentially resulting in higher-quality KG data capable of enabling meaningful rule mining and machine learning.In this paper we introduce a domain-agnostic workflow called BUILD-KG for integrating heterogeneous scientific and experimental data from multiple sources into a single unified KG potentially enabling richer analytics. BUILD-KG is broadly applicable, accepting input data in popular structured and unstructured formats. BUILD-KG is also designed to be carried out with end users as humans-in-the-loop, which makes it domain aware. We present the workflow, report on our experiences with applying it to scientific and experimental data in the materials science domain, and provide suggestions for involving domain scientists in BUILD-KG as humans-in-the-loop.

Knowledge graphs have been growing in popularity in recent years, due to their successful use in many data-analytics and knowledge-discovery tasks. As the sizes of domain graphs continue to grow, they can become too large to be processed efficiently by downstream applications. It is thus indispensable in many cases to aim to address the efficiency issue by reducing knowledge-graph sizes via summarization. At the same time, to provide quality results, that is, to be effective, on the graph summaries, many downstream analytics and knowledge-discovery tasks require the summaries to retain as much information from the original graph as possible. It turns out that state-of-the-art data-reduction approaches may generate task-specific or lossy summaries, which may present challenges for the effectiveness of downstream analytics in some cases. As a result, it is important to study trade-offs between the performance and accuracy of graph summarizations for analytics and knowledge discovery.In this paper, in the scope of knowledge-graph size reduction via summarization, we consider the trade-off between the performance and accuracy of one type of knowledge-graph analytics, inference-rule mining, on the summarized graphs as compared with the original graphs. Toward addressing the tradeoff challenge, we introduce a domain- and task-independent knowledge-graph summarization approach called GAME for generating reduced abstract knowledge graphs from a given graph. Our preliminary experimental results suggest that our GAME approach can preserve as much information from the given (original) graph as possible for the purpose of rule mining, while potentially significantly improving the rule-mining efficiency. We anticipate that the knowledge-graph reduction provided by the proposed GAME approach can enable efficient, yet effective, results for diverse applications and use cases.

Querying large-scale knowledge graphs (KGs) can be difficult for users in real-life scenarios, in which formal graph query languages potentially present usability barriers. Query-By-Example (QBE) approaches, which allow users to specify their query intent with examples, have become an emerging trend to address this issue. However, existing QBE approaches either require user-specified examples to provide values of all the KG attributes, or may return incorrect formalizations of user query intent due to the lack of user interaction. In this paper we propose an approach called Knowledge Graph Intuitive Querier (KGIQ) that addresses both challenges on large-scale KGs by using novel scalable algorithms. Unlike existing approaches, KGIQ ensures correct translation of user-specified examples into formal executable graph queries by interacting with users in a lightweight manner. Our experimental results suggest that KGIQ can correctly formalize graph queries on large-scale KGs with the help of uncomplicated user interactions and a feedback loop to improve user experience, while consistently outperforming the state of the art in terms of efficiency and outcome quality.

Recently, knowledge graphs have seen a significant increase in popularity in a wide variety of domains, as they provide a basis for many data-analytics and knowledge-discovery approaches. At the same time, many knowledge graphs are not immediately usable due to their format, unreadable or missing data, and inaccessibility. These issues present barriers to the exploration and use of knowledge graphs for big data analytics and knowledge discovery. In this paper we present a workflow for domain- and task-sensitive curation of large-scale knowledge graphs, and detail our experience with implementing this workflow with the biomedical knowledge graph called Drug Repurposing Knowledge Graph (DRKG). The workflow aims to address usability-related issues of real-life knowledge graphs, by performing data setup and curation that align with the needs of specific tasks and domains. Recognizing that domain experts and anticipated users of a knowledge graph provide invaluable expertise regarding the desired graph format, the proposed workflow involves them as humans-in-the-loop. We present the processes required to execute the workflow, detail our experience in the biomedical domain with the use case of DRKG, and discuss the challenges and lessons learned throughout the experience. We anticipate that the proposed workflow and experiences will be applicable to other domains, and that our workflow will enable and encourage exploration and wider use of large-scale knowledge graphs, thereby improving big data analytics.

Knowledge-graph (KG) embeddings have emerged as a promise in addressing challenges faced by modern biomedical research, including the growing gap between therapeutic needs and available treatments. The popularity of KG embeddings in graph analytics is on the rise, due at least partially to the presumed semanticity of the learned embeddings. Unfortunately, the ability of a node neighborhood picked up by an embedding to capture the node's semantics may depend on the characteristics of the data. One of the reasons for this problem is that KG nodes can be promiscuous, that is, associated with a number of different relationships that are not unique or indicative of the properties of the nodes.

Obtaining answers to domain-specific questions over large-scale unstructured (text) data is an important component of data analytics in many application domains. As manual question answering does not scale to large text corpora, it is common to use information extraction (IE) to preprocess the texts of interest prior to posing the questions. This is often done by transforming text corpora into the knowledge-graph (KG) triple format that is suitable for efficient processing of the user questions in graph-oriented data-intensive systems.In a number of real-life scenarios, trustworthiness of the answers obtained from domain-specific texts is vital for downstream decision making. In this paper we focus on one critical aspect of trustworthiness, which concerns aligning with the given domain vocabularies (ontologies) those KG triples that are obtained from the source texts via IE solutions. To address this problem, we introduce a scalable domain-independent text-to-KG approach that adapts to specific domains by using domain ontologies, without having to consult external triple repositories. Our IE solution builds on the power of neural-based learning models and leverages feature engineering to distinguish ontology-aligned data from generic data in the source texts. Our experimental results indicate that the proposed approach could be more dependable than a state-of-the-art IE baseline in constructing KGs that are suitable for trustworthy domain question answering on text data.

Drug discovery is an important process used by biomedical experts to identify potential treatments for diseases. In its traditional form, the process requires significant expert time and manual effort. By encoding a wealth of information about relationships between drugs and diseases, modern large-scale biomedical knowledge graphs provide excellent opportunities to accelerate drug discovery, by automating aspects of the process. One opportunity is to use explainable fact-checking tools to generate explanations for hypothesized drug-disease treatment relationships in a given knowledge graph, with a reliability score assigned to each explanation. The explanations and their scores can then be used by experts to determine which drug-disease pairs to consider for clinical trials.In our collaboration with a biomedical team, we have found that existing explainable fact-checking tools are not necessarily helpful in drug discovery, as their explanation formats and evaluation metrics do not match well the requirements of scientific discovery in the biomedical domain. To address these challenges in using fact-checking tools in drug discovery, we introduce a scalable automated approach for generating explanations that are modeled after existing biomedical concepts and supplemented with data-supported evaluation metrics. Our explanations are based on knowledge-graph patterns, which are readily understood by biomedical experts. Our experimental results suggest that our proposed metrics are accurate and useful on largescale biomedical knowledge graphs, and our explanations are understandable and reasonable to experts doing drug discovery.

In real-life analytics-oriented information-integration projects, the processes of information curation and integration cannot be completely automated. Rather, in each large-scale project the key objectives include maximizing scalability and throughput, while at the same time keeping the processes manageable and productive for the human experts in the loop. In this paper, we describe our experience with addressing these major objectives in the process of building a scalable end-to-end data-extraction, integration, and analytics workflow in the domain of antimicrobial resistance (AMR). The workflow is built using open-source tools, with the aims of enhancing the efficiency and accuracy of data collection and integration, while involving an acceptable level of efforts by collaborative multidisciplinary teams of humans-in-the-loop. We present the components of the proposed workflow, outline the challenges encountered in its development and testing, and discuss the experiences and lessons learned in enabling AMR experts and data analysts to interact with the workflow, with some of the lessons potentially applicable to other application domains.

Modern applications often need to manage and analyze widely diverse datasets that span multiple data models [1], [2], [3], [4], [5]. Warehousing the data through Extract-Transform-Load (ETL) processes can be expensive in such scenarios. Transforming disparate data into a single data model may degrade performance. Further, curating diverse datasets and maintaining the pipeline can prove to be labor intensive. As a result, an emerging trend is to shift the focus to federating specialized data stores and enabling query processing across heterogeneous data models [6]. This shift can bring many advantages: First, systems can natively leverage multiple data models, which can translate to maximizing the semantic expressiveness of underlying interfaces and leveraging the internal processing capabilities of component data stores. Second, federated architectures support query-specific data integration with just-in-time transformation and migration, which has the potential to significantly reduce the operational complexity and overhead. Projects that focus on developing systems in this research area stem from various backgrounds and address diverse concerns, which could make it difficult to form a consistent view of the work in this area. In this survey, we introduce a taxonomy for describing the state of the art and propose a systematic evaluation framework conducive to understanding of query-processing characteristics in the relevant systems. We use the framework to assess four representative implementations: BigDAWG [7], [8], CloudMdsQL [9], [10], Myria [11], [12], and Apache Drill [13].

WaveCluster is an important family of grid-based clustering algorithms that are capable of finding clusters of arbitrary shapes. In this paper, we investigate techniques to perform WaveCluster while ensuring differential privacy.Our goal is to develop a general technique for achieving differential privacy on WaveCluster that accommodates different wavelet transforms.

Community detection in real-world graphs presents a number of challenges. First, even if the number of detected communities grows linearly with the graph size, it becomes impossible to manually inspect each community for value added to the application knowledge base. Mining for communities with query nodes as knowledge priors could allow for filtering out irrelevant information and for enriching end-users knowledge associated with the problem of interest, such as discovery of genes functionally associated with the Alzheimer's (AD) biomarker genes. Second, the data-intensive nature of community enumeration challenges current approaches that often assume that the input graph and the detected communities fit in memory. As computer systems scale, DRAM memory sizes are not expected to increase linearly, while technologies such as SSD memories have the potential to provide much higher capacities at a lower power-cost point, and have a much lower latency than disks. Out-of-core algorithms and/or database-inspired indexing could provide an opportunity for different design optimizations for query-driven community detection algorithms tuned for emerging architectures. Therefore, this work addresses the need for query-driven and memory-efficient community detection. Using maximal cliques as the community definition, due to their high signal-to-noise ratio, we propose and systematically compare two contrasting methods: indexed-based and out-of-core. Both methods improve peak memory efficiency as much as 1000X compared to the state-of-the-art. However, the index-based method, which also has a 10-to-100-fold run time reduction, outperforms the out-of-core algorithm in most cases. The achieved scalability enables the discovery of diseases that are known to be or likely associated with Alzheimer's when the genome-scale network is mined with AD biomarker genes as knowledge priors.

No abstract available.

The problems of query containment, equivalence, and minimization are fundamental problems in the context of query processing and optimization. In their classic work [2] published in 1977, Chandra and Merlin solved the three problems for the language of conjunctive queries (CQ queries) on relational data, under the "set-semantics" assumption for query evaluation. While the results of [2] have been very influential in database research, it was recognized long ago that the set semantics does not correspond to the semantics of the standard commercial query language SQL. Alternative semantics, called bag and bag-set semantics, have been studied since 1993; Chaudhuri and Vardi in [5] outlined necessary and sufficient conditions for equivalence of CQ queries under these semantics. (The problems of containment of CQ bag and bag-set queries remain open to this day.) More recently, Cohen [7, 8] introduced a formalism for treating (generalizations of) CQ queries evaluated under each of set, bag, and bag-set semantics uniformly as special cases of the more general combined semantics. This formalism provides tools for studying broader classes of practical SQL queries, specifically important types of queries that arise in on-line analytical processing (OLAP). Cohen in [8] provides a sufficient condition for equivalence of (generalizations of) combined-semantics CQ queries, as well as sufficient and necessary equivalence conditions for several proper sublanguages of the query language of [8]. To the best of our knowledge, no results on minimization of CQ queries beyond set-semantics queries have been reported in the literature.

We consider data exchange for XML documents: given source and target schemas, a mapping between them, and a document conforming to the source schema, construct a target document and answer target queries in a way that is consistent with source information. The problem has primarily been studied in the relational context, in which data-exchange systems have also been built. Since many XML documents are stored in relations, it is natural to consider using a relational system for XML data exchange. However, there is a complexity mismatch between query answering in relational and XML data exchange, which indicates that restrictions have to be imposed on XML schemas and mappings, and on XML shredding schemes, to make the use of relational systems possible. We isolate a set of five requirements that must be fulfilled in order to have a faithful representation of the XML data-exchange problem by a relational translation. We then demonstrate that these requirements naturally suggest the inlining technique for dataexchange tasks. Our key contribution is to provide shredding algorithms for schemas, documents, mappings and queries, and demonstrate that they enable us to correctly perform XML data-exchange tasks using a relational system.

The problem of rewriting a query using a materialized view is studied for a well known fragment of XPath that includes the following three constructs: wildcards, descendant edges and branches. In earlier work, determining the existence of a rewriting was shown to be coNP-hard, but no tight complexity bound was given. While it was argued that Σ3p is an upper bound, the proof was based on results that have recently been refuted. Consequently, the exact complexity (and even decidability) of this basic problem has been unknown, and there have been no practical rewriting algorithms if the query and the view use all the three constructs mentioned above.

We consider the problem of finding equivalent minimal-size reformulations of SQL queries in presence of embedded dependencies [1]. Our focus is on select-project-join (SPJ) queries with equality comparisons, also known as safe conjunctive (CQ) queries, possibly with grouping and aggregation. For SPJ queries, the semantics of the SQL standard treats query answers as multisets (bags), whereas the stored relations are treated either as sets, which is called bag-set semantics, or as bags, which is called bag semantics. (Under set semantics, both query answers and stored relations are treated as sets.)

The problem of decentralized data sharing is relevant for a wide range of applications and is still a source of major theoretical and practical challenges, in spite of many years of sustained research in information integration. We focus on the challenge of efficiency of query evaluation in information-integration systems, with the objective of developing query-processing strategies that are widely applicable and easy to implement in real-life applications. In our algorithms we take into account important features of today's data-sharing applications, namely: XML as likely interface to or representation for data sources; potential for information overlap across data sources; and the need for inter-source processing (i.e., joins of data across data sources) in many applications.

Selecting and precomputing indexes and materialized views, with the goal of improving query-processing performance, is an important part of database-performance tuning. The significant complexity of the view- and index-selection problem may result in high total cost of ownership for database systems. In this paper, we develop efficient methods that deliver user-specified quality of the set of selected views and indexes when given view- and index-based plans as problem inputs. Here, quality means proximity to the globally optimum performance for the input query workload given the input query plans. Our experimental results and comparisons on synthetic and benchmark instances demonstrate the competitiveness of our approach and show that it provides a winning combination with end-to-end view- and index-selection frameworks such as those of [1, 2].

In on-line analytical processing (OLAP), precomputing (materializing as views) and indexing auxiliary data aggregations is a common way of reducing query-evaluation time costs for important data-analysis queries. We consider an OLAP view- and index-selection problem stated as an optimization problem, where (i) the inputs include the data-warehouse schema, a set of data-analysis queries of interest, and a storage-limit constraint, and (ii) the output is a set of views and indexes that minimizes the costs of the input queries, subject to the storage limit. While greedy and other heuristic strategies for choosing views or indexes might help to some extent in improving the costs, it is highly nontrivial to arrive at a globally optimum solution, one that reduces the processing costs of typical OLAP queries as much as is theoretically possible. In fact, as observed in [17] and to the best of our knowledge, there is no known approximation algorithm for OLAP view or index selection with nontrivial performance guarantees.

Querying large-scale graph-structured data with twig patterns is attracting growing interest. Generally, a twig pattern could have an extremely large, potentially exponential, number of matches in a graph. Retrieving and returning to the user this many answers may both incur high computational overhead and overwhelm the user.

In this paper we address the problem of evaluating XPath queries over streaming XML data. We consider a practical XPath fragment called Univariate XPath, which includes the commonly used '/' and '//' axes and allows *-node tests and arbitrarily nested predicates. It is well known that this XPath fragment can be efficiently evaluated in O(|D||Q|) time in the non-streaming environment, where |D| is the document size and |Q| is the query size. However, this is not necessarily true in the streaming environment, since streaming algorithms have to satisfy stricter requirement than non-streaming algorithms, in that all data must be read sequentially in one pass. Therefore, it is not surprising that state-of-the-art stream-querying algorithms have higher time complexity than O(|D||Q|).

Extensible markup language (XML) is emerging as a de facto standard for information exchange among various applications on the World Wide Web. There has been a growing need for developing high-performance techniques to query large XML data repositories efficiently. One important problem in XML query processing is twig pattern matching, that is, finding in an XML data tree D all matches that satisfy a specified twig (or path) query pattern Q. In this survey, we review, classify, and compare major techniques for twig pattern matching. Specifically, we consider two classes of major XML query processing techniques: the relational approach and the native approach. The relational approach directly utilizes existing relational database systems to store and query XML data, which enables the use of all important techniques that have been developed for relational databases, whereas in the native approach, specialized storage and query processing systems tailored for XML data are developed from scratch to further improve XML query performance. As implied by existing work, XML data querying and management are developing in the direction of integrating the relational approach with the native approach, which could result in higher query processing performance and also significantly reduce system reengineering costs.

We study optimization of relational queries using materialized views, where views may be regular or restructured. In a restructured view, some data from the base table(s) are represented as metadata - that is, schema information, such as table and attribute names - or vice versa.Using restructured views in query optimization opens up a new spectrum of views that were not previously available, and can result in significant additional savings in query-evaluation costs. These savings can be obtained due to a significantly larger set of views to choose from, and may involve reduced table sizes, elimination of self-joins, clustering produced by restructuring, and horizontal partitioning.In this paper we propose a general query-optimization framework that treats regular and restructured views in a uniform manner and is applicable to SQL select-project-join queries and views with or without aggregation. Within the framework we provide (1) algorithms to determine when a view (regular or restructured) is usable in answering a query, and (2) algorithms to rewrite a query using usable views.Semantic information, such as knowledge of the key of a view, can be used to further optimize a rewritten query. Within our general query-optimization framework, we develop techniques for determining the key of a (regular or restructured) view, and show how this information can be used to further optimize a rewritten query. It is straightforward to integrate all our algorithms and techniques into standard query-optimization algorithms.

We study the problem of finding efficient equivalent view-based rewritings of relational queries, focusing on query optimization using materialized views under the assumption that base relations cannot contain duplicate tuples. A lot of work in the literature addresses the problems of answering queries using views and query optimization. However, most of it proposes solutions for special cases, such as for conjunctive queries (CQs) or for aggregate queries only. In addition, most of it addresses the problems separately under set or bag-set semantics for query evaluation, and some of it proposes heuristics without formal proofs for completeness or soundness. In this paper we look at the two problems by considering CQ/A queries - that is, both pure conjunctive and aggregate queries, with aggregation functions SUM, COUNT, MIN, and MAX; the DISTINCT keyword in (SQL versions of) our queries is also allowed. We build on past work to provide algorithms that handle this general setting. This is possible because recent results on rewritings of CQ/A queries [1, 8] show that there are sound and complete algorithms based on containment tests of CQs.Our focus is that our algorithms are efficient as well as sound and complete. Besides the contribution we make in putting and addressing the problems in this general setting, we make two additional contributions for bag-set and set semantics. First, we propose efficient sound and complete tests for equivalence of CQ/A queries to rewritings that use overlapping views (the algorithms are complete with respect to the language of rewritings). These results apply not only to query optimization, but to all areas where the goal is to obtain efficient equivalent view-based query rewritings. Second, based on these results we propose two sound algorithms, BDPV and CDPV, that find efficient execution plans for CQ/A queries in terms of materialized views. Both algorithms extend the cost-based query-optimization approach of System R [19]. The efficient sound algorithm BDPV is also complete in some cases, whereas CDPV is sound and complete for all CQ/A queries we consider. We present a study of the completeness-efficiency tradeoff in the algorithms, and provide experimental results that show the viability of our approach and test the limits of query optimization using overlapping views.

Abstract. We consider a workload of aggregate queries and investigate the problem of selecting views that (1) provide equivalent rewritings for all queries, and (2) are optimal, in that the cost of evaluating the query workload is minimized. We consider conjunctive views and rewritings, with or without aggregation; in each rewriting, only one view contributes to computing the aggregated query output. We look at query rewriting using existing views and at view selection. In the query-rewriting problem, we give sufficient and necessary conditions for a rewriting to exist. For view selection, we prove complexity results. Finally, we give algorithms for obtaining rewritings and selecting views. 1

In this paper we study the following problem. Given a database and a set of queries, we want to find, in advance, a set of views that can compute the answers to the queries, such that the size of the viewset (i.e., the amount of space, in bytes, required to store the viewset) is minimal on the given database. This problem is important for many applications such as distributed databases, data warehousing, and data integration. We explore the decidability and complexity of the problem for workloads of conjunctive queries. We show that results differ significantly depending on whether the workload queries have self-joins. If queries can have self-joins, then a disjunctive viewset can be a better solution than any set of conjunctive views. We show that the problem of finding a minimal-size disjunctive viewset is decidable, and give an upper bound on its complexity. If workload queries cannot have self-joins, there is no need to consider disjunctive viewsets, and we show that the problem is in NP. We describe a very compact search space of conjunctive views, which contains all views in at least one optimal disjunctive viewset. We give a dynamic-programming algorithm for finding minimal-size disjunctive viewsets for queries without self-joins, and discuss heuristics to make the algorithm efficient.

The view-selection problem is to design and materialize a set of views over a database schema, such that the choice of views minimizes the cost of evaluating the selected workload of queries, and the combined size of the materialized views does not exceed a prespecified storage limit. Important applications of the view-selection problem include query optimization, data warehouse design, and information integration.We consider the view-selection problem in relational databases, for conjunctive queries and views. Suppose somebody wants to design a view-selection algorithm that outputs a polynomial number of views for all query workloads and storage limits and produces optimal selections of views independently of actual database contents. In previous work it was shown that it is impossible to design such an algorithm when the product (as for nested-loop joins) cost model is used. That is, there exist databases for which the number of views in an optima] viewset is exponential in the size of the database schema and query workload. As a consequence, under the product-cost model the view-selection problem has an exponential-time lower bound.Efficient join algorithms have a cost that is proportional to the sum of the sizes of the input and output relations. In this paper we prove that under the more practical sum-cost model, the view-selection problem also has an exponential time lower bound. As a consequence, under the sum-cost model it is also impossible to come up with a view-selection algorithm that outputs a polynomial number of views for all query workloads and databases, yet produces optimal selections of views.