Development of Interoperable Multimedia Smart and Virtual Catalogs

Principal Investigator: M.T. Özsu (University of Alberta)

> OBJECTIVES

This project addresses the issues in developing interoperable smart and virtual catalogs for electronic commerce which incorporate full multimedia capabilities. The underlying assumption is that future catalogs that will be used in electronic commerce will have two characteristics: (a) they will not only contain text and (perhaps) images, but will contain full multimedia capabilities including audio and video, and (b) these catalogs will not be monolithic, consisting of storage in a single database management system (DBMS), but will be distributed involving a number of different types of data storage systems. The general approach incorporates multimedia data management capabilities and interoperability techniques for the development of distributed information systems. The project has two specific objectives:

Background and rationale

Most of the existing EC catalogs are text-based with limited multimedia capabilities, only incorporating still images. Catalogs should have full multimedia capabilities with the inclusion of advertisement videos and audio "talk-overs". This enables the incorporation of TV and radio commercials into the catalogs. The proposed research aims at developing the software systems to manage the multimedia catalogs using database management system (DBMS) technology. The use of DBMS technology provides many advantages most important of which may be the ability to query the data using a high level interface.

Existing catalog systems are generally proprietary, monolithic systems which store all data in one system. This is not a suitable architecture for the types of catalog systems that are envisioned in this project. The proposed catalog systems have to store and manage multiple types of media objects (text, images, audio, video, synchronized text), as well as meta information about these objects, and these media objects have different characteristics which require specialized treatments. Therefore, in this project we propose an open architecture that uses different specialized servers for different classes of media objects and combines them to achieve a multimedia catalog server. One component of the server will be the document DBMS that was developed in a Phase II CITR project [1,2]. This database will store the structured catalog documents and the associated text. Still image management will use the DISIMA system [3] that is being built with an NSERC Strategic Grant. Media objects with real-time constraints such as audio, video and synchronized text will be managed by a continuous media file system (CMFS). These components will be combined into a multi-layer DBMS which will provide users with a generic interface (e.g., SQL with multimedia extensions) and will use the underlying components to manage individual media objects and to respond to queries about the media objects that they manage.

Another characteristic of catalog servers for Internet-based electronic commerce is the massive distribution of the server. Most of the existing catalog servers are centralized systems, which would have difficulty in supporting sophisticated electronic commerce applications such as virtual malls. In this project we will investigate solutions where data are distributed more widely and access is provided over the Internet. This is desirable (and, perhaps, even unavoidable) since the servers will be heterogeneous (see below) and distributed widely. Therefore, this project will investigate the issues in developing multimedia repositories that are accessible over the Internet. This involves issues such as query engines and building http front ends. From a data management perspective, opening up to the Internet poses interesting problems such as the lack of a schema that controls user access and querying, the difficulties in executing/optimizing queries across http connections across a network with imprecise QoS characteristics, and database query interfaces co-existing with browsing tools.

Even though the development of smart catalog servers, as described above, advances the state-of-the-art in that area, it is unlikely that all catalogs in an EC environment will follow the same design or that all of the catalog information will be stored in one catalog server or database. The environment will include repositories other than DBMSs while still providing a DBMS interface and functionality. This raises issues of interoperability and the development of virtual catalogs that "dynamically retrieve information from multiple smart catalogs and present these product data in a unified manner with their own look and feel, not that of the smart catalogs" [4].

The interoperability architecture will be based on the mediator/wrapper paradigm [5] where information sources are "wrapped" so that their interfaces to the outside world are uniform and mediators are built to mediate the performance of various tasks across these repositories. Object-oriented technology will be used to realize the mediator/wrapper paradigm. Implementation will use a "communication bus" following both CORBA Object Request Broker (ORBs) [6] approach and COM/OLE [7] approach. There has been little work in using CORBA to build mediator/wrapper architectures, except on the incorporation of DBMSs in such a system [8]. The extension of this approach to non-DBMS repositories and the provision of more sophisticated mediators (such as data mining mediators, filtering mediators, etc.) will be studied. The use of CORBA in the Internet environment will also be investigated. The project will also study methodologies and tools for the development of interoperable (virtual) catalogs.

