The structure of the ever increasing large RDF repositories is too complex to allow non-expert users extract useful information from them. Keyword search is an interesting alternative but in the context of RDF graph data, where query answers are RDF graph fragments, itfaces two major problems: the query quality answer problem and the result computation algorithm scalability problem. In this paper we focus on empowering keyword search on RDF data by exploiting personalized information. We proposean original approach which exploits the structural summary of the RDF graph to generate pattern graphs for the input keyword query. Pattern graphs are structured conjunctive queries and are seen as possible interpretations of the unstructured keyword query. Personalized information is represented as collections of profile graphs, a concept similar to pattern graphs. The ran king of the results is achieved by measuring graph similarity between the user profile graph and the generated pattern graphs. Novel similarity metrics have been introduced which consider intrinsic and extrinsic similarity and take into account both structural and semantic characteristics of the pattern and profile graphs. Effectiveness and efficiency experimental results show that our approach can tackle the two major problems that hinder the widespread use of keyword search on RDF data.

Keyword search is the most popular querying technique on semistructured data. Keyword queries are simple and convenient. However, as a consequence of their imprecision, there is usually a huge number of candidate results of which only very few match the user’s intent. Unfortunately, the existing semantics for keyword queries are ad-hoc and they generally fail to “guess” the user intent. Therefore, the quality of their answers is poor and the existing algorithms do not scale satisfactorily. In this paper, we introduce the novel concept of cohesive keyword queries for tree data. Intuitively, a cohesiveness relationship on keywords indicates that they should form a cohesive whole in a query result. Cohesive keyword queries allow term nesting and keyword repetition. Cohesive keyword queries bridge the gap between flat keyword queries and structured queries. Although more expressive, they are as simple as flat keyword queries and not require any schema knowledge. We provide formal semantics for cohesive keyword queries and rank query results on the proximity of the keyword instances. We design a stack based algorithm which efficiently evaluates cohesive keyword queries. Our experiments demonstrate that our approach outperforms in quality previous filtering semantics and our algorithm scales smoothly on queries of even 20 keywords on large datasets.

Finding interesting tree patterns hidden in large datasets is a central topic in data mining with many practical applications. Unfortunately, previous contributions have focused almost exclusively on mining-induced patterns from a set of small trees. The problem of mining homomorphic patterns from a large data tree has been neglected. This is mainly due to the challenging unbounded redundancy that homomorphic tree patterns can display. However, mining homomorphic patterns allows for discovering large patterns which cannot be extracted when mining induced or embedded patterns. Large patterns better characterize big trees which are important for many modern applications in particular with the explosion of big data. In this paper, we address the problem of mining frequent homomorphic tree patterns from a single large tree. We propose a novel approach that extracts non-redundant maximal homomorphic patterns. Our approach employs an incremental frequency computation method that avoids the costly enumeration of all pattern matchings required by previous approaches. Matching information of already computed patterns is materialized as bitmaps, a technique that not only minimizes the memory consumption, but also the CPU time. Our contribution also includes an optimization technique which can further reduce the search space of homomorphic patterns. We conducted detailed experiments to test the performance and scalability of our approach. The experimental evaluation shows that our approach mines larger patterns and extracts maximal homomorphic patterns from real and synthetic datasets outperforming state-of-the-art embedded tree mining algorithms applied to a large data tree.

Developing and exploiting flexible techniques for optimizing the evaluation of queries over loosely structured data (e.g. tree or graph databases) is of crucial importance for modern database applications. In this context, we consider a new type of views which can be materialized as compressed bitmaps over tree data. We introduce the concept of view structural template to define classes of views. We then define and address a novel view selection problem (called view class selection (VCS) problem) where the goal is to select classes of bitmap views in order to optimize the overall evaluation cost of all tree pattern queries (TPQs) that can be issued against a database while satisfying a space constraint and ensuring that all the TPQs can be answered using exclusively the materialized views. We show that the VCS problem is NP-hard and we design two heuristic greedy algorithms which iteratively generate new batches of candidate view classes and make them available for selection. Each algorithm uses a different view class expansion technique to enable the systematic generation of candidate view classes from classes with smaller templates. We run extensive experiments to evaluate both the effectiveness of the algorithms and their efficiency on real, benchmark and synthetic datasets. Our algorithms are able to suggest high quality selections of view classes in a reasonable amount of time.

