Search

We develop a multiset query and update language executable in a term rewriting system. Its most remarkable feature, besides non-standard approach to quantification and introduction of fresh values, is non-determinism — a query result is not uniquely determined by the database. We argue that this feature is very useful, e.g., in modelling user choices during simulation or reachability analysis of a data-centric business process — the intended application of our work. Query evaluation is implemented by converting the query into a terminating term rewriting system and normalizing the initial term which encapsulates the current database. A normal form encapsulates a query result. We prove that our language can express any relational algebra query. Finally, we present a simple business process specification framework (and an example specification). Both syntax and semantics of our query language is implemented in Maude. [ABSTRACT FROM AUTHOR]

There is a long tradition in understanding graphs by investigating their adjacency matrices by means of linear algebra. Similarly, logic-based graph query languages are commonly used to explore graph properties. In this paper, we bridge these two approaches by regarding linear algebra as a graph query language. More specifically, we consider MATLANG, a matrix query language recently introduced, in which some basic linear algebra functionality is supported. We investigate the problem of characterising the equivalence of graphs, represented by their adjacency matrices, for various fragments of MATLANG. That is, we are interested in understanding when two graphs cannot be distinguished by posing queries in MATLANG on their adjacency matrices. Surprisingly, a complete picture can be painted of the impact of each of the linear algebra operations supported in MATLANG on their ability to distinguish graphs. Interestingly, these characterisations can often be phrased in terms of spectral and combinatorial properties of graphs. Furthermore, we also establish links to logical equivalence of graphs. In particular, we show that MATLANG-equivalence of graphs corresponds to equivalence by means of sentences in the three-variable fragment of first-order logic with counting. Equivalence with regards to a smaller MATLANG fragment is shown to correspond to equivalence by means of sentences in the two-variable fragment of this logic. [ABSTRACT FROM AUTHOR]

Retroscope is a comprehensive lightweight distributed monitoring tool that enables users to query and reconstruct past consistent global states of the system. Retroscope achieves this by augmenting the system with Hybrid Logical Clocks (HLC) and by streaming HLC-stamped event logs for storage and processing; these HLC timestamps are then used for constructing global (or nonlocal) snapshots upon request. Retroscope provides a rich querying language (RQL) to facilitate searching for global predicates across past consistent states. The search is performed by advancing through global states in small incremental steps, greatly reducing the amount of computation needed to construct consistent states. The Retroscope search algorithm is embarrassingly-parallel and can employ many worker processes (each processing up to 150,000 consistent snapshots per second) to handle a single query. We evaluate Retroscope's monitoring capabilities in two case studies: Chord and Apache ZooKeeper. [ABSTRACT FROM AUTHOR]

For any query language F , we consider three natural families of boolean queries. Nonemptiness queries are expressed as e ≠ ∅ with e an F expression. Emptiness queries are expressed as e = ∅. Containment queries are expressed as e1 ⊆ e2. We refer to syntactic constructions of boolean queries as modalities. In first order logic, the emptiness, nonemptiness and containment modalities have exactly the same expressive power. For other classes of queries, e.g., expressed in weaker query languages, the modalities may differ in expressiveness. We propose a framework for studying the expressive power of boolean query modalities. Along one dimension, one may work within a fixed query language and compare the three modalities. Here, we identify crucial query features that enable us to go from one modality to another. Furthermore, we identify semantical properties that reflect the lack of these query features to establish separations. Along a second dimension, one may fix a modality and compare different query languages. This second dimension is the one that has already received quite some attention in the literature, whereas in this paper we emphasize the first dimension. Combining both dimensions, it is interesting to compare the expressive power of a weak query language using a strong modality, against that of a seemingly stronger query language but perhaps using a weaker modality. We present some initial results within this theme. The two main query languages to which we apply our framework are the algebra of binary relations, and the language of conjunctive queries. [ABSTRACT FROM AUTHOR]

Incomplete Information research is quite mature when it comes to so called existential nulls, where an existential null is a value stored in the database, representing an unknown object. For some reason universal nulls, that is, values representing all possible objects, have received almost no attention. We remedy the situation in this paper, by showing that a suitable finite representation mechanism, called Star Cylinders, handling universal nulls can be developed based on the Cylindric Set Algebra of Henkin, Monk and Tarski. We provide a finitary version of the cylindric set algebra, called Cylindric Star Algebra, and show that our star-cylinders are closed under this algebra. Moreover, we show that any First Order Relational Calculus query over databases containing universal nulls can be translated into an equivalent expression in our cylindric star-algebra, and vice versa. All cylindric star-algebra expressions can be evaluated in time polynomial in the size of the database. The representation mechanism is then extended to Naive Star Cylinders, which are star-cylinders allowing existential nulls in addition to universal nulls. For positive queries (with universal quantification), the well known naive evaluation technique can still be applied on the existential nulls, thereby allowing polynomial time evaluation of certain answers on databases containing both universal and existential nulls. If precise answers are required, certain answer evaluation with universal and existential nulls remains in coNP. Note that the problem is coNP-hard, already for positive existential queries and databases with only existential nulls. If inequalities ¬(xi ≈ xj) are allowed, reasoning over existential databases is known to be ∏ 2 p -complete, and it remains in ∏ 2 p when universal nulls and full first order queries are allowed. [ABSTRACT FROM AUTHOR]

