Search

Process-oriented data analysis techniques allow organizations to understand how their processes operate, where modifications are needed and where enhancements are possible. A recurrent task in any process analysis technique is querying. Process data querying allows analysts to easily explore the data with the intent of getting insights about the execution of business processes. The current generation of process query languages targets data scientists. However, there is a need to a query language to support domain analysts who may be inexperienced with database technologies. This paper addresses this challenge by proposing a natural language interface that assists the end-users in querying the stored event data. The interface takes a natural language query from the user, automatically constructs a corresponding structured query to be executed over the stored event data. We use graph based storage techniques, namely labeled property graphs, which allow to explicitly model event data relationships. As an executable query language, we use the Cypher language which is widely used for querying property graphs. The approach has been implemented and evaluated using two publicly available event logs. • We proposed a natural language interface for querying process execution data from natural language. • We presents a Labeled Graph metamodel for stroing process data. • We proposed a hybrid pipline to automatically constructing Cypher queries from natural language. • Our NLI system is hybrid and combines machine learning and rule-based approaches. • We defined a set of general intent patterns that are domain-independent. • We evaluated the proposed system with more than 530 natural language queries. [ABSTRACT FROM AUTHOR]

The recently proposed Geometric Monitoring (GM) method has provided a general tool for the distributed monitoring of arbitrary non-linear queries over streaming data observed by a collection of remote sites, with numerous practical applications. Unfortunately, GM-based techniques can suffer from serious scalability issues with increasing numbers of remote sites. In this paper, we propose novel techniques that effectively tackle the aforementioned scalability problems by exploiting a carefully designed sample of the remote sites for efficient approximate query tracking. Our novel sampling-based scheme utilizes a sample of cardinality proportional to N (compared to N for the original GM and its variants), where N is the number of sites in the network, to perform the monitoring process. Our extensive experimental evaluation and comparative analysis over a variety of real-life data streams demonstrates that our sampling-based techniques can significantly reduce the communication cost during distributed monitoring with controllable, predefined accuracy guarantees. In that, we manage to scale the monitoring of any given non-linear function on much higher network scales which had not been reached by any GM related method or variant so far. [ABSTRACT FROM AUTHOR]

We present a new graph compressor that works by recursively detecting repeated substructures and representing them through grammar rules. We show that for a large number of graphs the compressor obtains smaller representations than other approaches. Specific queries such as reachability between two nodes or regular path queries can be evaluated in linear time (or quadratic times, respectively), over the grammar, thus allowing speed-ups proportional to the compression ratio. [ABSTRACT FROM AUTHOR]

In recent years, many studies on computational linguistics have employed the Web as source for research. Specifically, the distribution of textual data in the Web is used to drive linguistic analyses in tasks such as information extraction, knowledge acquisition or natural language processing. For these purposes, commercial Web search engines are commonly used as the low-entry-cost way to access Web data and, more specifically, to estimate the distribution of the entity(ies) of interest from the hit count the search engines provide when querying such entities. Even though several studies have evaluated the effectiveness of Web search engines as information retrieval tools from the perspective of the end users, few authors have assessed the suitability of hit counts as research tools in computational linguistics; moreover, studies so far have focused on the most well-known search engines (typically Google, Bing and Yahoo!), and neglected potentially interesting alternatives that have recently surfaced. To fill this gap, in this work, we first compile and survey the general-purpose search engines that are currently available. Then, we evaluate the suitability of the hit counts they provide under several perspectives that are relevant for computational linguistics: flexibility of the query language, linguistic coherence, mathematical coherence and temporal consistency. The results of our survey show that, even though the choice of a particular search engine has been generally ignored by researchers relying on Web data, there are significant quality differences between the hit counts of current search engines, and that the most well-known and widely-used search engines do not provide the best results. In this respect, we also identify the search engines whose hit counts are best suited for research. [ABSTRACT FROM AUTHOR]

