In this poster, we present the P2P XML data localization layer of XLive, an XQuery mediation system developed at University of Versailles [2]. A major challenge in the evaluation of XQuery over a P2P network in the context of multiple XML sources is to abstract from structural heterogeneity. Most existing approaches have mainly exploited varied types of 1:1 semantic mappings between peer schemas and/or ontologies. Complex query algorithms are required to exploit these semantic links between peers. In contrast, our approach focuses on a simple semantic layer. It is built on a Chord [4] DHT for indexing semantic descriptions of mediated data sources. A mapping process transforms an XML view of a mediator (each peer is equipped with a mediator) to a semantic form that is published into the P2P network and stored in the DHT. For a given user query, a search in the DHT retrieves all relevant data sources able to contribute to the result elaboration. Then, every peer that contains relevant data is directly queried to collect data for elaborating the final answer.

We present the WebContent platform for managing distributed repositories of XML and semantic Web data. The platform allows integrating various data processing building blocks (crawling, translation, semantic annotation, full-text search, structured XML querying, and semantic querying), presented as Web services, into a large-scale efficient platform. Calls to various services are combined inside ActiveXML [8] documents, which are XML documents including service calls. An ActiveXML optimizer is used to: ( i ) efficiently distribute computations among sites; ( ii ) perform XQuery-specific optimizations by leveraging an algebraic XQuery optimizer; and ( iii ) given an XML query, chose among several distributed indices the most appropriate in order to answer the query.

In this paper, we propose a new classification method that addresses classification in multiple categories of textual documents. We call it Matrix Regression (MR) due to its resemblance to regression in a high dimensional space. Experiences on a medical corpus of hospital records to be classified by ICD (International Classification of Diseases) code demonstrate the validity of the MR approach. We compared MR with three frequently used algorithms in text categorization that are k-Nearest Neighbors, Centroide and Support Vector Machine. The experimental results show that our method outperforms them in both precision and time of classification.

The current abundance and complexity of P2P architectures makes it extremely difficult to assess their performance. P2PTester is the first tool devised to interface with, and measure the performance of, existing P2P data management platforms. We isolate basic components present in current P2P platforms, and insert "hooks" for P2PTester to capture, analyze and trace the interactions taking place in the underlying distributed system.

We analyzes category score algorithms for k-NN classifier found in the literature, including majority voting algorithm (MVA), simple sum algorithm (SSA). MVA and SSA are two mainly used algorithms to estimate score for candidate categories in k-NN classifier systems. Based on the hypothesis that utilization of internal relation between documents and categories could improve system performance, two new weighting score models: concept-based weighting (CBW) score model and term independence-based weighting (IBW) score model are proposed. Our experimental results confirm our hypothesis and show that in the term of precision average IBW and CBW are better than the other score models, while SSA is higher than MVA. According to macro-average F1 CBW performs best. Rocchio-based algorithm (RBA) always performs worst.

Clustering is one of the important techniques in data mining. The objective of clustering is to group objects into clusters such that objects within a cluster are more similar to each other than objects in different clusters. The similarity between two objects is defined by a distance function, e.g., the Euclidean distance, which satisfies the triangular inequality. Distance calculation is computationally very expensive and many algorithms have been proposed so far to solve this problem. This paper considers the gradual clustering problem. From practice, we noticed that the user often begins clustering on a small number of attributes, e.g., two. If the result is partially satisfying the user will continue clustering on a higher number of attributes, e.g., ten. We refer to this problem as the gradual clustering problem. In fact gradual clustering can be considered as vertically incremental clustering. Approaches are proposed to solve this problem. The main idea is to reduce the number of distance calculations by using the triangle inequality. Our method first stores in an index the distances between a representative object and objects in n-dimensional space. Then these pre-computed distances are used to avoid distance calculations in (n+m)-dimensional space. Two experiments on real data sets demonstrate the added value of our approaches. The implemented algorithms are based on the DBSCAN algorithm with an associated M-Tree as index tree. However the principles of our idea can well be integrated with other tree structures such as MVP-Tree, R*-Tree, etc., and with other clustering algorithms.