XML query languages typically allow the specification of structural patterns using XPath. Usually, these structural patterns are in the form of trees (Tree-Pattern Queries-TPQs). Finding the occurrences of such patterns in an XML tree is a key operation in XML query evaluation. The multiple previous algorithms presented for this operation focus mainly on the evaluation of tree-pattern queries. Recently, requirements for flexible querying of XML data have motivated the consideration of query classes that are more expressive and flexible than TPQs for which efficient nonmain-memory evaluation algorithms are not known. In this paper, we consider a class of queries, called Partial Tree-Pattern Queries (PTPQs), which generalize and strictly contain TPQs. PTPQs represent a broad fragment of XPath which is very useful in practice. In order to process PTPQs, we introduce a set of sound and complete inference rules to characterize structural relationship derivation. We provide necessary and sufficient conditions for detecting query unsatisfiability and node redundancy. We also show that PTPQs can be represented as directed acyclic graphs augmented with the “same-path” constraints. In order to leverage existing efficient evaluation algorithms for less expressive classes of queries, we design two approaches that evaluate a PTPQ by decomposing it into a set of simpler queries: algorithm IndexTPQGen, exploits a structural summary of the XML data and evaluates a PTPQ by generating an equivalent set of TPQs and unioning their answers. Algorithm PartialPathJoin decomposes the PTPQ into partial-path queries, and merge-joins their solutions. We also develop PartialTreeStack, an original polynomial time holistic algorithm for PTPQs. To the best of our knowledge, this is the first algorithm to support the evaluation of such a broad structural fragment of XPath in the inverted lists evaluation model. We provide a theoretical analysis of our algorithm and identify cases where it is asymptotically optimal. An extensive experimental evaluation shows that it is more efficient, robust, and stable than the other two and it outperforms a state-of-the art XQuery engine on PTPQs.

Answering queries using views is a well-established technique in databases. In this context, two outstanding problems can be formulated. The first one consists in deciding whether a query can be answered exclusively using one or multiple materialized views. Given the many alternative ways to compute the query from the materialized views, the second problem consists in finding the best way to compute the query from the materialized views. In the realm of XML, there is a restricted number of contributions in the direction of these problems due to the many limitations associated with the use of materialized views in traditional XML query evaluation models.

Query processing techniques for XML data have focused mainly on tree-pattern queries (TPQs). However, the need for querying XML data sources whose structure is very complex or not fully known to the user, and the need to integrate multiple XML data sources with different structures have driven, recently, the suggestion of query languages that relax the complete specification of a tree pattern. In order to implement the processing of such languages in current DBMSs, their containment problem has to be efficiently solved.

The streaming evaluation is a popular way of evaluating queries on XML documents. Besides its many advantages, it is also the only option for a number of important XML applications. Unfortunately, existing algorithms focus almost exclusively on tree-pattern queries (TPQs). Requirements for flexible querying of XML data have motivated recently the introduction of query languages that are more general and flexible than TPQs.

Finding the occurrences of structural patterns in XML data is a key operation in XML query processing. Existing algorithms for this operation focus almost exclusively on path-patterns or tree-patterns. Requirements in flexible querying of XML data have motivated recently the introduction of query languages that allow a partial specification of path-patterns in a query. In this paper, we focus on the efficient evaluation of partial path queries, a generalization of path pattern queries. Our approach explicitly deals with repeated labels (that is, multiple occurrences of the same label in a query).

XML query languages typically allow the specification of structural patterns of elements. Finding the occurrences of such patterns in an XML tree is the key operation in XML query processing. Many algorithms have been presented for this operation. These algorithms focus mainly on the evaluation of path-pattern or tree-pattern queries. In this paper, we define a partial path-pattern query language, and we address the problem of its efficient evaluation on XML data.

The wide adoption of XML has increased the interest of the database community on tree-structured data management techniques. Querying capabilities are provided through tree-pattern queries. The need for querying tree-structured data sources when their structure is not fully known, and the need to integrate multiple data sources with different tree structures have driven, recently, the suggestion of query languages that relax the complete specification of a tree pattern. In this paper, we use a query language which allows partial tree-pattern queries (PTPQs). The structure in a PTPQ can be flexibly specified fully, partially or not at all. To evaluate a PTPQ, we exploit index graphs which generate an equivalent set of "complete" tree-pattern queries.In order to process PTPQs, we need to efficiently solve the PTPQ satisfiability and containment problems. These problems become more complex in the context of PTPQs because the partial specification of the structure allows new, non-trivial, structural expressions to be derived from those explicitly specified in a PTPQ. We address the problem of PTPQ satisfiability and containment in the absence and in the presence of index graphs, and we provide necessary and sufficient conditions for each case. To cope with the high complexity of PTPQ containment in the presence of index graphs,we study a family of heuristic approaches for PTPQ containment based on structural information extracted from the index graph in advance and on-the-fly. We implement our approaches and we report on their extensive experimental evaluation and comparison.