In the Big Data Era, the management of energy consumption by servers and data centers has become a challenging issue for companies, institutions, and countries. In data-centric applications, Database Management Systems are one of the major energy consumers when executing complex queries involving very large databases. Several initiatives have been proposed to deal with this issue, covering both the hardware and software dimensions. They can be classified in two main approaches assuming that either (a) the database is already deployed on a given platform, or (b) it is not yet deployed . In this study, we focus on the first set of initiatives with a particular interest in physical design, where optimization structures (e.g., indexes, materialized views) are selected to satisfy a given set of non-functional requirements such as query performance for a given workload. In this paper, we first propose an initiative, called Eco-Physic , which integrates the energy dimension into the physical design when selecting materialized views, one of the redundant optimization structures. Secondly, we provide a multi-objective formalization of the materialized view selection problem, considering two non-functional requirements: query performance and energy consumption while executing a given workload. Thirdly, an evolutionary algorithm is developed to solve the problem. This algorithm differs from the existing ones by being interactive, so that database administrators can adjust some energy sensitive parameters at the final stage of the algorithm execution according to their specifications. Finally, intensive experiments are conducted using our mathematical cost model and a real device for energy measurements. Results underscore the value of our approach as an effective way to save energy while optimizing queries through materialized views structures. [ABSTRACT FROM AUTHOR]

This paper proposes a category- and selection-enabled nearest neighbor join (NNJ) between relation r and relation s , with similarity on T and support for category attributes C and selection predicate θ . Our solution does not suffer from redundant fetches and index false hits , which are the main performance bottlenecks of current nearest neighbor join techniques. A category-enabled NNJ leverages the category attributes C for query evaluation. For example, the categories of relation r can be used to limit relation s accessed at most once. Solutions that are not category-enabled must process each category independently and end up fetching, either from disk or memory, the blocks of the input relations multiple times. A selection-enabled NNJ performs well independent of whether the DBMS optimizer pushes the selection down or evaluates it on the fly. In contrast, index-based solutions suffer from many index false hits or end up in an expensive nested loop. Our solution does not constrain the physical design, and is efficient for row- as well as column-stores. Current solutions for column-stores use late materialization, which is only efficient if the data is clustered on the category attributes C . Our evaluation algorithm finds, for each outer tuple r , the inner tuples that satisfy the equality on the category and have the smallest distance to r with only one scan of both inputs. We experimentally evaluate our solution using a data warehouse that manages analyses of animal feeds. [ABSTRACT FROM AUTHOR]

The generic model query language GMQL is designed to query collections of conceptual models created in arbitrary graph-based modelling languages. Querying conceptual models means searching for particular model subgraphs that comply with a predefined pattern query. Such a query specifies the structural and semantic properties of the model fragment to be returned. In this paper, we derive requirements for a generic model query language from the literature and formally specify the language’s syntax and semantics. We conduct an analysis of GMQL׳s theoretical and practical runtime performance concluding that it returns query results within satisfactory time. Given its generic nature, GMQL contributes to a broad range of different model analysis scenarios ranging from business process compliance management to model translation and business process weakness detection. As GMQL returns results with acceptable runtime performance, it can be used to query large collections of hundreds or thousands of conceptual models containing not only process models, but also data models or organizational charts. In this paper, we furthermore evaluate GMQL against the backdrop of existing query approaches thereby carving out its advantages and limitations as well as pointing toward future research. [ABSTRACT FROM AUTHOR]

The issue of data quality is increasingly important as individuals as well as corporations are relying on multiple, often external sources of data to make decisions. Traditional query systems do not factor in data quality considerations in their response. Further, studies into the diverse interpretations of data quality indicate that fitness for use is a fundamental criterion in the evaluation of data quality. In this paper we address the issue of data quality aware query systems by developing a query answering framework that considers user data quality preferences over a collaborative information systems architecture. Our work is motivated by an extensive study of data quality literature that revealed a lack of holistic solutions that encompass both business and technological aspects of data quality management. Accordingly the developed framework for data quality aware query systems takes an end-to-end view of the problem. In this paper we have focused on three major aspects relating to quality aware query systems, namely measuring data quality, modeling of user's data quality preferences, and answering the query in consideration of the defined preferences and measures. We then address each of these issues by introducing data quality profiling, data quality aware SQL, and data quality aware query answering methods. Contributions of this paper have been evaluated on real and simulated data. The individual components have also been assembled into a running prototype. [ABSTRACT FROM AUTHOR]

