Motivation and Introduction

Virtual electronic market places and virtual enterprises have become important applications for query processing [Jhi00]. Building a scalable virtual B2B market place with hundreds or thousands of participating suppliers requires highly flexible, distributed query processing capabilities. Architecting an electronic market place as a data warehouse by integrating all the data from all participating enterprises in one centralized data repository incurs severe problems:

• Security and privacy violations: The participants of the market place have to relinquish the control over their data and entrust sensitive information to the market place host.
• Coherence problems: The coherence of highly dynamic data, such as availability and shipping information, may be violated due to outdated materialized data in the market place's data warehouse.
• Schema integration problems: Using the warehouse approach all relevant data from all participants have to be converted a priori into the same format. Often, it would be easier to leave the data inside the participant's information systems, e.g., legacy systems, within the local sites, and apply particular local wrapper operations. This way, data is only converted on demand and the most recent coherent state of the data is returned.
• Fixed query operators: In a data warehouse-like electronic market place, all information is converted into materialized data. This is often not desirable in such complex applications like electronic procurement/bidding. For example, in pricing offers one would like to have vastly different choices:
  • fixed pricing via materialized data
  • operators which calculate the prices based on a multitude of local and global parameters (identity of the consumer company, availability, sub-contractor prices, etc.)
  • even human interaction during the processing of such complex e-procurement queries is desirable. In some participating enterprises the pricing could be done by a human user via an interactive "query operator".

We propose a reference architecture for building scalable and dynamic market places and a framework for evaluating so-called HyperQueries in such an environment. HyperQueries are essentially query evaluation sub-plans "sitting behind" hyperlinks. This way the electronic market place can be built as an intermediary between the client and the providers executing their sub-queries referenced via hyperlinks. The hyperlinks are embedded as attribute values within data objects of the intermediary's database. Retrieving such a virtual object automatically initiates the execution of the referenced HyperQuery in order to materialize the entire object. Thus, sensitive data can remain under the full control of the data providers. Instead of replicating the data at the intermediary, only the hyperlink is embedded.

An Overview of the QueryFlow System

We give a short overview of the basic architecture of our implementation, the QueryFlow system [1]. The proposed architecture claims to be a reference architecture for building open, extensible, and scalable electronic B2B market places. Furthermore we demonstrate the execution of queries in such an environment. Figure 1 sketches how hyperlinks of the market place refer to HyperQueries at the remote hosts. Thereby the remote hosts have the possibility to implement the HyperQueries using different approaches: at first, a remote host can state an SQL query, second a complex business application or even human input can be used using special wrappers, and finally the remote hosts can delegate the query to further hosts.

Figure 1: HyperQueries are referenced by Hyperlinks

Architecture of the QueryFlow System

We propose a reference architecture for building scalable electronic market places. During the implementation of our prototypical system, we payed special attention to rely on standardized (or proposed) protocols such as: XML [BPSMM00] and XML Schema [XML00] for all data being processed, SQL for querying data [2], X.509 certificates [HFPS00] and XML Signature [XML01] for authentication, and HTTP [FGM+99] and SOAP [BEK+00] for exchanging data between multiple hosts. Figure 2 depicts the basic components of the system, that can be described as follows:

Figure 2: The Architecture of the QueryFlow System

• The query processing capabilities of the QueryFlow system are based on the ObjectGlobe system [BKK+01], which is a distributed and open query processor for data sources on the Internet.
• The communication between multiple instances of the QueryFlow system is implemented via a proprietary Messaging Service. Additionally SOAP as the emerging standard for transferring XML data provides an open interface both to integrate other systems and to be integrated by other systems.
• The HyperQuery Engine combines all operators that are specific for HyperQuery processing, i.e., for resolving the hyperlinks to HyperQueries (which is done by the so-called Dispatch operator), collecting incoming objects, and operators for optimization of HyperQuery execution (see [KW01a,KW01b]).
• The QueryFlow CoreSystem manages the instantiated HyperQueries and the distribution of the execution to multiple physical hosts. Furthermore all additional data structures such as caches and administrative data of the executed HyperQueries are managed within this component.
• The HyperQuery Instantiator manages the instantiation of HyperQueries at the remote sites. The HyperQueries are stored in a hierarchical structured repository that can be on top of the file system, a proprietary database, or a web server.
• The certificate-based HyperQuery Authenticator is used for signing requests and queries when sending them to hosts and verifying them at the destination. This component is based on the underlying ObjectGlobe security system.
• As already mentioned, the QueryFlow system processes XML data. The XML Integration component collects all functionality to access XML data sources and to handle semi-structured data.
  As the native data format of our system is relational, the processing of XML data is done the following way: we distinguish between XML elements that are needed during the execution of the query and elements that are not needed. The needed elements are transformed into the relational representation suitable for processing. The additional elements are passed as strings through the query-plan and are displayed to the client.