Selecting a set of views for materialization is a required task in many current database and data warehousing applications including the design of a data warehouse, and the maintenance of multiple materialized views. The selected views can be materialized permanently or transiently depending on the specific view selection problem. The view selection algorithms are expensive due to the size of the search space of the problem.In this paper we propose an approach for generating candidate views for materialization for view selection problems based on the definition of the input queries. We also provide rewritings of the input queries using the generated candidate views. In generating candidate views, we do not apply costbased techniques but we try to maximize the operations in the views. Subsequently, view selection algorithms can exploit problem dependent cost functions to choose among the generated candidate views. Our approach is not restricted to a specific view selection problem. Compared to a previous one, it generates views that involve more relation occurrences (or operations) and can reduce the size of the search space which can be very large. We implement our approach and we report some experimental evaluation with comparison to previous works.

Nowadays, huge volumes of data, including scientific data, are organized or exported in tree-structured form. Querying capabilities are provided through tree-pattern queries. The need for integrating multiple data sources with different tree structures has driven, recently, the suggestion of query languages that relax the complete specification of a tree pattern. In this paper we adopt a query language with partially specified tree-pattern queries. A central feature of this type of queries is that the structure can be specified fully, partially, or not at all in a query. Important issues in query optimization require solving the query containment problem. We study the containment problem for partially specified tree-pattern queries. To support the evaluation of such queries, we use semantically rich constructs, called dimension graphs, which abstract structural information of the tree-structured data. We address the problem of query containment in the absence (absolute query containment) and in the presence (relative query containment) of dimension graphs, and we provide necessary and sufficient conditions for each type of query containment. We suggest a technique for relative query containment checking based on structural information extracted in advance from the dimension graph. Our approach is implemented and validated through extensive experimental evaluation.

Nowadays, huge volumes of data are organized or exported in a tree-structured form. Querying capabilities are provided through queries that are based on branching path expression. Even for a single knowledge domain structural differences raise difficulties for querying data sources in a uniform way. In this paper, we present a method for semantically querying tree-structured data sources using partially specified tree patterns. Based on dimensions which are sets of semantically related nodes in tree structures, we define dimension graphs. Dimension graphs can be automatically extracted from trees and abstract their structural information. They are semantically rich constructs that support the formulation of queries and their efficient evaluation. We design a tree-pattern query language to query multiple tree-structured data sources. A central feature of this language is that the structure can be specified fully, partially, or not at all in the queries. Therefore, it can be used to query multiple trees with structural differences. %and We study the derivation of structural expressions in queries by introducing a set of inference rules for structural expressions. We define two types of query unsatisfiability and we provide necessary and sufficient conditions for checking each of them. Our approach is validated through experimental evaluation.

The recent proliferation of XML-based standards and technologies for managing data on the Web demonstrates the need for effective and efficient management of tree-structured data. Querying tree-structured data is a challenging issue due to the diversity of the structural aspect in the same or in different trees. In this paper, we show how to evaluate queries on tree-structured data, called value trees. The formulation of these queries does not depend on the structure of a particular value tree. Our approach exploits semantic information provided by dimension graphs. Dimension graphs are semantically rich constructs that abstract the structural information of the value trees. We show how dimension graphs can be used to query efficiently value trees in the presence of structural differences and irregularities. Value trees and their dimension graphs are represented as XML documents. We present a method for transforming queries to XPath expressions to be evaluated on the XML documents. We also provide conditions for identifying strongly and weakly unsatisfiable queries. Finally, we conducted various experiments to compare our method for evaluating queries with one that does not exploit dimension graphs. Our results demonstrate the superiority of our approach.