Abstract: Continuous reverse k nearest neighbor (CRkNN) monitoring in road networks has recently received increasing attentions. However, there is still a lack of efficient CRkNN algorithms in road networks up to now. In road networks, moving query objects and data objects are restricted by the connectivity of the road network and both the object–query distance and object–object distance updates affect the result of CRkNN queries. In this paper, we present a novel algorithm for continuous and incremental evaluation of CRkNN queries in road networks. Our method is based on a novel data structure called dual layer multiway tree (DLM tree) we proposed to represent the whole monitoring region of a CRkNN query q. We propose several lemmas to reduce the monitoring region of q and the number of candidate objects as much as possible. Moreover, by associating a variable NN_count with each candidate object, we can simplify the monitoring of candidate objects. There are a large number of objects roaming in a road network and many of them are irrelevant to a specific CRkNN query of a query object q. To minimize the processing extension, for a road in the network, we give an IQL list and an IQCL list to specify the set of query objects and data objects whose location updates should be maintained for CRkNN processing of query objects. Our CRkNN method consists of two phase: the initial result generating phase and incremental maintenance phase. In each phase, algorithms with high performance are proposed to make our CRkNN method more efficient. Extensive simulation experiments are conducted and the result shows that our proposed approach is efficient and scalable in processing CRkNN queries in road networks. [ABSTRACT FROM AUTHOR]

Abstract: A number of proposals for integrating geographical (Geographical Information Systems—GIS) and multidimensional (data warehouse—DW and online analytical processing—OLAP) processing are found in the database literature. However, most of the current approaches do not take into account the use of a GDW (geographical data warehouse) metamodel or query language to make available the simultaneous specification of multidimensional and spatial operators. To address this, this paper discusses the UML class diagram of a GDW metamodel and proposes its formal specifications. We then present a formal metamodel for a geographical data cube and propose the Geographical Multidimensional Query Language (GeoMDQL) as well. GeoMDQL is based on well-known standards such as the MultiDimensional eXpressions (MDX) language and OGC simple features specification for SQL and has been specifically defined for spatial OLAP environments based on a GDW. We also present the GeoMDQL syntax and a discussion regarding the taxonomy of GeoMDQL query types. Additionally, aspects related to the GeoMDQL architecture implementation are described, along with a case study involving the Brazilian public healthcare system in order to illustrate the proposed query language. [Copyright &y& Elsevier]

Abstract: Query rewriting using views is a technique that allows a query to be answered efficiently by using pre-computed materialized views. It has many applications, such as data caching, query optimization, schema integration, etc. This issue has been studied extensively for relational databases and, as a result, the technology is maturing. For XML data, however, the work is inadequate. Recently, several frameworks have been proposed for query rewriting using views for XPath queries, with the requirement that a rewriting must be complete. In this paper, we study the problem of query rewriting using views for XPath queries without requiring that the rewriting be complete. This will increase its applicability since in many cases, complete rewritings using views do not exist. We give formal definitions for various concepts to formulate the problem, and then propose solutions. Our solutions are built under the framework for query containment. We look into the problem from both theoretic perspectives, and algorithmic approaches. Two methods to generate rewritings using views are proposed, with different characteristics in terms of generalities and efficiencies. The maximality properties of the rewritings generated by these methods are discussed. [Copyright &y& Elsevier]