We survey foundational features underlying modern graph query languages. We first discuss two popular graph data models: edge-labelled graphs, where nodes are connected by directed, labelled edges and property graphs, where nodes and edges can further have attributes. Next we discuss the two most fundamental graph querying functionalities: graph patterns and navigational expressions. We start with graph patterns, in which a graph-structured query is matched against the data. Thereafter, we discuss navigational expressions, in which patterns can be matched recursively against the graph to navigate paths of arbitrary length; we give an overview of what kinds of expressions have been proposed and how they can be combined with graph patterns.We also discuss several semantics under which queries using the previous features can be evaluated, what effects the selection of features and semantics has on complexity, and offer examples of such features in three modern languages that are used to query graphs: SPARQL, Cypher and Gremlin. We conclude by discussing the importance of formalisation for graph query languages; a summary of what is known about SPARQL, Cypher and Gremlin in terms of expressivity and complexity; and an outline of possible future directions for the area. [ABSTRACT FROM AUTHOR]

We consider the containment problem for regular queries with memory and regular queries with data tests: two recently proposed query languages for graph databases that, in addition to allowing the user to ask topological queries, also track how the data changes along paths connecting various points in the database. Our results show that the problem is undecidable in general. However, by allowing only positive data comparisons we find natural fragments with better static analysis properties: the containment problem is PSpace -complete in the case of regular queries with data tests and ExpSpace -complete in the case of regular queries with memory. [ABSTRACT FROM AUTHOR]

A business process or workflow is an assembly of tasks that accomplishes a business goal. Business process management is the study of the design, configuration/implementation, enactment and monitoring, analysis, and re-design of workflows. The traditional methodology for the re-design and improvement of workflows relies on the well-known sequence of extract, transform and load (ETL), data/process warehousing and online analytical processing (OLAP) tools. In this paper, we study the ad hoc queryiny of process enactments for (data-centric) business processes, bypassing the traditional methodology for more flexibility in querying. We develop an algebraic query language based on "incident patterns" with four operators inspired from Business Process Model and Notation (BPMN) representation, allowing the user to formulate ad hoc queries directly over workflow logs. A formal semantics of this query language, a preliminary query evaluation algorithm, and a group of elementary properties of the operators are provided. [ABSTRACT FROM AUTHOR]

When querying an Resource Description Framework (RDF) graph, a prominent feature is the possibility of extending the answer to a query with optional information. However, the definition of this feature in SPARQL-- the standard RDF query language--has raised some important issues. Most notably, the use of this feature increases the complexity of the evaluation problem, and its closed-world semantics is in conflict with the underlying open-world semantics of RDF. Many approaches for fixing such problems have been proposed, the most prominent being the introduction of the semantic notion of weakly monotone SPARQL query. Weakly monotone SPARQL queries have shaped the class of queries that conform to the open-world semantics of RDF. Unfortunately, finding an effective way of restricting SPARQL to the fragment of weakly monotone queries has proven to be an elusive problem. In practice, the most widely adopted fragment for writing SPARQL queries is based on the syntactic notion of well designedness. This notion has proven to be a good approach for writing SPARQL queries, but its expressive power has yet to be fully understood. The starting point of this article is to understand the relation between well-designed queries and the semantic notion of weak monotonicity. It is known that every well-designed SPARQL query is weakly monotone; as our first contribution we prove that the converse does not hold, even if an extension of this notion based on the use of disjunction is considered. Given this negative result, we embark on the task of defining syntactic fragments that are weakly monotone and have higher expressive power than the fragment of well-designed queries. To this end, we move to a more general scenario where infinite RDF graphs are also allowed, so interpolation techniques studied for first-order logic can be applied. With the use of these techniques, we are able to define a new operator for SPARQL that gives rise to a query language with the desired properties (over finite and infinite RDF graphs). It should be noticed that every query in this fragment is weakly monotone if we restrict the semantics to finite RDF graphs. Moreover, we use this result to provide a simple characterization of the class of monotone CONSTRUCT queries, that is, the class of SPARQL queries that produce RDF graphs as output. Finally, we pinpoint the complexity of the evaluation problem for the query languages identified in the article. [ABSTRACT FROM AUTHOR]

Information Retrieval is a complex task, which deals with both the subjectivity related to the user's needs and the uncertainty and vagueness that characterize the retrieval process. For this reason, deciding to which extent a document is relevant to a user's needs is not easy, and it strongly depends on several dimensions such as topicality, novelty, user's context, and so on. One of the most straightforward ways to interpret this activity is as a Multi-Criteria Decision Making (MCDM) problem, in which the choice of appropriate aggregation operators can play an important role in various tasks related to, or characterizing the IR process. This article aims to provide a presentation of the main approaches that in the literature have made use of aggregation operators in Information Retrieval. [ABSTRACT FROM AUTHOR]

Purpose-The purpose of this paper is to assess whether Europeana can be really seen as the new "Library of Alexandria" for digital resources from the perspective of teachers, academics and researchers that might want to retrieve and reuse those resources for learning purposes. Design/methodology/approach-he authors define a systematic method for studying Europeana digital resources and their potential for reuse in e-learning environments. To achieve this, the authors explore the coverage of digital resources when searching information about a specific area. The paper studies the relevance of the results (thematic coverage) provided by queries targeting the resources' metadata elements defined by the EDM Europeana model. All the data collected for this study from Europeana digital resources are the result of four explorations since 2012-2016. Findings-The autors found that Europeana as a digital library has good levels of coverage of digital resources for those terms in the AAT thesaurus explored (terms from the "Styles and Periods" subset). This subset was selected as an example of faceted search given that it is a common search topic in the academic environment. However, it is important to remark the use of common vocabulary words provided by participants in order to obtain relevant results of search based on specific knowledge areas defined by AAT terms. Research limitations/implications-This research used a relatively small sample size of resources which may not be representative of the general size of Europeana digital resources. However, the results are illustrative as they are based on a specific knowledge area of AAT (118 terms) which contains very common topics used in high school courses by students and teachers in the field of art and cultural heritage. The study also aspires to provide a systematic method for conducting future studies in other knowledge areas. Originality/value-The coverage study aims to analyze if Europeana is a digital library that teachers could use for the development of learning objects in specific knowledge areas, through the reuse of free/open access digital resources. [ABSTRACT FROM AUTHOR]