In this paper, we present our experiences on managing semi-structured data in relational databases. We use a Java package built on top of relational database for store and query semi-structured data. In this work, we introduced a more complete data model, a flexible storage scheme, and a compact metedata structure for processing regular path expressions.

Distributed systems require declarative access to diverse information sources. One approach to solving this heterogeneous distributed database problem is based on mediator architectures. In these architectures, mediators accept queries from users, process them with respect to wrappers, and return answers. Wrappers provide access to underlying sources. To efficiently process queries, the mediator must optimize the plan used for processing the query. In classical databases, cost-estimate based query optimization is effective. In a heterogeneous distributed databases, cost-estimate based query optimization is difficult to achieve because the underlying data sources do not export cost information. This paper describes a new method that permits the wrapper programmer to export cost estimates. For the wrapper programmer to describe all cost estimates may be impossible due to lack of information or burdensome due to the amount of information. We ease this responsibility of the wrapper programmer by leveraging the generic cost model of the mediator with specific cost estimates from the wrappers.

From the beginning of 1994 to the end of 1996, the IRO-DB (Interoperable Relational and Object-Oriented Databases) ESPRIT project has developed tools for accessing relational and object-oriented databases in an integrated way, and for designing and maintaining integrated applications on large federations of heterogeneous databases. IRO-DB is based on the ODMG pivotal object model and gives an OQL/OML-C++ interface to users on a federation of relational and object-oriented databases. This paper summarizes the main problems and choices done during the system design, describes the IRO-DB architecture and components, presents the project's achievements and gives a synthesis of the lessons learned during the project's development. It also introduces future plans for the system.

We present a functional paradigm for querying efficiently abstract collections of complex objects. Abstract collections are used to model class extents, multivalued attributes as well as indexes or hashing tables. Our paradigm includes a functional language called OFL (Object Functional Language) and a supporting execution model based on graph traversals. OFL is able to support any complex object algebra with recursion as macros. It is an appropriate target language for OQL-like query compilers. The execution model provides various strategies including set-oriented and pipelined traversals. OFL has been implemented on top of an object manager. Measures of a typical query extracted from a geographical benchmark show the value of hybrid strategies integrating pipelined and set-oriented evaluations. They also show the potential of function result memorization, a typical optimization approach known as "Memoization" 2 in functional languages.

ESQL2 is an SQL2 upward-compatible database language that integrates the essential concepts of relational, object-oriented, and deductive databases. ESQL2's salient features are a rich and extendible type system based on abstract data types (ADTs) implemented in various programming languages, complex objects with object sharing by combining generic ADTs and object identity, the capability of querying and updating relations containing simple or complex objects using SQL-compatible syntax and semantics, and a DATALOG-like deductive capability provided as an extension of the SQL view mechanism. A declarative semantics is proposed for ESQL2 retrieval statements using F-Logic, which provides a solid basis for understanding the integration of objects and relations.>

An integrated approach to query rewriting in an extensible database server supporting ADTs, objects, deductive capabilities and integrity constraints is described. The approach is extensible through a uniform high level rule language used by the database implementor to specify optimization techniques. This rule language is compiled to enrich the strategy component and the knowledge base of the rewriter. Rules can be added to specify various aspects of query rewriting, including operation permutation, recursive query processing, integrity constraint addition, predicate simplification and method call simplification.>