Abstract: Many geographical applications deal with objects in space that cannot be adequately described by determinate, crisp spatial concepts because of their intrinsically indeterminate and vague nature. Geographical information systems and spatial database systems are currently unable to cope with this kind of data. To support the efficient representation, querying, and manipulation of vague spatial data in a database context, we present a formal data model called vague spatial algebra (VASA). This algebra comprises a set of vague spatial data types for vague points, vague lines, and vague regions together with a comprehensive collection of vague spatial operations and vague topological predicates. One of VASA''s main benefits is that its formal framework is based on well known, general, and exact models of crisp spatial data types. This enables an exact definition of the vague spatial model since we can build upon an already existing theory of spatial data types. In particular, crisp spatial data types turn out to be a special case of their vague counterparts. In addition, our approach enables executable specifications for the operations, which can be immediately used as implementations. The article offers a precise and conceptually clean foundation for implementing a DBMS extension for vague spatial data and demonstrates the embedding of these new data types as attribute data types in a database schema as well as the incorporation of vague spatial operations and predicates into queries formulated in an SQL-like query language. All concepts have been verified in a prototype implementation. [Copyright &y& Elsevier]

Abstract: We introduce a new methodology for coupling language-induced partitions and index-induced partitions on XML documents that is aimed for the benefit of efficient evaluation of XPath queries. In particular, we identify XPath fragments which are ideally coupled with the newly introduced -partition which has its definition grounded in the well-known structural index and its associated partition. We then utilize these couplings to investigate fundamental questions about the use of structural indexes in XPath query evaluation. [Copyright &y& Elsevier]

This paper presents dedale, a spatial database system, which provides an abstract and non-specialized data model and query language for representating and manipulating geometric data in arbitrary dimension. dedale relies on a logical model based on linear constraints. The main features of the constraint model are: (1) a uniform representation of all sorts of data, including geometric, spatio-temporal or elevation data and (2) an algebraic query language whose formal foundations constitute a basis for practical query optimization.We show the practical relevance of the approach by describing an implementation which builds on standard technology for data storage, database indexing and on the parsing and optimization of SQL. dedale validates the linear constraint model over various applications, proposes a user query language based on SQL which allows to query the database in a purely declarative way, and gives some first steps towards query optimization.We believe that this experience is a fruitful step toward sound and consistent database models which hide the complexity of arbitrary geometric data, while keeping manipulation languages intuitive and efficient. [Copyright &y& Elsevier]

Multi-dimensional expressions (MDX) provide an interface for asking several related OLAP queries simultaneously. An interesting problem is how to optimize the execution of an MDX query, given that most data warehouses maintain a set of redundant materialized views to accelerate OLAP operations. A number of greedy and approximation algorithms have been proposed for different versions of the problem. In this paper we evaluate experimentally their performance, concluding that they do not scale well for realistic workloads. Motivated by this fact, we develop two novel greedy algorithms. Our algorithms construct the execution plan in a top–down manner by identifying in each step the most beneficial view, instead of finding the most promising query. We show by extensive experimentation that our methods outperform the existing ones in most cases. [Copyright &y& Elsevier]

Current data management and information retrieval systems lack advanced string processing capabilities needed in string-oriented application areas like computational molecular biology. Several theoretical models for string processing have been proposed but they either have not been implemented in practice or the implementations are too restricted or platform-dependent to be generally useful. In this article, we introduce the language Alignment Declarations designed for string querying and restructuring. The language extends the capabilities of existing database query languages by allowing the user to define database predicates that express structural properties of strings (e.g. containment of certain patterns) or relations between several strings (e.g. similarity measures). These predicates can be created and executed within the same database session and also stored for later sessions. We also describe the design and implementation of a working system. [Copyright &y& Elsevier]