Deciding which views to materialize is an important problem in the design of a Data Warehouse. Solving this problem requires generating a space of candidate view sets from which an optimal or near-optimal one is chosen for materialization. In this paper we address the problem of constructing this search space. This is an intricate issue because it requires detecting and exploiting common subexpressions among queries and views. Our approach suggests adding to the alternative evaluation plans of multiple queries views called closest common derivators (CCDs) and rewriting the queries using CCDs. A CCD of two queries is a view that is as close to the queries as possible and that allows both queries to be (partially or completely) rewritten using itself. CCDs generalize previous definitions of common subexpressions. Using a declarative query graph representation for queries we provide necessary and sufficient conditions for a view to be a CCD of two queries. We exploit these results to describe a procedure for generating all the CCDs of two queries and for rewriting the queries using each of their CCDs.

Multidimensional aggregation queries constitute the single most important class of queries for data warehousing applications and decision support systems. The bottleneck in the evaluation of these queries is the join of the usually huge fact table with the restricted dimension tables (star-join). Recently,a multidimensional hierarchical clustering schema for star schemas is suggested. Subsequently,query evaluation plans for multidimensional queries appeared that essentially implement a star join as a multidimensional range restriction. We present a number of transformations for such plans. The transformations place grouping/aggregation operations before joins and safely prune aggregated tuples. They can be applied at no or minimal extra I/O cost. We show how these transformations can be used to construct a new evaluation plan for grouping/aggregation queries over multidimensional hierarchically clustered schemas. The new plan improves previous results by grouping and aggregating tuples and by excluding aggregated tuples from further consideration at an early stage of the computation of a query.

On-line analytical processing (OLAP) is a technology that encompasses applications requiring a multidimensional and hierarchical view of data. OLAP applications often require fast response time to complex grouping/aggregation queries on enormous quantities of data. Commercial relational database management systems use mainly multiple one-dimensional indexes to process OLAP queries that restrict multiple dimensions. However, in many cases, multidimensional access methods outperform one-dimensional indexing methods.We present an architecture for multidimensional databases that are clustered with respect to multiple hierarchical dimensions. It is based on the star schema and is called CSB star. Then, we focus on heuristically optimizing OLAP queries over this schema using multidimensional access methods. Users can still formulate their queries over a traditional star scheme, which are then rewritten by the query processor over the CSB star. We exploit the different clustering features of the CSB star to efficiently process a class of typical OLAP queries. We detect special cases where the construction of an evaluation plan can be simplified and we discuss improvements of our technique.

A Data Warehouse (DW) is a large collection of data integrated from multiple distributed autonomous databases and other information sources. A DW can be seen as a set of materialized views defined over the remote source data. Until now research work on DW design is restricted to quantitatively selecting view sets for materialization. However, quality issues in the DW design are neglected. In this paper we suggest a novel statement of the DW design problem that takes into account quality factors. We design a DW system architecture that supports performance and data consistency quality goals. In this framework we present a high level approach that allows to check whether a view selection guaranteeing a data completeness quality goal also satisfies a data currency quality goal. This approach is based on an AND/OR dag representation for multiple queries and views. It also allows determining the minimal change propagation frequencies that satisfy the data currency quality goal along with the optimal query evaluation and change propagation plans. Our results can be directly used for a quality driven design of a DW.

Article A general framework for the view selection problem for data warehouse design and evolution Share on Authors: Dimitri Theodoratos Department of EE&CS, National Technical University of Athens, Greece Department of EE&CS, National Technical University of Athens, GreeceView Profile , Mokrane Bouzeghoub Laboratoire PRiSM Université de Versailles, France Laboratoire PRiSM Université de Versailles, FranceView Profile Authors Info & Claims DOLAP '00: Proceedings of the 3rd ACM international workshop on Data warehousing and OLAPNovember 2000 Pages 1–8https://doi.org/10.1145/355068.355309Online:01 November 2000Publication History 37citation1,787DownloadsMetricsTotal Citations37Total Downloads1,787Last 12 Months4Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Recently there is an important interest in On-Line Analytical Processing (OLAP) technology. In this context, in order to facilitate complex analysis, data are usually modeled multidimensionally where multiple hierarchies are associated with the dimensions. These multidimensional (MD) data structures are called data cubes. In the existing OLAP products, the user interaction is limited to one operation at a time. Further computing OLAP operations is very expensive since sequential scans are required. In this paper we provide a simple data model for MD databases, and a simple algebraic MD query language that permit the modeling of the principal OLAP operations. The MD query language allows the user to directly specify the result. Therefore, optimization techniques can be applied globally to the MD query evaluation. We state declarative conditions for answering queries on cubes using exclusively one or more precomputed queries (derived cubes). Then, we provide instance independent expressions that compute an MD query on a cube from derived cubes. These results can be used to increase availability of data and to improve MD query performance.