• Finally, we implemented an extensible QueryFlow ServiceManager for executing Java-based e-services. These services are required for administrative issues, e.g., for the registration of suppliers, products, and HyperQueries. The services can be accessed via the Messaging Service or the SOAP interface of the QueryFlow system.

Processing HyperQueries in the QueryFlow System

We demonstrate the HyperQuery technique with a scenario of the car manufacturing industry. We assume a hierarchical supply chain of suppliers and sub-contractors. A typical process of e-procurement to cover unscheduled demands of the production is to query a market place for these products and to select the incoming offers by price, terms of delivery, available quantity, etc. The price of the needed products can vary by customer/supplier-specific sales discounts, the quantity of materials to be provided, duties, plant utilization, etc.

In traditional distributed query processing systems such a query can only be executed if a global schema exists or all local databases are replicated at the market place. Considering an environment, where hundreds of suppliers participate in a market place, one global query which integrates the sub-queries for all participants would be too complex and error-prone.

Following our approach the suppliers have to register their products at the market place, which they want to participate in, and specify by hyperlinks the sub-plans to compute the price information at their sites. These hyperlinks to sub-plans are embedded as virtual attributes into the tables of the market place. For instance hq://supplier1.com/Price?ProdID=1255 would refer to supplier1.com and request at the remote host the calculation of ProdID=1255 with the sub-plan named Price.

The SQL-like query

select   p.ProductDescription, c.Supplier, c.Price 
from     NeededProducts p,  Catalog@MarketPlace c 
where    p.ProductDescription = c.ProductDescription 
order by p.ProductDescription, c.Price 
expires  Friday, May 18, 2001 5:00:00 PM CET

When evaluating these hyperlinks, our QueryFlow system distinguishes between two modes: In hierarchical mode (Figure 3(a)) the initiator of a HyperQuery is in the charge of collecting the processed data. Under broadcast mode (Figure 3(b)) data objects are routed directly to the query initiator. The two basic patterns for both modes are shown in Figure 4(a)/(b), where the smaller boxes represent HyperQueries and the Dispatch operator is responsible for routing objects to the HyperQuery given by the hyperlink. The decision, which processing mode is used, relies-with some restrictions-only to the initiator of a HyperQuery. Thus, the initiator determines, if the results should be sent directly to the client, or if the initiator is in charge of collecting the objects processed by the HyperQueries. During the execution trace of one query both processing modes can be mixed and nested to obtain more complex, multi-level scenarios. So, HyperQueries may be arbitrary complex and involve sub-contractors, too. As our system is written in Java and provides secure extensibility, user-defined operators can be integrated into the query plan and are loaded on demand. Thus, special wrappers for accessing legacy systems, applications, JDBC databases, XML data sources, or even human input can be used within the HyperQueries. All our operators are tuned for processing mass data, are pipelined, and the communication operators work push-based, i.e., objects are sent to the next sub-plan when the local processing is finished. A detailed description of HyperQuery processing including security, optimization issues, and implementation details can be found in [KW01a,KW01b].

(a) Hierarchical Processing	(b) Broadcast Processing
Figure 3:Execution Traces (The dashed (red) lines indicate the flow of control and intermediate results, the solid (black) lines indicate the flow of result objects)

(a) Hierarchical Mode	(b) Broadcast Mode
Figure 4:Patterns for HyperQuery Execution

The execution of the query in our QueryFlow system is demonstrated here.

People Involved into QueryFlow

• Prof. Alfons Kemper
• Christian Wiesner
• Peter Winklhofer
• Christina Popp

Results

The following publications are avaliable:

• HyperQueries: Dynamic Distributed Query Processing on the Internet
  Alfons Kemper and Christian Wiesner.
  Proceedings of the 27th International Conference on Very Large Data Bases (VLDB)
  pages 551-560, Rome, Italy, September 2001
  Presentation: [PowerPoint] · [PDF]
  
• HyperQueries: Dynamic Distributed Query Processing on the Internet
  Alfons Kemper and Christian Wiesner.
  Internal Technical Report
  University of Passau, October 2001.
• Building Dynamic Market Places Using HyperQueries
  Christian Wiesner, Peter Winklhofer, and Alfons Kemper.
  Demonstration presented on the VIII. Conference on Extending Database Technology (EDBT 2002), pages 749-752, Prague, March 2002.
• Master's Thesis of Peter Winklhofer

References

[1] The name of our system was derived from query processing and workflow systems because processing queries with HyperQueries bears some similarities with processing distributed workflows by routing documents to the appropriate tasks.

[2] We plan to support XQuery [CFR+01], too.