For centuries, sheet music scores have been the traditional way to preserve and disseminate Western music works. Nowadays, their content can be encoded in digital formats, making possible to store music score data in digital score libraries (DSL). To supply intelligent services (extracting and analysing relevant information from data), the new generation of DSL has to rely on digital representations of the score content as structured objects apt at being manipulated by high-level operators. In the present paper, we propose the Muster model, a graph-based data model for representing the music content of a digital score, and we discuss the querying of such data through graph pattern queries. We then present a proof-of-concept of this approach, which allows storing graph-based representations of music scores in the Neo4j database, and performing musical pattern searches through graph pattern queries with the Cypher query language. A benchmark study, using (real) datasets stemming from the Neuma Digital Score Library, complements this implementation.

We examine the problem of quality awareness when querying graph databases. According to quality annotations that denote quality problems appearing in data subgraphs (the annotations typically result from collaborative practices in the context of open data usage like e.g. users' feedbacks), we propose a notion of quality aware (graph pattern) query based on (usage-dependent) quality profiles. In this paper, we present the formal foundations of the approach. We also show how to simply extend a generic state-of-the-art algorithm for graph pattern queries evaluation in order to implement quality awareness at evaluation time and we study its complexity. We then expose implementation guidelines, supported by a proof-of-concept prototype based on the Neo4J graph database management system.

Digital music scores are a way to present music notation and lack of semantic information useful for musicology purposes in order to manipulate music concepts. We propose a general approach to extend score encodings with semantic annotations. It relies on an ontology of music notation designed to integrate semantic music elements either extracted or produced by a knowledge process. We illustrate the whole mechanism by extracting RDF facts based on the identification of dissonances in Renaissance counterpoint.

We consider the emerging field of music score libraries, where documents rely on a music notation markup language such as MusicXML or MEI. We propose to model as synchronized time-series the music structure that can be extracted from such documents, together with an algebra that operates in closed form and allows manipulations, restructurings, and combinations of music scores stored in a database. We formally present the model, its algebraic operators, and finally show how our approach can serve as a building block for a query and analytic language on large collections of XML-encoded music scores.

File names are one of the earliest computing abstractions, a string of characters to uniquely identify a file for the system, and to help users remember the contents when they look for it later. They are also a rich source of semantic metadata about files. However, this metadata is unstructured and opaque to the rest of the system. As a result, metadata in file names is often error-prone, and hard to search for. File names can and should be more meaningful and reliable, while simplifying application design and encouraging users and applications to provide more metadata for search.

The demonstration is devoted to the desktop-level interactions offered by Cador, a content-based document management system currently under development. Cador provides a rule-based language to query and manipulate large collections of documents distributed in repositories. The language is able to define the content of Virtual File Systems (VFS) as views over the document collections. This feature allows users to combine their familiar interface and desktop-based softwares with the powerful search and transformation tools provided by the underlying system.

We consider the class of applications that manage time series (TS) and propose a data model and a query language that let these applications manipulate TS data sets at a logical level. We introduce the concept of synchronized time series (STS) to model the alignment of several time series in a common time space. We show how this concept helps to analyze and compare information extracted from time series, and how it constitutes a convenient tool that supports an extended set of operations. The main contribution of the paper is a formal query language that combines generic operators on TS with user-defined functions. The language can be evaluated in closed form over STS data sets and gives rise to rewriting and optimization techniques. Throughout the paper, we illustrate our approach with several examples drawn from a few representative TS applications.

AS-Index is a new index structure for exact string search in disk resident databases. It uses hashing, unlike known alternatives, whether baesd on trees or tries. It typically indexes every n-gram in the database, though non-dense indexing is possible. The hash function uses the algebraic signatures of n-grams. Use of hashing provides for constant index access time for arbitrarily long patterns, unlike other structures whose search cost is at best logarithmic. The storage overhead of AS-Index is basically 500 - 600%, similar to that ofalternatives or smaller. We show the index structure, our use of algebraic signatures and the search algorithm. We present the theoretical and experimental performance analysis. We compare the AS-Index to main alternatives. We conclude that AS-Index is an attractive structure and we indicate directions for future work.

We consider the class of database programs and address the problem of minimizing the cost of their exchanges with the database server. This cost partly consists of query execution at the server side, and partly of query submission and network exchanges between the program and the server. The natural organization of database programs leads to submit an intensive flow of elementary SQL queries to the server, and exploits only locally its optimization power. In this paper, we develop a global optimization approach. We base this approach on an execution model where queries can be executed asynchronously with respect to the flow of the application program. Our method aims at choosing an efficient query scheduling which limits the penalty of client/server interactions. Our results show that the technique can improve the execution time of database programs by several orders of magnitude.

We propose an approach for producing database publishing programs by example. The main idea is to interactively build an example document, representative of the program output. The system infers from this document, without ambiguity, the publishing program. The end-user does not need to know a programming language, a query language or the database schema.

We propose a general framework to index very large datasets of spatial data in a distributed system. Our proposal is built on the recently proposed Scalable Distributed Rtree (SD-Rtree) [4] and addresses specifically the server allocation problem. In SD-Rtree, a new server is assigned to the network whenever a split of a full node is required. We describe a more flexible allocation protocol which copes with a temporary shortage of storage resources. Our algorithm is especially based on k-NN query processing we introduce as well. We analyze the cost of this protocol, describe its features, and propose practical hints to use it. We also present experiments validating our approach.

We propose a scalable distributed data structure (SDDS) called SD-Rtree. We intend our structure for point and window queries over possibly large spatial datasets distributed on clusters of interconnected servers. SD-Rtree generalizes the well-known Rtree structure. It uses a distributed balanced binary spatial tree that scales with insertions to potentially any number of storage servers through splits of the overloaded ones. A user/application manipulates the structure from a client node. The client addresses the tree through its image that the splits can make outdated. This may generate addressing errors, solved by the forwarding among the servers. Specific messages towards the clients incrementally correct the outdated images.

The paper presents a framework for publishing relational databases in textual documents such as mails, HTML pages, LATEX or BibTex files, plain texts, etc. The publication process relies on a mapping of the relational database to a virtual data graph which supports navigation operators. Applications can express the data they need by navigating in the graph. These operations are provided by a declarative query language over virtual graphs, named DOCQL. We illustrate its features with the conference management system MYREVIEW

We consider an environment where a subscription system continuously evaluates pattern-based requests over unbounded sequential data. We propose an extension of the traditional pattern-matching techniques for efficiently handling large sets of such continuous queries. This extension relies on the introduction of variables in patterns in order to augment their expressivity. Based on this extended class of parameterized queries, our main contributions are threefold. First, we define a refinement relation based on variable relaxation. Second, we use the semi-lattice structure of the set of parameterized patterns for patterns aggregation and filtering. We propose an on-line pattern aggregation algorithm so as to both reduce the cost of pattern-matching evaluation as well as to filter out sequences that cannot match any of the patterns in a subscription cluster. Finally we show, through analysis and experiments, that our technique reduces quite effectively the cost of the matching process

Many applications rely on sequence databases and use extensively pattern-matching queries to retrieve data of interest. This paper extends the traditional pattern-matching expressions to parameterized patterns, featuring variables. Parameterized patterns are more expressive and allow to define concisely regular expressions that would be very complex to describe without variables. They can also be used to express additional constraints on patterns' variables.We show that they can be evaluated without additional cost with respect to traditional techniques (e.g., the Knuth-Morris-Pratt algorithm). We describe an algorithm that enjoys low memory and CPU time requirements, and provide experimental results which illustrate the gain of the optimized solution.

This paper addresses fundamental issues related to the modeling of geometric data embedded in high-dimensional spaces. This covers several application fields, including moving objects where trajectories are described in a three- or four-dimensional space, and digital elevation models (DEMs). We show that moving objects and DEMs are specific instances of a broader class of complex spatial data that require the interpolation of values from collections of samples. We propose to model such data conceptually using infinite relations (e.g. the trajectory of a moving point yields an infinite ternary relation) which can be manipulated through standard relational query languages (e.g. SQL), with no mention of the interpolated definition. This approach is simple and establishes a clear separation between logical and physical levels. It permits the expression of queries on spatio-temporal databases in a purely declarative way. Next, we investigate algorithms for evaluating queries on interpolated data. In the general cases, the cost of manipulating $d$-dimensional data is exponential in $d$. We describe how to use rewriting and optimization techniques in order to evaluate queries with a small set of algorithms running in dimension 2, thus making the complexity independent from the global dimension.

We propose a new algorithm to solve the problem of joining two spatial relations R and S when S is indexed by an R-tree. The method combines classical query processing techniques and a plane-sweeping algorithm. We compare our approach to the simple indexed-nested-loop method and to the state-of-the-art algorithms, and show through analysis and experiments on synthetic and real-life datasets that our method outperforms in most cases the other ones, both in CPU and I/O. More importantly it appears to be more robust regarding the many parameters involved in spatial query processing.

This paper presents DEDALE, a spatial database system intended to overcome some limitations of current systems by providing an abstract and non-specialized data model and query language for the representation and manipulation of spatial objects. DEDALE relies on a logical model based on linear constraints, which generalizes the constraint database model of [KKR90]. While in the classical constraint model, spatial data is always decomposed into its convex components, in DEDALE holes are allowed to fit the need of practical applications. The logical representation of spatial data although slightly more costly in memory, has the advantage of simplifying the algorithms. DEDALE relies on nested relations, in which all sorts of data (thematic, spatial, etc.) are stored in a uniform fashion. This new data model supports declarative query languages, which allow an intuitive and efficient manipulation of spatial objects. Their formal foundation constitutes a basis for practical query optimization. We describe several evaluation rules tailored for geometric data and give the specification of an optimizer module for spatial queries. Except for the latter module, the system has been fully implemented upon the O2 DBMS, thus proving the effectiveness of a constraint-based approach for the design of spatial database systems.