Significance to the shared goals of the major project

The goal of the major project is to investigate the enabling technologies required to support next generation electronic commerce applications. A key element of the enabling technologies is the catalogs that are used in the commerce activity. One aspect of this project is to consider the development of more sophisticated catalogs involving multimedia capability.

Many of the existing catalogs are either for a single vendor/supplier or involve storing all of the information in one data management system. Supporting electronic commerce on the Internet will require an open system where users can seamlessly access catalogs from a variety of sources. This requires interoperable systems which is the second focus of this project.

This project is most tightly connected to the Quality of Service and Distributed System Management (98-6-3) and User Interface and Intelligent Search Engines (98-6-4) projects. The relationship to 98-6-3 is in terms of building query processors/optimizers that take into account QoS constraints while the connection with 98-6-4 is in terms of the user interfaces that will be built to execute the query model that is developed in this project.

Research progress

This project is a continuation of two projects which were undertaken under the umbrella of the Broadband Services Major project during Phase II of CITR. One project involved the development of an object-oriented multimedia document DBMS in compliance with the SGML/HyTime standard, and the second project involved interoperability issues in electronic commerce. The following summarizes our progress in each of these projects.

(A) Development of Multimedia Document DBMS

The multimedia document DBMS we developed [1, 2] is fully compliant with SGML [9], together with a subset of HyTime [10] used primarily for the specification of hyperlinks and the synchronization requirements of continuous media components. The system, which is built on top of the object-oriented DBMS ObjectStore [11], consists of a kernel type system and a suite of document management tools. Text and images are stored in and managed directly by the DBMS; continuous media is stored on a continuous media file server and managed indirectly by the DBMS via metadata that it maintains.

One set of document management tools provides the support for analyzing and incorporating new Document Type Definitions (DTDs) into the system. This is accomplished by the DTD Parser that first validates a new DTD and then passes a parse tree to the Type Generator. The Type Generator uses the parse tree to automatically generate C++ code that extends the kernel type system with new types defining the new elements in the DTD. DTD elements can be specified in a manner that allows common element types to be consistently shared across multiple DTDs in the system. Compatibility of shared elements is automatically enforced. The new code is automatically compiled, built into libraries, and linked into applications that are in turn invoked to initialize selected databases with the new DTD and its associated schema.

The second tool set, used for document entry, is concurrently built by the Type Generator during DTD incorporation. This process similarly involves C++ code generation to extend a kernel meta-type system. Singleton instances of the generated meta-types are instantiated in the target databases to enable the creation of object instances that can represent element components of documents to be entered into a database. Thus, code for a DTD-specific Instance Generator is generated by the Type Generator, incorporated into a DTD-specific library, and linked to an enhanced SGML parser to create a document entry application. This document entry application is then able to process document instances by retrieving the appropriate DTD from the database. If the document is valid, it then passes a parse tree to the Instance Generator, which in turn retrieves the required meta-type instances from the database to create the new element objects from the parse tree data. Related tools provide for document removal or the removal of entire DTDs together with their associated documents. A simple document versioning system is currently being implemented.

(B) Interoperability Issues

Our research in this direction has been conducted within the context of the AURORA project [12]. The main goal of AURORA is to study issues and techniques for building middleware systems that provide integrated access to data that reside in a large number of heterogeneous and autonomous sources. Systems such as this must be scalable so that adding or removing a data source from the access scope is easy, and efficient both in terms of the algorithms to access data and in terms of the amount of redundant data that is accessed. AURORA addresses these issues with research along two main themes: (1) the development of a scalable mediation model; and (2) study of enabling techniques that allow efficient data access. In the past two years, we have completed the design of a two-tier, plug-and-play mediation model, and developed a range of enabling techniques to support the efficient realization of this mediation model.

The two-tier model divides the mediation process into two steps: homogenization followed by integration, each of which is performed by specialized mediators [13]. Homogenization removes idiosyncrasies of a data source in structure and semantics. After homogenization, a data source can be integrated by an integration mediator in a simple plug-and-play fashion. The scalability is achieved through independent and parallel homogenization and simple plug-and-play style integration. Indeed, the two-tier mediation model is a divide-and-conquer approach towards information integration and it is inherently scalable.

