Search

We propose the first known solution to the problem of correlating, in small space, continuous streams of XML data through approximate (structure and content) matching, as defined by a general tree-edit distance metric. The key element of our solution is a novel algorithm for obliviously embedding tree-edit distance metrics into an L1 vector space while guaranteeing a (worst-case) upper bound of O([log.sup.2] n log* n) on the distance distortion between any data trees with at most n nodes. We demonstrate how our embedding algorithm can be applied in conjunction with known random sketching techniques to (1) build a compact synopsis of a massive, streaming XML data tree that can be used as a concise surrogate for the full tree in approximate tree-edit distance computations; and (2) approximate the result of tree-edit-distance similarity joins over continuous XML document streams. Experimental results from an empirical study with both synthetic and real-life XML data trees validate our approach, demonstrating that the average-case behavior of our embedding techniques is much better than what would be predicted from our theoretical worst-case distortion bounds. To the best of our knowledge, these are the first algorithmic results on low-distortion embeddings for tree-edit distance metrics, and on correlating (e.g., through similarity joins) XML data in the streaming model. Categories and Subject Descriptors: H.2.4 [Database Management]: Systems--Query processing; G.2.1 [Discrete Mathematics]: Combinatorics--Combinatorial algorithms General Terms: Algorithms, Performance, Theory Additional Key Words and Phrases: XML, data streams, data synopses, approximate query processing, tree-edit distance, metric-space embeddings

Commercial relational database systems lack support for complex business modeling. ANSI SQL cannot treat relations as multidimensional arrays and define multiple, interrelated formulas over them, operations which are needed for business modeling. Relational OLAP (ROLAP) applications have to perform such tasks using joins, SQL Window Functions, complex CASE expressions, and the GROUP BY operator simulating the pivot operation. The designated place in SQL for calculations is the SELECT clause, which is extremely limiting and forces the user to generate queries with nested views, subqueries and complex joins. Furthermore, SQL query optimizers are preoccupied with determining efficient join orders and choosing optimal access methods and largely disregard optimization of multiple, interrelated formulas. Research into execution methods has thus far concentrated on efficient computation of data cubes and cube compression rather than on access structures for random, interrow calculations. This has created a gap that has been filled by spreadsheets and specialized MOLAP engines, which are good at specification of formulas for modeling but lack the formalism of the relational model, are difficult to coordinate across large user groups, exhibit scalability problems, and require replication of data between the tool and RDBMS. This article presents an SQL extension called SQL Spreadsheet, to provide array calculations over relations for complex modeling. We present optimizations, access structures, and execution models for processing them efficiently. Special attention is paid to compile time optimization for expensive operations like aggregation. Furthermore, ANSI SQL does not provide a good separation between data and computation and hence cannot support parameterization for SQL Spreadsheets models. We propose two parameterization methods for SQL. One parameterizes ANSI SQL view using subqueries and scalars, which allows passing data to SQL Spreadsheet. Another method presents parameterization of the SQL Spreadsheet formulas. This supports building stand-alone SQL Spreadsheet libraries. These models are then subject to the SQL Spreadsheet optimizations during model invocation time. Categories and Subject Descriptors: H.2.3. [Database Management]: Languages--Data manipulation languages (DML); query languages; H.2.4. [Database Management]: Systems--Query processing General Terms: Design, Languages Additional Key Words and Phrases: Excel, analytic computations, OLAP, spreadsheet

We discuss the design of an acquisitional query processor for data collection in sensor networks. Acquisitional issues are those that pertain to where, when, and how often data is physically acquired (sampled) and delivered to query processing operators. By focusing on the locations and costs of acquiring data, we are able to significantly reduce power consumption over traditional passive systems that assume the a priori existence of data. We discuss simple extensions to SQL for controlling data acquisition, and show how acquisitional issues influence query optimization, dissemination, and execution. We evaluate these issues in the context of TinyDB, a distributed query processor for smart sensor devices, and show how acquisitional techniques can provide significant reductions in power consumption on our sensor devices. Categories and Subject Descriptors: H.2.3 [Database Management]: Languages--Query languages; H.2.4 [Database Management]: Systems--Distributed databases; query processing General Terms: Experimentation, Performance Additional Key Words and Phrases: Query processing, sensor networks, data acquisition

XML is becoming the universal format for data exchange between applications. Recently, the emergence of Web services as standard means of publishing and accessing data on the Web introduced a new class of XML documents, which we call intensional documents. These are XML documents where some of the data is given explicitly while other parts are defined only intensionally by means of embedded calls to Web services. When such documents are exchanged between applications, one has the choice of whether or not to materialize the intensional data (i.e., to invoke the embedded calls) before the document is sent. This choice may be influenced by various parameters, such as performance and security considerations. This article addresses the problem of guiding this materialization process. We argue that--like for regular XML data--schemas (a la DTD and XML Schema) can be used to control the exchange of intensional data and, in particular, to determine which data should be materialized before sending a document, and which should not. We formalize the problem and provide algorithms to solve it. We also present an implementation that complies with real-life standards for XML data, schemas, and Web services, and is used in the Active XML system. We illustrate the usefulness of this approach through a real-life application for peer-to-peer news exchange. Categories and Subject Descriptors: H.2.5 [Database Management]: Heterogeneous Databases General Terms: Algorithms, Languages, Verification Additional Key Words and Phrases: Data exchange, intensional information, typing, Web services, XML

The use of intranets or the Internet has also increased the difficulties experienced by chemists in the storing and sharing of data. The need to share information requires chemists to store data in formats that can be 'mined' by other users. To aid chemists and other users take advantage of the new the technology software vendors have created middleware-based software that will help the users in combining several data types and at the same time perform format interchanges.

The GSI data acquisition system MBS (Multi Branch System) has become, since its introduction in 1994, the standard system at GSI (37 local and 9 portable systems). It is also used at numerous outside laboratories (29 systems). Compared to phase I of the system [1], the current version MBS 3.0 offers four new major enhancements: 1. Support of event builder hierarchies. 2. Support of message oriented busses and networks. 3. Multiple parallel event builders. 4. A multi-threaded graphical user interface (Java). The software supports various hardware setups and topologies.

The Virgo experiment is a challenge in many aspects, particularly for the control-command environment. The essential requirements for flexibility and reliability, induced by the very drastic technical constraints as well as the unapprehended nature of the overall logic imply that strong and well-defined paradigms are used throughout the building phases of this environment. This results in providing a software architecture, called the Supervisor environment based upon some basic principles such as the component oriented packaging or the use of scriptable formal languages. In addition, keeping this architecture simple and well defined makes it compliant with quality requirements for long term maintenance, evolution and interoperability. This environment provides the basic services required by user applications to operate the experiment such as communication, database management, error handling, logic and graphical control as a set of interoperable components making extensive use of the object oriented paradigm and of the scriptable specification languages. The Supervisor itself is the basic control application and can be cloned, refined and customized to extend the basic logic towards specific needs. The presentation will show some of the basic ingredients of this architecture, and will discuss how user control applications have been integrated in this environment.