Estimating the sizes of query results, and intermediate results, is crucial to many aspects of query processing. In particular, it is necessary for effective query optimization. Even at the user level, predictions of the total result size can be valuable in “next-step” decisions, such as query refinement. This paper proposes a technique to obtain query result size estimates effectively in an XML database.Queries in XML frequently specify structural patterns, requiring specific relationships between selected elements. Whereas traditional techniques can estimate the number of nodes (XML elements) that will satisfy a node-specific predicate in the query pattern, such estimates cannot easily be combined to provide estimates for the entire query pattern, since element occurrences are expected to have high correlation.We propose a solution based on a novel histogram encoding of element occurrence position. With such position histograms, we are able to obtain estimates of sizes for complex pattern queries, as well as for simpler intermediate patterns that may be evaluated in alternative query plans, by means of a position histogram join (pH-join) algorithm that we introduce. We extend our technique to exploit schema information regarding allowable structure (the no-overlap property) through the use of a coverage histogram.We present an extensive experimental evaluation using several XML data sets, both real and synthetic, with a variety of queries. Our results demonstrate that accurate and robust estimates can be achieved, with limited space, and at a minuscule computational cost. These techniques have been implemented in the context of the TIMBER native XML database (available at http://www.eecs.umich.edu/db/timber) at the University of Michigan. [Copyright &y& Elsevier]

The success of Internet applications has led to an explosive growth in the demand for bandwidth from Internet Service Providers. Managing an Internet protocol network requires collecting and analyzing network data, such as flow-level traffic statistics. Such analyses can typically be expressed as OLAP queries, e.g., correlated aggregate queries and data cubes. Current day OLAP tools for this task assume the availability of the data in a centralized data warehouse. However, the inherently distributed nature of data collection and the huge amount of data extracted at each collection point make it impractical to gather all data at a centralized site. One solution is to maintain a distributed data warehouse, consisting of local data warehouses at each collection point and a coordinator site, with most of the processing being performed at the local sites. In this paper, we consider the problem of efficient evaluation of OLAP queries over a distributed data warehouse. We have developed the Skalla system for this task. Skalla translates OLAP queries, specified as certain algebraic expressions, into distributed evaluation plans which are shipped to individual sites. A salient property of our approach is that only partial results are shipped — never parts of the detail data. We propose a variety of optimizations to minimize both the synchronization traffic and the local processing done at each site. We finally present an experimental study based on TPC-R data. Our results demonstrate the scalability of our techniques and quantify the performance benefits of the optimization techniques that have gone into the Skalla system. [Copyright &y& Elsevier]

Maintaining statistics on multidimensional data distributions is crucial for predicting the run-time and result size of queries and data analysis tasks with acceptable accuracy. Applications of such predictions include traditional query optimization, priority management and resource scheduling for data mining tasks, as well as querying heterogeneous Web data sources with diverse information quality. To this end a plethora of techniques have been proposed for maintaining a compact data “synopsis” on a single table, ranging from variants of histograms to methods based on wavelets and other transforms. However, the fundamental question of how to reconcile the synopses for large information sources with many tables has been largely unexplored. This paper develops a general framework for reconciling the synopses on many tables, which may come from different information sources. It shows how to compute an optimal combination of synopses for a given workload and a limited amount of available memory. As the exact solution has large computational complexity, efficient heuristics are presented for limiting the search space of synopses combinations. The practicality of the approach and the accuracy of the proposed heuristics are demonstrated by experiments. [Copyright &y& Elsevier]

Queries containing universal quantification are used in many applications, including business intelligence applications and in particular data mining. We present a comprehensive survey of the structure and performance of algorithms for universal quantification. We introduce a framework that results in a complete classification of input data for universal quantification. Then we go on to identify the most efficient algorithm for each such class. One of the input data classes has not been covered so far. For this class, we propose several new algorithms. Thus, for the first time, we are able to identify the optimal algorithm to use for any given input dataset.These two classifications of optimal algorithms and input data are important for query optimization. They allow a query optimizer to make the best selection when optimizing at intermediate steps for the quantification problem.In addition to the classification, we show the relationship between relational division and the set containment join and we illustrate the usefulness of employing universal quantifications by presenting a novel approach for frequent itemset discovery. [Copyright &y& Elsevier]

In this paper, we propose a method to accelerate the speed of subset query on uncompressed images. First, we change the method to store images: the pixels of images are stored on the disk in the Hilbert order instead of row-wise order that is used in traditional methods. After studying the properties of the Hilbert curve, we give a new algorithm which greatly reduces the number of data segments in subset query range. Although, we have to retrieve more data than necessary, because the speed of sequential readings is much faster than the speed of random access readings, it takes about 10% less elapsed time in our algorithm than in the traditional algorithms to execute the subset queries. In some systems, the saving is as much as 90%. [Copyright &y& Elsevier]

Recent database applications are typically oriented towards a large set of non-expert users, and therefore, they need to be equipped with suitable interfaces facilitating the interaction with the system. Moreover, the incorporation of the time dimension in database systems is a desirable feature. Indeed, several temporal data models and the corresponding textual query languages have been proposed. However, there is a limited amount of research concerning the investigation of user-oriented languages for querying temporal databases. Our proposal addresses such a need. In particular, we propose a visual query environment, namely Temporal Visual Query Environment (TVQE) which provides an easier interaction of the user with temporal databases. The system adopts a diagrammatic representation of the database schema (including temporal classes and relationships) and a “graphical notebook” as interaction metaphor. In our approach, non-database experts are released from syntactical difficulties which are typical of textual languages, and they can easily express temporal queries by means of elementary graphical operations (e.g. click on a node label). Differently from many proposals in the field of visual query languages, the language underlying TVQE is provided with formal syntax and semantics. It is based on a minimal set of temporal graphical primitives (TGPs), which are defined on a Temporal Graph Model (TGM), with visual syntax and object-based semantics. In this paper we mainly concentrate on the formal aspects of TVQE, and provide some hints on the visual interaction mechanisms and implementation issues. [Copyright &y& Elsevier]

In this paper, we explore the possibility of transforming queries with minimum and maximum predicates into equivalent queries that can be computed more efficiently. The main contribution of the paper is an algorithm for propagating min and max predicates while preserving query equivalence under certain monotonicity constraints. We show that the algorithm is correct and that the transformed query is often safe when the original one is not. Although in this paper we use logic rules, the technique presented can be used to optimize (possibly recursive) queries expressed using SQL3. [Copyright &y& Elsevier]

Aiming at the efficient retrieval of objects with set-valued attributes, we introduce three variations of a new method in order to satisfy subset and superset queries. Our approach is to combine the advantages of two access methods, that of linear Hashing and of tree-shaped methods, on which other similar methods have been previously reported as well. Performance estimation analytical functions for each particular method are presented, followed by a thorough experimental comparison of all investigated structures, where analytical and experimental results deviate 10% on the average. Finally, the results of this performance evaluation are presented and discussed, clearly showing the superiority of the new methods reaching an improvement of up to 85%. [Copyright &y& Elsevier]

The extension of the eXtensible Style sheet Language (XSL) by variables and passing of data values between template rules has generated a powerful XML query language: eXtensible Style sheet Language Transformations (XSLT). An informal introduction to XSTL is given, on the bases of which a formal model of a fragment of XSLT is defined. This formal model is in the spirit of tree transducers, and its semantics is defined by rewrite relations. It is shown that the expressive power of the fragment is already beyond that of most other XML query languages. Finally, important properties such as termination and closure under composition are considered. [Copyright &y& Elsevier]

This paper presents a novel query for spatial databases, called r everse n earest neighbor h ood (RNH) query, to discover the neighborhoods that find a query facility as their nearest facility among other facilities in the dataset. Unlike a reverse nearest neighbor (RNN) query, an RNH query emphasizes on group of users instead of an individual user. More specifically, given a set of user locations U , a set of facility locations F , a query location q , a distance parameter ρ and a positive integer k , an RNH query returns all ρ -radius circles C enclosing at least k users u ∈ U , called n eighbor h oods (NH) such that the distance between q and C is less than the distance between C and any other facility f ∈ F. The RNH queries might have many practical applications including on demand facility placement and smart urban planning. We present an efficient approach for processing RNH queries on location data using R-tree based data indexing. In our approach, first we retrieve candidate RNH users by an efficient bound, prune and refine technique. Then, we incrementally discover RNHs of a query facility from these candidate RNH users. We also present the variants of RNH queries in spatial databases and propose solutions for them. We validate our approach by conducting extensive experiments with real datasets. • A novel query called reverse nearest neighborhood (RNH) query is proposed. • An approach for processing RNH queries using R-Tree data indexing is presented. • Our approach incrementally discovers RNHs of a facility from the candidate RNH users. • The variants of RNH query in spatial databases and solutions for them are presented. • Extensive experiments with real datasets are conducted to validate the approach. [ABSTRACT FROM AUTHOR]