Even though the mediation model is orthogonal to data models, we have so far been working with relational DBMSs. In the future, we plan to work with object-oriented data models as well.

We have investigated two types of techniques that allow efficent data access: the mediation enabling algebras (MEAs) and mediator indices. MEAs are algebras specially designed to manipulate heterogeneous data at various stages of mediation. Mediator indices [14] are a means to materialize selected data at the mediator so as to facilitate intelligent query decomposition.

Research Plan

Our focus during the next year will be (i) to start development of multimedia smart catalog servers, and (ii) to develop an interoperability framework for relational DBMS repositories.

(A) Development of multimedia smart catalog servers

Development of a multimedia smart catalog system requires repositories that can handle multimedia servers. A multimedia server stores multimedia objects (text, images, audio, video) as well as meta information about these objects. We are interested in the development of DBMS-based distributed multimedia servers. The DBMS capabilities enable sophisticated searches in these catalogs as well as support for multi-user access.

Storing all of the multimedia data as native objects in a DBMS is one alternative. As indicated earlier, this is not an advisable approach to take. In any case, this is not currently feasible as the current generation of commercial (relational, object-oriented, or object-relational) DBMSs do not provide the facilities to efficiently store and manage all media objects in one system. One of the object-oriented commercial products that we have utilized, ObjectStore, has implemented Object Managers to provide some specialized support for text, images, audio, and video, but even these do not adequately handle content and spatial relationships in images or the QoS and synchronization requirements of continuous media (audio, video and synchronized text). Continuous media requires incorporation of real-time facilities into the DBMS, support of QoS specification and negotiation that are necessary for these media types, query processing and optimization in the presence of QoS constraints, and query primitives for these media types.

We, therefore, propose to take an alternative route where the smart catalog servers are built by coupling DBMSs that are specialized to handle various media types into one server. In the first year, we will concentrate on the architectural issues and in coupling a document DBMS with an image DBMS. The incorporation of a CMFS to manage audio and video will follow in subsequent phases of the project.

Our CITR supported research on an SGML/HyTime DBMS and our NSERC supported (by means of a strategic grant) research on an image DBMS (called DISIMA) will form the basis of our work during the first year. We intend to integrate the SGML/HyTime DBMS with DISIMA, both of which are built on top of ObjectStore, as complementary components by providing a common query interface [15, 16] for user access. Both of these systems are built on top of an object-oriented system (ObjectStore). This architecture exploits componentization for openness and scalability and enables users (and client modules) to interact directly with the DBMS using a high level interface and not worry about the additional peculiarities of accessing different DBMS components or individual file systems.

This approach gives rise to a number of research questions such as componentization of DBMS functions, development of multi-layered query processors/optimizers (one layer for media-specific queries and another layer at a higher, more generic level) the sensitivity of the DBMS to the QoS requirements of applications and users, collaboration of the DBMS with a synchronization module to properly display the results at the clients, and addition of real-time scheduling to DBMS functions. Among these, the architectural issues and those that relate to the coupling of document and image DBMSs will be our focus during the 1998-99 program year.

(B) Interoperability Framework

Our work in this area will continue within the framework of the AURORA project. We will focus on two issues in the coming year. The first is the development of a functional interoperability prototype.

The prototype will include two components, AURORA-RH, the relational homogenization mediator, and AURORA-RI, the relational integration mediator. For this first prototype, we will use the COM/DCOM and OLE-DB technologies as the basic distributed computing infrastructure in this prototype. AURORA-RH and AURORA-RI will be built as components that communicate and cooperate with each other via COM/DCOM.

AURORA-RH will connect, through ISG Navigator, to any data source that has an OLE-DB provider. The primary function of ISG Navigator is to extend the functionality of any data source (as long as it has an OLE-DB provider) by adding a relational query interface. If the source OLE-DB provider offers no relational query facilities, ISG Navigator compensates for it. ISG navigator also provides multi-source query processing through an OLE-DB conforming interface. In the context of the mediator/wrapper paradigm, ISG Navigator is a relational wrapper to all sources with an OLE-DB provider, including files, directories and spreadsheets. The use of ISG Navigator allows the prototype to interface with a large variety of data sources readily and easily.