In this paper, we first propose a natural syntactical extension of DATALOG called NESTED_DATALOG for dealing with complex objects represented as nested predicates. Then, we introduce the token object model which is a simple extension of the relational model with tokens to represent complex objects and support referential information sharing. An implementation model of a NESTED_DATALOG program is defined by mapping it to the token object model which remains a straightforward extension of classical logical databases. Through this work, we can accommodate two basic requirements. The availability of a rule language for reasoning with complex objects, and the mechanism for mapping a complex object rule program to a relational DBMS offering a pure DATALOG rule language. In summary, the main contributions of the paper are the definition of a rule language for complex objects and the development of a technique to compile this complex object rule language to classical DATALOG.

The authors introduce a new method to compile queries referencing recursively defined predicates. This method is based on an interpretation of the query and the relations as functions which map one column of a relation to another column. It is shown that a large class of queries with associated recursive rules, including mutually recursive rules, can be computed as the limit of a series of functions. Typical cases of series of functions are given and solved. The solutions lend themselves towards either extended relational algebra or SQL optimized programs to compute the recursive query answers. Examples of applications are given.

With the advent of relational database systems, multi-key searching problems have became the focus of a great deal of research. In this paper, we present a new data structure called predicate trees for clustering tuples of a relation in a way that allows the system to accelerate a large number of multi-dimensional queries. The directories used for the implementation of predicate trees in SABRE are organized as relations which are searched efficiently by filters. One of the most significant advantages of predicate trees is the possibility of defining logical addresses based on content, called signatures, and to use filters to manage directories.

This paper presents and analyzes algorithms for computing joins and semijoins of relations in a multiprocessor database machine. First, a model of the multiprocessor architecture is described, incorporating parameters defining I/O, CPU, and message transmission times that permit calculation of the execution times of these algorithms. Then, three join algorithms are presented and compared. It is shown that, for a given configuration, each algorithm has an application domain defined by the characteristics of the operand and result relations. Since a semijoin operator is useful for decreasing I/O and transmission times in a multiprocessor system, we present and compare two equi-semijoin algorithms and one non-equi-semijoin algorithm. The execution times of these algorithms are generally linearly proportional to the size of the operand and result relations, and inversely proportional to the number of processors. We then compare a method which consists of joining two relations to a method whereby one joins their semijoins. Finally, it is shown that the latter method, using semijoins, is generally better. The various algorithms presented are implemented in the SABRE database system; an evaluation model selects the best algorithm for performing a join according to the results presented here. A first version of the SABRE system is currently operational at INRIA.

The purpose of this correspondence is to present an approach for verifying that explicitly stated integrity constraints are not violated by certain transactions. We utilize a relational model wherein constraints are given in a language based on the first-order predicate calculus. Transactions are written in terms of a Pascal-like host language with embedded first-order predicate calculus capabilities allowing queries and updates.

This paper presents a deadlock-free and distributed control algorithm for robustly and consistently updating replicated databases. This algorithm is based on local locking and time stamps on lock tables which permit detection of conflicts among transactions executed at different sites. Messages are exchanged in the network whenever a transaction commitment occurs, that is, at the end of every consistent step of local processing. Conflicts among remote transactions are resolved by a roll back procedure. Local restart is based on a journal of locks which provides backup facilities. Performance in terms of the number of messages and volume of control messages of the proposed algorithm is compared with that of the voting and centralized locking algorithms. These results reveal that the proposed distributed control algorithm performs, in most cases, comparably to the centralized locking algorithm and better than the voting algorithm.

This paper presents a robust, deadlock-free and distributed control algorithm for consistently updating replicated databases. This algorithm is based on local locking and time stamps on lock tables which permit detection of conflicts among transactions executed at replicated databases. Messages are exchanged in the network whenever a transaction commitment occurs, that is, at the end of every consistent step of local processing. Conflicts among remote transactions are resolved by a roll back procedure. Local restart is based on a journal of locks which provides backup facilities. Performance in terms of the number of messages and volume of control messages of the proposed algorithm is compared with that of the voting and centralized locking algorithms. The results reveal that the proposed distributed control algorithm performs, in most cases, comparably to the centralized locking algorithm and better than the voting algorithm.