Next Generation Sequencing (NGS) is a family of technologies for reading the DNA or RNA, capable of producing whole genome sequences at an impressive speed, and causing a revolution of both biological research and medical practice. In this exciting scenario, while a huge number of specialized bio-informatics programs extract information from sequences, there is an increasing need for a new generation of systems and frameworks capable of integrating such information, providing holistic answers to the needs of biologists and clinicians. To respond to this need, we developed GMQL, a new query language for genomic data management that operates on heterogeneous genomic datasets. In this paper, we focus on three domain-specific operations of GMQL used for the efficient processing of operations on genomic regions, and we describe their efficient implementation; the paper develops a theory of binning strategies as a generic approach to parallel execution of genomic operations, and then describes how binning is embedded into two efficient implementations of the operations using Flink and Spark, two emerging frameworks for data management on the cloud. [ABSTRACT FROM AUTHOR]

Promoting declarative approaches in data mining is a long standing theme, the main idea being to simplify as much as possible the way data analysts interact with their data. This paper goes into this direction by proposing a well-founded logical query language, S a f e RL , allowing the expression of a wide variety of rules to be discovered against a database. By rules, we mean statements of the form “if …then …”, as defined in logics for “implications” between boolean variables. As a consequence, S a f e RL extends and generalizes functional dependencies to new and unexpected rules. We provide a query rewriting technique and a constructive proof of the main query equivalence theorem, leading to an efficient query processing technique. From S a f e RL , we have devised RQL, a user-friendly SQL-like query language. We have shown how a tight integration can be performed on top of any relational database management system. Every RQL query turns out to be seen as a query processing problem, instead of a particular rule mining problem. This approach has been implemented and experimented on sensor network data. A web prototype has been released and is freely available ( http://rql.insa-lyon.fr ). Data analysts can upload a sample of their data, write their own RQL queries and get answers to know whether or not a rule holds (if not, a counterexample from the database is displayed) and much more. [ABSTRACT FROM AUTHOR]

While a huge amount of (epi)genomic data of multiple types is becoming available by using Next Generation Sequencing (NGS) technologies, the most important emerging problem is the so-called tertiary analysis , concerned with sense making, e.g., discovering how different (epi)genomic regions and their products interact and cooperate with each other. We propose a paradigm shift in tertiary analysis, based on the use of the Genomic Data Model (GDM), a simple data model which links genomic feature data to their associated experimental, biological and clinical metadata. GDM encompasses all the data formats which have been produced for feature extraction from (epi)genomic datasets. We specifically describe the mapping to GDM of SAM (Sequence Alignment/Map), VCF (Variant Call Format), NARROWPEAK (for called peaks produced by NGS ChIP-seq or DNase-seq methods), and BED (Browser Extensible Data) formats, but GDM supports as well all the formats describing experimental datasets (e.g., including copy number variations, DNA somatic mutations, or gene expressions) and annotations (e.g., regarding transcription start sites, genes, enhancers or CpG islands). We downloaded and integrated samples of all the above-mentioned data types and formats from multiple sources. The GDM is able to homogeneously describe semantically heterogeneous data and makes the ground for providing data interoperability, e.g., achieved through the GenoMetric Query Language (GMQL), a high-level, declarative query language for genomic big data. The combined use of the data model and the query language allows comprehensive processing of multiple heterogeneous data, and supports the development of domain-specific data-driven computations and bio-molecular knowledge discovery. [ABSTRACT FROM AUTHOR]

How can users who know neither programming nor statistics explore large databases? We present a novel interface, designed to guide explorers through their data: Blaeu. Blaeu is a database front-end, “boosted” with unsupervised learning primitives. Thanks to these primitives, it can summarize and recommend queries. Our first contribution is Blaeu's interaction model. With Blaeu, users explore the data through data maps. A data map is an interactive set of clusters, which users navigate with zooms and projections. Our second contribution is Blaeu's engine. We present three mapping algorithms, for three different settings. The first algorithm deals with small to medium databases, the second one targets high dimensional spaces, and the last one focuses on speed and interaction. We then present an optimization strategy based on sampling. Our experiments reveal that Blaeu can cluster millions of tuples with hundreds of columns in a few seconds on commodity hardware. [ABSTRACT FROM AUTHOR]

We study highly expressive query languages for unordered data trees, using as formal vehicles Active XML and extensions of languages in the while family. All languages may be seen as adding some form of control on top of a set of basic pattern queries. The results highlight the impact and interplay of different factors: the expressive power of basic queries, the embedding of computation into data (as in Active XML), and the use of deterministic vs. nondeterministic control. All languages are Turing complete, but not necessarily query complete in the sense of Chandra and Harel. Indeed, we show that some combinations of features yield serious limitations, analogous to FO definability in the relational context. On the other hand, the limitations come with benefits such as the existence of powerful normal forms providing opportunities for optimization. Other languages are 'almost' complete, but fall short because of subtle limitations reminiscent of the copy elimination problem in object databases. [ABSTRACT FROM AUTHOR]

Two XML query languages were tested for intuitivity, learnability and memorability. The languages differ with relation to the query structures like the use of variables, iterators and reference to attributes. One of the languages, XQuery, is a procedural, expressive and data-oriented query language that is suitable even for programming purposes; the other, XIL, is more declarative, document-oriented query language with a simpler syntax. A query-writing test with the learners of the languages was executed. The study indicates that, in the query writing, the more procedural query language yields a greater number of correct queries. Similarity between the tested languages, and to SQL, is discussed from the point of view of learnability. [ABSTRACT FROM AUTHOR]

Spreadsheets are among the most commonly used applications for data management and analysis. They combine data processing with very diverse supplementary features: statistics, visualization, reporting, linear programming solvers, Web queries periodically downloading data from external sources, etc. However, the spreadsheet paradigm of computation still lacks sufficient analysis. In this article, we demonstrate that a spreadsheet can implement all data transformations definable in SQL, merely by utilizing spreadsheet formulas. We provide a query compiler, which translates any given SQL query into a worksheet of the same semantics, including NULL values. Thereby, database operations become available to the users who do not want to migrate to a database. They can define their queries using a high-level language and then get their execution plans in a plain vanilla spreadsheet. The functions available in spreadsheets impose limitations on the algorithms one can implement. In this paper, we offer $O(n\,\log ^2\,n)$ sorting spreadsheet, using a non-constant number of rows, and, surprisingly, Depth-First-Search and Breadth-First-Search on graphs. [ABSTRACT FROM PUBLISHER]

With the rise of social networks, large-scale graph analysis becomes increasingly important. Because SQL lacks the expressiveness and performance needed for graph algorithms, lower-level, general-purpose languages are often used instead. For greater ease of use and efficiency, we propose SociaLite, a high-level graph query language based on Datalog. As a logic programming language, Datalog allows many graph algorithms to be expressed succinctly. However, its performance has not been competitive when compared to low-level languages. With SociaLite, users can provide high-level hints on the data layout and evaluation order; they can also define recursive aggregate functions which, as long as they are meet operations, can be evaluated incrementally and efficiently. Moreover, recursive aggregate functions make it possible to implement more graph algorithms that cannot be implemented in Datalog. We evaluated SociaLite by running nine graph algorithms in total; eight for social network analysis (shortest paths, PageRank, hubs and authorities, mutual neighbors, connected components, triangles, clustering coefficients, and betweenness centrality) and one for biological network analysis (Eulerian cycles). We use two real-life social graphs, LiveJournal and Last.fm, for the evaluation as well as one synthetic graph. The optimizations proposed in this paper speed up almost all the algorithms by 3 to 22 times. SociaLite even outperforms typical Java implementations by an average of 50 percent for the graph algorithms tested. When compared to highly optimized Java implementations, SociaLite programs are an order of magnitude more succinct and easier to write. Its performance is competitive, with only 16 percent overhead for the largest benchmark, and 25 percent overhead for the worst case benchmark. Most importantly, being a query language, SociaLite enables many more users who are not proficient in software engineering to perform network analysis easily and efficiently. [ABSTRACT FROM PUBLISHER]

The standard regular expressions over finite alphabets have been widely accepted as the most basic formalism to query graph databases. However, the major drawback of this approach is that it ignores the presence of data. In this paper we study the so called regular expressions with binding (REWB), that is, regular expressions equipped with variables to store data within a well defined scope. In particular, we study the complexity of the query evaluation of REWB queries over graph databases. [ABSTRACT FROM AUTHOR]

Hermes is a Web-based framework that makes use of many Semantic Web technologies for building personalized news services. Ontologies are employed for knowledge representation, natural language processing techniques are used for semantic text analysis, and semantic query languages enable the specification of the desired information. To accommodate for the need for an intuitive way to create complex queries for news information, we present the Hermes Graphical Query Language (HGQL). The language enables users to create structured queries that use disjunctive, conjunctive, negation, and pattern operators. In addition, this paper presents a ranking algorithm based on the queries made using our graphical query language. Results show that our proposed ranking algorithm significantly outperforms three state-of-the-art ranking algorithms and that users prefer our graphical query language over a text-based alternative. [ABSTRACT FROM AUTHOR]

Data heterogeneity in XML retrieval activities can be tackled by giving users the possibility to obtain approximate answers to their queries. XPath query relaxation has been proposed as a mechanism to provide approximate answers in the case of positive XPath queries. Under this mechanism, the “satisfaction score” of an answer is defined by looking at how the query must be relaxed to produce that answer, and the user is provided with the best \(k\) answers according to their satisfaction score (top- \(k\) query answering). In this paper we investigate the problem of top- \(k\) query answering for XPath queries with negation. We tackle the challenging issues that need to be carefully considered when dealing with the approximation of negated conditions and propose an incremental top- \(k\) query answering technique based on query relaxation. Specifically, after defining a weighted query language and its semantics, we develop a general incremental query evaluation framework, which is flexible enough to support different evaluation strategies. The experimental assessment confirms the effectiveness of the whole framework. [ABSTRACT FROM AUTHOR]

Given a spatio-temporal network (STN) and a set of STN operations, the goal of the Storing Spatio-Temporal Networks (SSTN) problem is to produce an efficient method of storing STN data that minimizes disk I/O costs for given STN operations. The SSTN problem is important for many societal applications, such as surface and air transportation management systems. The problem is NP hard, and is challenging due to an inherently large data volume and novel semantics (e.g., Lagrangian reference frame). Related works rely on orthogonal partitioning approaches (e.g., snapshot and longitudinal) and incur excessive I/O costs when performing common STN queries. Our preliminary work proposed a non-orthogonal partitioning approach in which we optimized the \(LGetOneSuccessor()\) operation that retrieves a single successor for a given node on STN. In this paper, we provide a method to optimize the \(LGetAllSuccessors()\) operation, which retrieves all successors for a given node on a STN. This new approach uses the concept of a Lagrangian Family Set (LFS) to model data access patterns for STN queries. Experimental results using real-world road and flight traffic datasets demonstrate that the proposed approach outperforms prior work for \(LGetAllSuccessors()\) computation workloads. [ABSTRACT FROM AUTHOR]

We propose a logical framework to analyze complex predicates (those involving a subquery) in SQL. We propose a new operator in the relational algebra for handling such predicates, and study its properties and how it combines with traditional relational operator. We focus on predicates of the form att \(\theta \) MOD S, where att is an attribute, \(\theta \) a comparison operator, MOD is one of SOME or ALL, and S is a (correlated or non-correlated) subquery. We provide a formal characterization of these predicate, as well as an implementation and optimization strategies for it. We show that our approach is extendible, so we can support the expression and optimization of other, similar predicates. Finally, we describe experimental evidence that the proposed approach is more efficient than the traditional approach across a variety of conditions. [ABSTRACT FROM PUBLISHER]

Abstract: The early concept of the World Wide Web was the network of related (linked) documents represented in human readable form. The ongoing development leads to another aspect of the web, the web of data. The goal being that the network will provide first-class, machine readable data. Therefore the current network will be transformed to a network where the machines will not only serve as the platform that hosts human readable data but as a true machine–machine network. In this paper, we review and compare the formats, technologies and approaches that are used today for publishing semantic, machine readable data, on the web. [Copyright &y& Elsevier]

As digital sports video becomes increasingly pervasive, semantic video summary becomes one of the important components for the next generation of multimedia applications. Ontology is a feasible way to mine the semantic information from the video stream. However, current ontology‐based methods did not concentrate on the effectiveness and soundness of semantic reasoning. Here, the authors propose a content‐directed ontology reasoning approach to produce meaningful sports video summarisation. The proposed ontology can facilitate the metadata acquisition of video and the improvement of query performance. It also provides a flexible way to query the sports video database, which cannot be achieved by simple keyword search. For annotating, describing and managing the sports video content, we propose a sports video descriptive language (SVDL) based on the proposed ontology. Moreover, the semantically meaningful sports video abstraction is produced by reasoning engine which is based on the extension of the Tableau algorithm. Meanwhile, the soundness and completeness of the reasoning algorithm can be solidly proved. Subjective assessment experimental results reveal the reliability and efficiency of the propose scheme. [ABSTRACT FROM AUTHOR]

We describe HABITAT, a declarative observational debugger for SQL. HABITAT facilitates true language-level (not: plan-level) debugging of, probably flawed, SQL queries that yield unexpected results. Users mark SQL subexpressions of arbitrary size and then observe whether these evaluate as expected. HABITAT understands query nesting and free row variables in correlated subqueries, and generally aims to not constrain users while suspect subexpressions are marked for observation. From the marked SQL text, HABITAT's algebraic compiler derives a new query whose result represents the values of the desired observations. These observations are generated by the target SQL database host itself and are derived from the original data: HABITAT does not require prior data extraction or extra debugging middleware. Experiments with TPC-H database instances indicate that observations impose a runtime overhead sufficiently low to allow for interactive debugging sessions. [ABSTRACT FROM AUTHOR]

The aim of this study is to take advantage of both shape and texture properties of image to improve the performance of image indexing and retrieval algorithm. Further, a framework for partitioning image into non‐overlapping tiles of different sizes, which results in higher retrieval efficiency, is presented. In the new approach, the image is divided into different regions (tiles). Then, the energy and standard deviation of Hartley transform coefficients of each tile, which serve as the local descriptors of texture, are extracted as sub‐features. Next, invariant moments of edge image are used to record the shape features. The shape features and combination of sub‐features of texture provide a robust feature set for image retrieval. The most similar highest priority (MSHP) principle is used for matching of textural features and Canberra distance is utilised for shape features matching. The retrieved image is the image which has less MSHP and Canberra distance from the query image. The proposed method is evaluated on three different image sets, which contain about 17 000 images. The experimental results indicate that the proposed method achieves higher retrieval accuracy than several previously presented schemes, whereas the computational complexity and processing time of the new method are less than those of other approaches. [ABSTRACT FROM AUTHOR]

We study properties of the join operation in query languages and describe some of its major drawbacks. We provide strong arguments against using joins as a main construct for retrieving related data elements in general purpose query languages and argue for using references instead. Since conventional references are quite restrictive when applied to data modeling and query languages, we propose to use generalized references as they are defined in the concept-oriented model (COM). These references are used by two new operations, called projection and de-projection, which are denoted by right and left arrows and therefore this access method is referred to as arrow notation. We demonstrate advantages of the arrow notation in comparison to joins and argue that it makes queries simpler, more natural, easier to understand, and the whole query writing process more productive and less error-prone. [ABSTRACT FROM AUTHOR]

Abstract: A Business Process consists of multiple business activities, which, when combined in a flow, achieve some particular goal. These processes usually operate in a distributed environment and the software implementing them is fairly complex. Thus, effective tools for analysis of the possible executions of such processes are extremely important for companies (Beeri et al., 2006, 2007 ); (Deutch and Milo, 2008 ); these tools can allow to debug and optimize the processes, and to make an optimal use of them. The goal of the present paper is to consider a formal model underlying Business Processes and study query languages over such processes. We study in details the relationship of the proposed model with previously suggested formalisms for processes modeling and querying. In particular we propose a query evaluation algorithm of polynomial data complexity that can be applied uniformly to two kind of common queries over processes, namely queries on the structure of the process specification as well as temporal queries on the potential behavior of the defined process. We show that unless the efficiency of our algorithm is asymptotically optimal. [Copyright &y& Elsevier]

Nested words provide a natural model of runs of programs with recursive procedure calls. The usual connection between monadic second-order logic (MSO) and automata extends from words to nested words and gives us a natural notion of regular languages of nested words. In this paper we look at some well-known aspects of regular languages-their characterization via fixed points, deterministic and alternating automata for them, and synchronization for defining regular relations-and extend them to nested words. We show that mu-calculus is as expressive as MSO over finite and infinite nested words, and the equivalence holds, more generally, for mu-calculus with past modalities evaluated in arbitrary positions in a word, not only in the first position. We introduce the notion of alternating automata for nested words, show that they are as expressive as the usual automata, and also prove that Muller automata can be determinized (unlike in the case of visibly pushdown languages). Finally we look at synchronization over nested words. We show that the usual letter-to-letter synchronization is completely incompatible with nested words (in the sense that even the weakest form of it leads to an undecidable formalism) and present an alternative form of synchronization that gives us decidable notions of regular relations. [ABSTRACT FROM AUTHOR]

The class of unions of conjunctive queries ( UCQ) has been shown to be particularly well-behaved for data exchange; its certain answers can be computed in polynomial time (in terms of data complexity). However, this is not the only class with this property; the certain answers to any Datalog program can also can be computed in polynomial time. The problem is that both UCQ and Datalog do not allow negated atoms, as adding an unrestricted form of negation to these languages yields to intractability. In this paper, we propose a language called Datalog that extends Datalog with a restricted form of negation, and study some of its fundamental properties. In particular, we show that the certain answers to a Datalog program can be computed in polynomial time (in terms of data complexity), and that every union of conjunctive queries with at most one inequality or negated relational atom per disjunct, can be efficiently rewritten as a Datalog program in the context of data exchange. Furthermore, we show that this is also the case for a syntactic restriction of the class of unions of conjunctive queries with at most two inequalities per disjunct. This syntactic restriction is given by two conditions that are optimal, in the sense that computing certain answers becomes intractable if one removes any of them. Finally, we provide a thorough analysis of the combined complexity of computing certain answers to Datalog programs and other related query languages. In particular, we show that this problem is Exptime-complete for Datalog, even if one restricts to conjunctive queries with single inequalities, which is a fragment of Datalog by the result mentioned above. Furthermore, we show that the combined complexity is coNexptime-complete for the case of conjunctive queries with k inequalities, for every k≥2. [ABSTRACT FROM AUTHOR]

Abstract: Many DB management systems use SQL syntax in order to provide a mechanism for data accessing. Although SQL is widely used, its syntax is not very comprehensive to a typical user. In this paper we present a tool capable of transforming simple queries formatted in natural language into their equivalent SQL queries. The purpose of this study is to provide a query syntax method closer to natural language. We currently support three languages: English, German and Greek and we show how our tool can be extended easily from a user so as to support any other language. [Copyright &y& Elsevier]

Abstract: Annotated relational databases can be queried either by simply making the annotations explicitly available along the ordinary data, or by adapting the standard query operators so that they have an implicit effect also on the annotations. We compare the expressive power of these two approaches. As a formal model for the implicit approach we propose the color algebra, an adaptation of the relational algebra to deal with the annotations. We show that the color algebra is relationally complete: it is equivalent to the relational algebra on the explicit annotations. Our result extends a similar completeness result established for the query algebra of the MONDRIAN annotation system, from unions of conjunctive queries to the full relational algebra. We also show that the color algebra is nonredundant: no operator can be expressed in terms of the other operators. We also present a generalization of the color algebra that is relationally complete in the presence of built-in predicates on the annotations. [Copyright &y& Elsevier]

In this paper we present a graphical software system that provides an automatic support to the extraction of information from web pages. The underlying extraction technique exploits the visual appearance of the information in the document, and is driven by the spatial relations occurring among the elements in the page. However, the usual information extraction modalities based on the web page structure can be used in our framework, too. The technique has been integrated within the Spatial Relation Query (SRQ) tool. The tool is provided with a graphical front-end which allows one to define and manage a library of spatial relations, and to use a SQL-like language for composing queries driven by these relations and by further semantic and graphical attributes. [Copyright &y& Elsevier]

We give a language-independent characterization of the expressive power, of the relational algebra on finite sets of source-target relation instance pairs. The associated decision problem is shown to be cograph-isomorphism hard and in coNP. The main result is also applied in providing a new characterization of the generic relational queries. [ABSTRACT FROM AUTHOR]

Active learning and training is a particularly effective form of education. In various domains, skills are equally important to knowledge. We present an automated learning and skills training system for a database programming environment that promotes procedural knowledge acquisition and skills training. The system provides meaningful knowledge-level feedback such as correction of student solutions and personalized guidance through recommendations. Specifically, we address automated synchronous feedback and recommendations based on personalized performance assessment. At the core of the tutoring system is a pattern-based error classification and correction component that analyzes student input in order to provide immediate feedback and in order to diagnose student weaknesses and suggest further study material. A syntax-driven approach based on grammars and syntax trees provides the solution for a semantic analysis technique. Syntax tree abstractions and comparison techniques based on equivalence rules and pattern matching are specific approaches. [ABSTRACT FROM AUTHOR]

The SPAROL LeftJoin abstract operator is not distributive over union; this limits the algebraic manipulation of graph patterns, which in turn restricts the ability to create query plans for distributed processing or query optimization. In this paper, we present semQA, an algebraic extension for the SPARQL query language for RDF, which overcomes this issue by transforming graph patterns through the use of an idempotent disjunction operator Or as a substitute for Union. This permits the application of a set of equivalences that transform a query into distinct forms. We further present an algorithm to derive the solution set of the original query from the solution set of a query where Union has been substituted by Or. We also analyze the combined complexity of SPARQL, proving it to be NP-complete. It is also shown that the SPARQL query language is not, in the general case, fixed-parameter tractable. Experimental results are presented to validate the query evaluation methodology presented in this paper against the SPARQL standard to corroborate the complexity analysis and to illustrate the gains in processing cost reduction that can be obtained through the of semQA. [ABSTRACT FROM AUTHOR]

Data cubes for OLAP (On-Line Analytical Processing) often need to be constructed from data located in several distributed and autonomous information sources. Such a data integration process is challenging due to semantic, syntactic, and structural heterogeneity among the data. While XML (extensible markup language) is the de facto standard for data exchange, the three types of heterogeneity remain. Moreover, popular path-oriented XML query languages, such as XQuery, require the user to know in much detail the structure of the documents to be processed and are, thus, effectively impractical in many real-world data integration tasks. Several Lowest Common Ancestor (LCA)-based XML query evaluation strategies have recently been introduced to provide a more structure-independent way to access XML documents. We shall, however, show that this approach leads in the context of certain—not uncommon—types of XML documents to undesirable results. This article introduces a novel high-level data extraction primitive that utilizes the purpose-built Smallest Possible Context (SPC) query evaluation strategy. We demonstrate, through a system prototype for OLAP data cube construction and a sample application in informetrics, that our approach has real advantages in data integration. [ABSTRACT FROM AUTHOR]

The whole product life cycle consists of three phases: Beginning of Life (BOL), Middle of Life (MOL), and End of Life (EOL). Although large amounts of product life-cycle data are generated over the whole product life cycle, data flows are rather vague after BOL. Over the last decade, however, emerging Internet, wireless mobile telecommunications, and product identification technologies have created the potential of making the whole product life cycle visible. As a result, the scope of data to be managed has expanded over the whole product life cycle. Hence, it becomes important to describe product life-cycle metadata in a systematic manner. Although much attention has been paid to data modeling over several objects such as products and processes, modeling methodology for product life-cycle metadata is not well developed. To cope with this limitation, we develop a modeling method for product life-cycle metadata by using the resource description framework (RDF). We define an RDF data model and its schema for describing and managing product life-cycle metadata. In addition, we describe how the proposed RDF model can be usefully applied to track, trace, and infer product life-cycle data with an RDF query language. [ABSTRACT FROM AUTHOR]

In our query language introduced in Part I (Niemi & Jämsen, in press) the user can formulate queries to find out (possibly complex) semantic relationships among entities. In this article we demonstrate the usage of our query language and discuss the new applications that it supports. We categorize several query types and give sample queries. The query types are categorized based on whether the entities specified in a query are known or unknown to the user in advance, and whether text information in documents is utilized. Natural language is used to represent the results of queries in order to facilitate correct interpretation by the user. We discuss briefly the issues related to the prototype implementation of the query language and show that an independent operation like Rho (Sheth et al., 2005; Anyanwu & Sheth, 2002, 2003), which presupposes entities of interest to be known in advance, is exceedingly inefficient in emulating the behavior of our query language. The discussion also covers potential problems, and challenges for future work. [ABSTRACT FROM AUTHOR]

Purpose - An issue that tends to be ignored in information retrieval is the issue of updating inverted files. This is largely because inverted files were devised to provide fast query service, and much work has been done with the emphasis strongly on queries. This paper aims to study the effect of using parallel methods for the update of inverted files in order to reduce costs, by looking at two types of partitioning for inverted files: document identifier and term identifier. Design/methodology/approach - Raw update service and update with query service are studied with these partitioning schemes using an incremental update strategy. The paper uses standard measures used in parallel computing such as speedup to examine the computing results and also the costs of reorganising indexes while servicing transactions. Findings - Empirical results show that for both transaction processing and index reorganisation the document identifier method is superior. However, there is evidence that the term identifier partitioning method could be useful in a concurrent transaction processing context. Practical implications - There is an increasing need to service updates, which is now becoming a requirement of inverted files (for dynamic collections such as the web), demonstrating that a shift in requirements of inverted file maintenance is needed from the past. Originality/value - The paper is of value to database administrators who manage large-scale and dynamic text collections, and who need to use parallel computing to implement their text retrieval services. [ABSTRACT FROM AUTHOR]

Abstract: The real world is inherently three dimensional. Therefore it is natural to represent it in 3D. Many application domains such as architecture, urban planning, epidemiology, and virtual reality require representation of objects in three dimensions. These applications require an effective way of querying three dimensional data. Querying 3D objects based on their exact geometry has proven to be computationally expensive. This paper presents a representation that approximates the geometry of 3D objects. This representation is based on 3D line segments. We compare the proposed representation with the polyhedral representation to detect collision between two objects. Our experiments show that our representation can reduce significantly the computation time to detect collisions. We also show how our representation combined with meta-data can be used to effectively query 3D objects. [Copyright &y& Elsevier]

Abstract: Performing complex analysis on top of massive data stores is essential to most modern enterprises and organizations and requires significant aggregation over different attribute sets (dimensions) of the participating relations. Such queries may take hours or days, a time period unacceptable in most cases. As a result, it is important to study these queries and identify special frequent cases that can be evaluated with specialized algorithms. Understanding complex aggregate queries leads to better execution plans and, consequently, performance. The idea of partitioning is fundamental and central in aggregate queries. This concept can be used to define a class of queries called group queries. The main characteristic of a group query is that it can be evaluated in a partitioned (or groupwise) fashion, i.e. the underlying relation(s) can be partitioned (based on a set of attributes) into disjoint groups and each group can be processed separately, possibly in parallel. For example, a query that performs a complex operation (e.g. joins and/or selections and/or aggregations) within each group is a group query. To express it in SQL, one has to join/correlate several views and/or subqueries on the grouping attributes. A naive plan (where the joins are executed) may be very expensive, even for relatively small base relations. On the other hand, a groupwise evaluation can lead to huge performance gains. We present a syntactic criterion to identify group queries in SQL and show that every group query can be expressed in a way that satisfies this criterion. This work is based on Chatziantoniou and Ross [Querying Multiple Features of Groups in Relational Databases. in: 22nd International Conference on Very Large Databases, VLDB, 1996, pp. 295–306]. The concept of group queries is useful not only in terms of evaluation, but also in terms of analyzing a complex decision support query that aggregates over different sets of attributes. In such a case the query may be decomposable to one or more query components, where each component is a group query. This observation allows parallel execution, multi-query processing and identification of special cases. We present in this paper two algorithms to decompose a complex aggregate query to its group query components. The value of groupwise processing has been recently recognized by the research community and implemented in at least a major commercial system. To be of use however in a relational system, partitioned evaluation has to be modeled as a relational operator. We review three different approaches for such an operator and propose a generalized groupwise operator. We also perform some experiments to show that naive optimization with the new operator incorporated without taking into consideration decompositions to group query components does not always lead to the most efficient plans. An extended syntax is another way to identify special frequent cases and apply efficient algorithms. Having specific operators for common operations contributes to the succinctness and optimizability of certain queries (e.g. datacubes). An extended syntax is presented with emphasis for multi-feature queries, a frequent and practical subclass of group queries that is amenable to specialized evaluation, involving (potentially repeated) selection, grouping and aggregation over the same groups. [Copyright &y& Elsevier]

The Resource Description Framework (RDF) is a metadata model and language recommended by the W3C. This paper presents a framework to incorporate temporal reasoning into RDF, yielding temporal RDF graphs. We present a semantics for these kinds of graphs which includes the notion of temporal entailment and a syntax to incorporate this framework into standard RDF graphs, using the RDF vocabulary plus temporal labels. We give a characterization of temporal entailment in terms of RDF entailment and show that the former does not yield extra asymptotic complexity with respect to nontemporal RDF graphs. We also discuss temporal RDF graphs with anonymous timestamps, providing a theoretical framework !or the study of temporal anonymity. Finally, we sketch a temporal query language for RDF, along with complexity results for query evaluation that show that the time dimension preserves the tractability of answers. [ABSTRACT FROM AUTHOR]

The research presented in this paper is situated in the framework of constraint databases introduced by Kanellakis, Kuper, and Revesz in their seminal paper of 1990, specifically, the language with real polynomial constraints (FO + poly). For reasons of efficiency, this model is implemented with only linear polynomial constraints, but this limitation to linear polynomial constraints has severe implications on the expressive power of the query language. In particular, when used for modeling spatial data, important queries that involve Euclidean distance are not expressible. The aim of this paper is to identify a class of two-dimensional constraint databases and a query language within the constraint model that go beyond the linear model and allow the expression of queries concerning distance. We seek inspiration in the Euclidean constructions, i.e., constructions by ruler and compass. We first present a programming language that captures exactly the first-order ruler-and-compass constructions that are expressible in a first-order language with real polynomial constraints. If this language is extended with a while operator, we obtain a language that is complete for all ruler-and-compass constructions in the plane. We then transform this language in a natural way into a query language on finite point databases, but this language turns out to have the same expressive power as FO + poly and is therefore too powerful for our purposes. We then consider a safe fragment of this language and use this to construct a query language that allows the expression of Euclidean distance without having the full power of FO + poly. [ABSTRACT FROM AUTHOR]

Abstract: We consider the problem of answering queries using views, where queries and views are conjunctive queries with arithmetic comparisons over dense orders. Previous work only considered limited variants of this problem, without giving a complete solution. We first show that obtaining equivalent rewritings for conjunctive queries with arithmetic comparisons is decidable. Then, we consider the problem of finding maximally contained rewritings (MCRs) where the decidability proof does not carry over. We investigate two special cases of this problem where the query uses only semi-interval comparisons. In both cases decidability of finding MCRs depends on the query containment test. First, we address the case where the homomorphism property holds in testing query containment. In this case decidability is easy to prove but developing an efficient algorithm is not trivial. We develop such an algorithm and prove that it is sound and complete. This algorithm applies in many cases where the query uses only left (or right) semi-interval comparisons. Then, we develop a new query containment test for the case where the containing query uses both left and right semi-interval comparisons but with only one left (or right) semi-interval subgoal. Based on this test, we show how to produce an MCR which is a Datalog query with arithmetic comparisons. The containment test that we develop obtains a result of independent interest. It finds another special case where query containment in the presence of arithmetic comparisons can be tested in nondeterministic polynomial time. [Copyright &y& Elsevier]