There are two core components of AURORA-RH. One is an GUI-based tool supporting homogenization activities. This tool mandates a homogenization methodology. Another component is a query processor that rewrites, decomposes, optimizes a query, and submits the subqueries to underlying repositories for execution and assembles query result. This query process implements the Mediation Enabling Algebra for AURORA-RH, called MEA-RH. The technical basis of these core components are described in detail in [13].

AURORA-RI employs a plug-and-play integration mechanism to allow any homogenized source to be integrated through a simple registration process. There are many techniques in AURORA-RI still under research; therefore, the prototype will implement a plug-and-play integration mechanism [12] and the first version of a query processing algorithm. The purpose is to demonstrate the scalability of the two-tier mediation model by showing the ease with which data sources can be added and removed from the access scope of an application.

The second issue that we will study is what may be called conflict-tolerant query processing. When querying data originating from a large number of data sources, we encounter "instance level conflicts", problems caused by the fact that different data sources may "say" different things about the same application object. For instance, catalog (database) A may record that item #3426 weighs 25 kg, while catalog B indicates that it weighs 35 kg. Ability to process queries in the presence of these types of conflicts is important since these types of conflicts are likely to remain in the database even after the homogenization process which only resolves schema-level conflicts. [17], instance level conflicits are handled by aggregation functions. In the above example, we'd retrieve all information about Fred into the mediator and take the MIN, MAX, or AVG of age values from all sources. This approach poses much difficulty in query optimization [18] In many cases, much useless data must be retrieved simply for the purpose of detecting and handling instance level conflicts. This is the reason why many interoperability projects, such as Information Manifold [19] and DISCO [20] don't really consider such conflicts but rather assume that data is consistent among all sources.

Some work exists that develops special rules and approaches for optmizing queries when aggregation functions are used for handling instance level conflicts but the improvement is rather limited [18].

In AURORA, we will explore a new approach towards query processing in the presence of instance level conflicts. We make the following assumptions:

  1. Conflicts are exceptions, not the rule. Hence conflict handling should not incur a massive performance penalty.
  2. In many types of applications, retrieving data with absolute accuracy is less important then getting it as fast as possible. If so, a middleware system should allow the application to specify that it is willing to trade accuracy for speed.

Based on the above assumptions, we provide three levels of quality in processing a query Q:

  1. If it is at all possible that the answer is correct.

Query result with this quality has the following properties:

    1. Any tuple t in the result is a questionable; it is possible to argue that t is not an answer to Q by asserting that a certain instance level conflict is handled incorrectly in the process of query processing.
    2. If treatment of all instance level conflicts are equally likely to be correct, then the answer contains all possible answers to Q.

Consider the example above. Answer to a query such as „Retrieve items which weigh more than 30kg" at this accuracy level shuld contain item #3426. It is possible to argue that this item is not an answer to the query by arguing that when there is an instance level conflict on „weight", we should resolve the conflict by taking MIN, which, in the case of item #3426, would lead to the conclusion that it is indeed 25kg and should not be in the answer set. This demonstrates property (a) above. Now assume that we have no idea how the instance level conflicts on weight should be resolved and it is equally possible that item #3426 is either 25 kg or 35 kg. Then item #3426 should not be in the answer set to the above query. This demonstrates property (b).

  1. Random selection.
  2. In case of conflicts, randomly select one value to be the correct one and evaluate Q. The query result with this level of accuracy satisfies property 1(a) but not property 1(b).

  3. Conflict tolerant.

The query result with this level of accuracy contains no questionable answers to the query. That is, no matter how the instance level conflicts are resolved, the query result will be valid.

Each level of quality allows a different degree of query optimization. Our approach to conflict-tolerant query processing can be called 2-phase query processing (2PQP). The idea is to always try to evaluate a query optimistically, that is, assume that conflicts do nto exist, and use the second phase to further refine the answer in order to achieve the quality required by the user.

References

[1] M.T. Özsu, D. Szafron, G. El-Medani, and C. Vittal, "An Object-Oriented Multimedia Database System for News-on-Demand Application", ACM Multimedia Systems, 3: 182-203, 1995.

[2] M.T. Özsu P. Iglinski, D. Szafron, S. El-Medani, and M. Junghanns, "An Object-Oriented SGML/HyTime Compliant Multimedia Database Management System", In Proc. ACM International Conference on Multimedia Systems, Seattle, November 1997, pages 239-249.

[3] V. Oria, M.T. Özsu, L. Liu, X. Li, J.Z. Li, Y. Niu, and P. Iglinski, " Modeling Images for Content-Based Queries: The DISIMA Approach", In Proc. Second International Conference on Visual Information Systems, San Diego, CA, December 1997, pages 339-346.

[4] A. Keller, "Smart Catalogs and Virtual Catalogs", In Readings in Electronic Commerce, R. Kalakota and A.B. Whinston (eds.), Chapter 11, pages 259-274, 1997.

[5] G. Wiederhold, "Mediators in the Architecture of Future Information Systems", IEEE Computer, 25 (3): 38-49, March 1992.

[6] J. Siegel (ed.), CORBA Fundamentals and Programming, John Wiley, New York, NY, 1996.

[7] K. Brockschmidt, Inside OLE, 2nd edition, Microsoft Press, Redmond, WA, 1995.

[8] A. Dogac, C. Dengi, and M.T. Özsu, "Building Interoperable Databases on Distributed Object Management Platforms", Communication of ACM, 1998, in press.

[9] International Standards Organization, Information Processing - Text and Office Information Systems - Standard Generalized Markup Language, ISO 8870, 1986.

[10] International Standards Organization, Hypermedia/Time-Based Structuring Language: HyTime, ISO 10744, 1992.

[11] C. Lamb, G. Landis, J. Orenstein, and D. Weinreb, „The ObjectStore Database System", Communications of ACM, 34(10): 19-20, 1991.

[12] L. L. Yan, „Towards Efficient and Scalable Mediation: The AURORA Approach", In Proc. CASCON'97 Conference, Toronto, Ontario, November 1997.

[13] L. L. Yan, M.T. Özsu and L. Liu, „Accessing Heterogeneous Data Through Homogenization and Integration Mediators", In Proc. Second IFCIS Conference on Cooperative Information Systems (CoopIS-97), Charleston, South Carolina, June 1997, pages 130-139.

[14] L. L. Yan, M.T. Özsu and L. Liu, „Mediator Join Indices", In Proc. Seventh International Workshop on Research Issues in Data Engineering: High-Performance Database Management for Large Scale Applications (RIDE'97), Birmingham, England, April 1997, pages 51-59.

[15] J. Z. Li, M.T. Özsu, D. Szafron, V. Oria. „MOQL: A Multimedia Object Query Language", In Proc. Third International Workshop on Multimedia Information Systems, Como, Italy, September 1997, pages 19-28.

[16] J.Z. Li, Modeling and Querying Multimedia Data, Ph.D. Thesis, University of Alberta, Department of Computing Science, 1998 (upcoming).

[17] U. Dayal, „Query Processing in a multidatabase system", In Query Processing in Database Systems, W. Kim and D. Reiner and D. Batory (eds.), 1985, pages 81-108.

[18] A. Chen, „Outerjoin Optimization in Multidatabase Systems", In Proc. Second International Symposium on Distributed and Parallel Database Systems, 1990, pages 211-218.

[19] A. Levy, A. Rajaraman, and J. Ordille, „Querying Heterogeneous Information Sources Using Source Descriptions", In Proc. 22nd International Conference on Very Large Data Bases, Mumbai, India, 1996.

[20] A. Tomasic, L. Raschid, and P. Valduriez, „Scaling Heterogeneous Database and the Design of DISCO", In Proc. International Conference on Distributed Computer Systems, 1996.

Milestones

December 98 • Completion of prototype implementation of AURORA-RH and AURORA-RI

March 99 • Completion of integration of multimedia document DBMS with DISIMA image DBMS

• Completion of work on fault tolerant querying

Relationship to Support Currently Held or Applied for

The image DBMS is being developed through an NSERC Strategic Grant awarded to the M.T. Özsu, L. Liu and X. Li. This funding will continue until 1999.