icde_1999_elementary.txt

利用lwp：：get写的

<proceedings><paper><title>Message from the Program Co-Chairs</title><year>1999</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract></abstract></paper><paper><title>Program Committee Chairs</title><year>1999</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract></abstract></paper><paper><title>External Reviewers</title><year>1999</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract></abstract></paper><paper><title>Que Sera, Sera: The Coincidental Confluence of Economics, Business, and Collaborative Computing</title><author><AuthorName>Michael L. Brodie</AuthorName><institute><InstituteName>GTE Laboratories Incorporate</InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>The World Wide Web (WWW) changes everything, but how? Amazon.com is the current exemplar of e-business but does not begin to suggest what is possible. The Web frequently raises technology-based ideas such as WWW sites, Intranets, extra-nets, global access to information systems, and WWW-based interoperation. However, technical ideas serve to realize more significant changes such as the way business is conducted (e.g., e-business, business-to-business interactions, globalization, elimination of geographic boundaries, consolidation, dis-intermediation, stores without products, and worldwide price competition). More radical and more fundamental changes are those related to new economic models that underlie, predict, and enable new business models and which define technology requirements. The potential offered by the WWW is so great and so radical that it will take at least a decade to understand and possibly another decade to realize, since it involves fundamental change not only in computing models and practice but also in business and most significantly in economics.This is a time of radical change in what appears to be the parallel worlds of technology, business, and economics. They are not parallel. The intimate relationship of these domains has resulted in collateral homeostasis due in part to their interdependence. Recent radical change in each domain is now opening the door to collateral change. This presentation focuses on the confluence of these changes. Technology change includes not only the WWW but also other major factors. Gizmos, such as the Palm III, will become the dominant computing platform in sheer numbers. The trend toward packaged applications, e.g., SAP R/3, will extend far beyond the current strength in Enterprise Resource Planning to become the dominant method for software development and delivery. Business change involves not only organizations racing to capitalize on e-business opportunities, but also constant re-organization as seen in consolidations, mergers, and acquisitions that pose serious challenges to conventional technology (e.g., integration of generations old technology). Economic change is less obvious and more radical. It involves the move from cost-based accounting to economic-chain accounting.Current technology is designed to support cost-based accounting, which involves the management of data/information/knowledge within the boundaries of an organization. Current technology is inadequate to support economic-chain accounting, which involves the acquisition and management of data/information/knowledge beyond the boundaries of an organization.This presentation is an exploration of the next generation computing based on the confluence of radical and coincidental changes in economics, business, and technology. Whereas technology is a key enabler of change, it is and is the servant, not the master. Without a depth of understanding of this enabling role and the content in which technology serves, technology can be misguided and its developers can lose perspective. This presentation outlines a proposal made to the US President' s Office of Science and Technology for technology research for the next decade, which calls for new computational models, operating systems, data models, and infrastructure, amongst others, to support the next generation of computing, collaborative.</abstract></paper><paper><title>A Database Approach for Modeling and Querying Video Data</title><author><AuthorName>Cyril Decleir</AuthorName><institute><InstituteName>LISI-INS</InstituteName><country></country></institute></author><author><AuthorName>Jacques Kouloumdjian</AuthorName><institute><InstituteName>LISI-INS</InstituteName><country></country></institute></author><author><AuthorName>Mohand-Said Hacid</AuthorName><institute><InstituteName>RWTH Aache</InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Indexing video data is essential for providing content based access. In this paper, we consider how database technology can offer an integrated framework for modeling and querying video data. As many concerns in video (e.g., modeling and querying) are also found in databases, databases provide an interesting angle to attack many of the problems. From a video applications perspective, database systems provide a nice basis for future video systems. More generally, database research will provide solutions to many video issues even if these are partial or fragmented. From a database perspective, video applications provide beautiful challenges. Next generation database systems will need to provide support for multimedia data (e.g., image, video, audio). These data types require new techniques for their management (i.e., storing, modeling, querying, etc.). Hence new solutions are significant.This paper develops a data model and a rule-based query language for video content based indexing and retrieval. The data model is designed around the object and constraint paradigms. A video sequence is split into a set of fragments. Each fragment can be analyzed to extract the information (i.e., symbolic descriptions) of interest that can be put into a database. This database can then be searched to find information of interest. Two types of information are considered: (1) the entities (i.e., objects) of interest in the domain of a video sequence, (2) video frames which contain these entities. To represent these information, our data model allows facts as well as objects and constraints. We present a declarative, rule-based, constraint query language that can be used to infer relationships about information represented in the model. The language has a clear declarative and operational semantics.</abstract></paper><paper><title>Efficient Theme and Non-Trivial Repeating Pattern Discovering in Music Databases</title><author><AuthorName>Chih-Chin Liu</AuthorName><institute><InstituteName>National Tsing Hua Universit</InstituteName><country></country></institute></author><author><AuthorName>Jia-Lien Hsu</AuthorName><institute><InstituteName>National Tsing Hua Universit</InstituteName><country></country></institute></author><author><AuthorName>Arbee L. P. Chen</AuthorName><institute><InstituteName>National Tsing Hua Universit</InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>In this paper, we propose an approach for fast discovering all non-trivial repeating patterns in music objects. A repeating pattern is a sequence of notes which appears more than once in a music object. The longest repeating patterns in music objects are typically their themes. The themes and other non-trivial repeating patterns are important music features which can be used for both content-based retrieval of music data and music data analysis. We present a data structure called RT-tree and its associated algorithms for fast extracting all non-trivial repeating patterns in a music object. Experiments are performed to compare with the related approaches. The results are further analyzed to show the efficiency and the effectiveness of our approach.</abstract></paper><paper><title>Query Processing Issues in Image(Multimedia) Databases</title><author><AuthorName>Surya Nepal</AuthorName><institute><InstituteName>RMIT Universit</InstituteName><country></country></institute></author><author><AuthorName>M.V. Ramakrishna</AuthorName><institute><InstituteName>RMIT Universit</InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Multimedia databases have attracted academic and industrial interest, and systems such as QBIC (Content Based Image Retrieval system from IBM) have been released. Such systems are essential to effectively and efficiently use the existing large collections of image data in the modern computing environment. The aim of such systems is to enable retrieval of images based on their contents. This problem has brought together the (decades old) database and image processing communities.As part of our research in this area, we are building a prototype CBIR system called CHITRA. This uses a four level data model, and we have defined a Fuzzy Object Query Language(FOQL) for this system. This system enables retrieval based on high level concepts, such as &amp;quot;retrieve images of MOUNTAINS&amp;quot;, &amp;quot;retrieve images of MOUNTAINS and SUNSET&amp;quot;.A problem faced in this system is processing of complex queries such as &amp;quot;retrieve all images that have similar color histogram and similar texture to the given example image&amp;quot;. Such problems have attracted research attention in recent times, notably by Fagin, Chaudhury and Gravano. Fagin has given an algorithm for processing such queries and provided a probabilistic upper bound for the complexity of the algorithm (which has been implemented in IBM's Garlic project). In this paper we provide theoretical (probabilistic) analysis of the expected cost of this algorithm. We propose a new multi-step query processing algorithm and prove that it performs better than Fagin's algorithm in all cases. Our algorithm requires fewer database accesses. We have evaluated both algorithms against an image database of 1000 images on our CHITRA system. We have used color histogram and Gabor texture features. Our analysis presented and the reported experimental results validate our algorithm (which has significant performance improvement).</abstract></paper><paper><title>On Getting Some Answers Quickly, and Perhaps More Later</title><author><AuthorName>Kian-Lee Tan</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Cheng Hian Goh</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Beng Chin Ooi</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Traditionally, the answer to a database query is construed to be the set of all tuples that meet the criteria stated. Strict adherence to this notion in query evaluation is however increasingly unsatisfactory because decision makers are more prone to adopting an exploratory strategy for information search which we call ``getting some answers quickly, and perhaps more later.'' In this paper, we propose a progressive query processing strategy that exploits this behavior to conserve system resources and to minimize query response time. This is accomplished by the heuristic decomposition of user queries into subqueries that can be evaluated on demand. We also describe the architecture of a prototype system that provides a non-intrusive implementation of our approach. Finally, we present experimental results that demonstrate the benefits of the progressive query processing strategy.</abstract></paper><paper><title>Systematic Multiresolution and its Application to the World Wide Web</title><author><AuthorName>Swarup Acharya</AuthorName><institute><InstituteName>Bell Laboratories, Lucent Technologie</InstituteName><country></country></institute></author><author><AuthorName>Henry F. Korth</AuthorName><institute><InstituteName>Bell Laboratories, Lucent Technologie</InstituteName><country></country></institute></author><author><AuthorName>Viswanath Poosala</AuthorName><institute><InstituteName>Bell Laboratories, Lucent Technologie</InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Many emerging environments are increasingly facing the problem where the requirements of applications easily outstrip the system resources. This is particularly acute in the World Wide Web (WWW) and many data-intensive applications like OLAP and multimedia databases. In this paper, we address this problem in the Web context via ``systematic multiresolution'', i.e., a framework for providing responses at different qualities (resolutions) and costs.We validate our conceptual contributions by implementing NetBlitz, a multiresolution-based proxy server on the WWW. NetBlitz addresses two key problems facing the Web: high latencies and heterogeneity of client resources and requirements. It solves these problems by dynamically generating the ``required version'' of a web object based on client preferences and capabilities. We also propose novel multiresolution-aware caching techniques that further improve performance. Finally, we experimentally demonstrate the utility of multiresolution and the caching enhancements proposed.</abstract></paper><paper><title>Capability-Sensitive Query Processing on Internet Sources</title><author><AuthorName>Hector Garcia-Molina</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Wilburt Labio</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Ramana Yerneni</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>On the Internet, the limited query-processing capabilities of sources make answering even the simplest queries challenging. In this paper, we present a scheme called GenCompact for generating capability-sensitive plans for queries on Internet sources. The query plans generated by GenCompact have the following advantages over those generated by existing query processing systems: (1) the sources are guaranteed to support the query plans; (2) the plans take advantage of the source capabilities; and (3) the plans are more efficient since a larger space of plans is examined.</abstract></paper><paper><title>A Messaging-Based Architecture for Enterprise Application Integration</title><author><AuthorName>Tommy Joseph</AuthorName><institute><InstituteName>Tibco In</InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>This talk discusses a messaging-based architecture for Enterprise Application Integration (EAI). The first generation of Enterprise Application Integration focused on the problem of making data held by various enterprise applications available from a common location and in a common format. The current generation of EAI goes beyond this by also propagating and controlling the flow of business events from application to application as they occur. A flexible, robust and scaleable messaging infrastructure is essential to this form of &amp;quot;active integration.&amp;quot;</abstract></paper><paper><title>Database as an Application Integration Platform</title><author><AuthorName>Ashok R. Saxena</AuthorName><institute><InstituteName>Oracle Corporatio</InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>This paper describes critical features that should be provided by any platform for application integration. These features include message queuing, message filtering and data transformation. The integration of these features with a database makes for a powerful platform for application integration that is scalable, reliable, available and manageable.</abstract></paper><paper><title>Business Objects and Application Integration</title><author><AuthorName>Saydean Zeldin</AuthorName><institute><InstituteName>TSI Softwar</InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Application integration addresses the need for diverse applications to be able to communicate with each other across application boundaries and across platform boundaries. Business objects extend the type system of relational databases to deal with the needs of application integration.The requirements of business application integration include event-based information workflow to manage the exchange of data, well-formed business objects to reduce the number of application interfaces and to keep the semantic integrity of the information exchange intact, seamless transformation to integrate the validation and construction of interfacing business objects, and heterogeneous transport adapters to move business objects from one place to another.The objective of this paper is to examine the requirements for business objects and their role in application integration and to show examples of how the Mercator product addresses these requirements.</abstract></paper><paper><title>Cooperative Caching in Append-Only Databases with Hot Spots</title><author><AuthorName>Aman Sinha</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Craig Chase</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Munir Cochinwala</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>We measure the performance of several cooperative caching policies for a database with hot spots. The workload consists of queries and append-only update transactions, and is modeled after a financial database of stock (historical) trading information.We show that cooperative caching is effective for this application. We show that selecting the correct set of peer servers when servicing a cache miss is crucial to achieving high performance, and we demonstrate a greedy algorithm that performs close to optimal for this workload. We also evaluate several cache replacement policies and show that a 2$^{nd}$-chance algorithm performs best. In a 2$^{nd}$-chance algorithm, replaced pages are transferred to a peer server rather than being discarded. When a page is selected for replacement a 2$^{nd}$ time, the page is discarded.Our results can be applied in the design of ``proxy'' servers for databases or web servers where a layer of proxy servers are used to scale the system performance.</abstract></paper><paper><title>Improving RAID Performance Using a Multibuffer Technique</title><author><AuthorName>Kien A. Hua</AuthorName><institute><InstituteName>University of Central Florid</InstituteName><country></country></institute></author><author><AuthorName>Khanh Vu</AuthorName><institute><InstituteName>University of Central Florid</InstituteName><country></country></institute></author><author><AuthorName>Ta-Hsiung Hu</AuthorName><institute><InstituteName>Syscom Computer Engineering Co</InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>RAID (redundant array of inexpensive disks) offers high performance for read accesses and large writes to many consecutive blocks. On small writes, however, it entails large penalties. Two approaches have been proposed to address this problem:1. The first approach records the update information on a separate log disk, and only brings the affected parity blocks to the consistent state when the system is idle. This strategy increases the chance of disk failure due to the additional log disks. Furthermore, heavy system loads for an extended period of time can overflow the log disks and cause sudden disastrous performance.2. The second approach avoids the above problems by grouping the updated blocks into new stripes and writing them as large writes. Unfortunately, this strategy improves write performance on the expense of read operations. After many updates, a set of logically consecutive data blocks can migrate to only a few disks making fetching them more expensive.In this paper, we improve on the second approach by eliminating its negative side effects. Our simulation results indicate that the existing scheme sometime performs worse than the standard RAID5 design. Our method is consistently better than either of these techniques.</abstract></paper><paper><title>Managing Distributed Memory to Meet Multiclass Workload Response Time Goals</title><author><AuthorName>Markus Sinnwell</AuthorName><institute><InstituteName>SAP AG, Walldor</InstituteName><country></country></institute></author><author><AuthorName>Arnd Christian Konig</AuthorName><institute><InstituteName>University of the Saarlan</InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>In this paper we present an online method for managing a goal oriented buffer partitioning in the distributed memory of a network of workstations. Our algorithm implements a feedback mechanism which dynamically changes the sizes of dedicated buffer areas and thereby the buffer hit rate for the different classes in such a way that user specified response time goals will be satisfied. The aggregated size of the buffer memory across all network nodes remains constant and only the partitioning is changed. The algorithm is based on efficiently approximating the trajectory of the per-class response time curves as a function of the available buffer. Changes in the workload that would lead to the violation of response time goals are counteracted by accordingly adjusting the buffer allocation. For local replacement decisions, we integrate a cost based buffer replacement algorithm to fit into our goal oriented approach. We have implemented out algorithm in a detailled simulation prototype and we present some first results with this prototype.</abstract></paper><paper><title>Scalable Web Server Design for Distributed Data Management</title><author><AuthorName>Scott M. Baker</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Bongki Moon</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Traditional techniques for a distributed web server design rely on manipulation of central resources, such as routers or DNS services, to distribute requests designated for a single IP address to multiple web servers. The goal of the Distributed Scalable Web Server development is to explore application-level techniques for distributing web content. We achieve this by dynamically manipulating the hyperlinks stored within the web documents themselves. The distributed scalable web server effectively eliminates the bottleneck of centralized resources, while balancing the load among distributed web servers. The web servers may be located in different networks, or even different continents and still balance load effectively. The distributed scalable web server design is fully compatible with existing HTTP protocol semantics and existing web client software products.</abstract></paper><paper><title>A Transparent Replication of HTTP Service</title><author><AuthorName>Radek Vingralek</AuthorName><institute><InstituteName>Bell Laboratories, Lucent Technologie</InstituteName><country></country></institute></author><author><AuthorName>Yuri Breitbart</AuthorName><institute><InstituteName>Bell Laboratories, Lucent Technologie</InstituteName><country></country></institute></author><author><AuthorName>Mehmet Sayal</AuthorName><institute><InstituteName>Northwestern Universit</InstituteName><country></country></institute></author><author><AuthorName>Peter Scheuermann</AuthorName><institute><InstituteName>Northwestern Universit</InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>We describe the architecture of Web++, a prototype for user-transparent replication of Web service. Web++ is built on top of the standard HTTP protocol and does not require any changes to existing Web browsers or the instalation of any software on the client side. We report on live Internet experiments that show that Web++ improves the client response time on the average by 36%, when compared to current Web performance.</abstract></paper><paper><title>Atomic Commitment in Database Systems over Active Networks</title><author><AuthorName>Zhili Zhang</AuthorName><institute><InstituteName>North Dakota State Universit</InstituteName><country></country></institute></author><author><AuthorName>William Perrizo</AuthorName><institute><InstituteName>North Dakota State Universit</InstituteName><country></country></institute></author><author><AuthorName>Victor T.-S. Shi</AuthorName><institute><InstituteName>North Dakota State Universit</InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>This paper proposes a novel approach to atomic commitment of transactions in distributed database systems. In our approach, active nodes participate in the process of atomic commitment of distributed transactions by maintaining passive &amp;quot;blackboards&amp;quot; which record voting status of participant subtransactions.</abstract></paper><paper><title>A Hypertext Database for Advanced Sharing of Distributed Web Pages</title><author><AuthorName>Takanori Yamakita</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Takashi Fuji</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>There are many learning systems using their web pages. These systems provide not only contents of the web pages but also the embedded links on them for learners. In these systems, since the learners can use all the hyperlinks embedded on the web page, they can visit unnecessary/invalid web pages.In order to use web pages as instructional materials, authors of instructional materials need to be able to select appropriate web pages. Moreover, it is necessary to provide only the hyperlinks among these selected pages.A hyperlink view means the network of these selected web pages and hyperlinks. We regard this style of reusing web pages based on the hyperlink view as the advanced sharing of them. For the purpose of constructing a hypertext database that supports above advanced sharing of web pages, we developed an object- oriented framework of hypertext database. This framework is an extension of the Dexter model by adding link-context layer, context selecting interface, and more detailed presentation specifications to it. Material Authors can create their own hyperlink views and store each view in the hypertext database as a new link context individually. As the context selecting interface accomplishes composition of some link contexts, they can extend their link contexts. In this framework, a unit for sharing of web pages is a link context.It is necessary to hide hotspots about invalid hyperlinks on a screen dynamically. We add hiding mechanism of the invalid hotspots to the Dexter model. It is possible to treat hyperlink views through an ordinary web browsers. We developed a prototypical instructional material database, that is an example of the applications of our framework. Through this experience, we confirmed that the advanced sharing of web pages and their hyperlinks reduced the cost of material developments.</abstract></paper><paper><title>Similarity Searching in Text Databases with Multiple Field Types</title><author><AuthorName>Kostas Tzeras</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Euripides G.M. Petrakis</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract></abstract></paper><paper><title>Integrating Heterogeneous OO Schemas</title><author><AuthorName>Yangjun Chen</AuthorName><institute><InstituteName>IPSI Institut</InstituteName><country></country></institute></author><author><AuthorName>Wolfgang Benn</AuthorName><institute><InstituteName>Technical University Chemnit</InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>In this paper, we would like to introduce a new assertion, the so-called derivationassertion, to accommodate more heterogeneities, which can not be treated by the existing methodologies. As an example, consider two local object-oriented schemas: S 1 and S 2 and assume that S 1 contains two classes: parent and brother, and S 2 contains a class: uncle. A derivation assertion of the form: S 1 (parent, brother) (r) S 2 (uncle) can specify their corresponding semantic relationship clearly, which can not be established otherwise. We claim that this kind of assertions is necessary for the following reason. Imagine a query concerning uncle, submitted to the integrated schema from S 1 and S 2 . If the above assertion is not specified, the query evaluation will not take schema S 1 into account and thus the answers to the query can not be correctly computed in the sense of cooperations. Some more complicated examples will be given in a full paper to show that derivation assertions can always be used to handle intricate semantic relationships.</abstract></paper><paper><title>Confirmation: A Solution for Non-Compensatability in Workflow Applications</title><author><AuthorName>Chengfei Liu</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Maria Orlowska</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Xuemin Lin</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Xiaofang Zhou</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>The notion of a compensation is widely used in advanced transaction models as means of recovery from a failure. Similar concepts are adopted for providing ``transaction-like'' behaviour for long business processes supported by workflows technology. Generally, designing a compensating task in the context of a workflow process is a non-trivial job. In fact, not every task is compensatable since the forcibility of ``reverse'' operations of the task is not always guaranteed by the application semantics. In addition, the isolation requirement on data resources may make a task difficult to compensate. In this paper, we introduce a new concept called confirmation. By using confirmation, we can modify some originally non-compensatable tasks so that they become compensatable. Upon success of a workflow instance, the confirmation tasks of all executed tasks, if defined, are required for execution. An object-oriented framework which incorporates the confirmation concept is presented in this paper as well as its implementation issues.</abstract></paper><paper><title>Policies in a Resource Manager of Work ow Systems: Modeling, Enforcement and Management</title><author><AuthorName>Yan-Nong Huang</AuthorName><institute><InstituteName>Hewlett-Packard Laboratorie</InstituteName><country></country></institute></author><author><AuthorName>Ming-Chien Shan</AuthorName><institute><InstituteName>Hewlett-Packard Laboratorie</InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>We are interested in Work ow Management Systems (WFMS) [3, 4], and particularly, in Resource Management (RM) [1, 2] of WFMS. A WFMS consists of coordinating executions of multiple activities, instructing who (resource) do what (activity) and when. The &amp;quot;when&amp;quot; part is taken care of by the workflow engine which orders the executions of activities based on a process definition. The &amp;quot;who&amp;quot; part is handled by the resource manager that aims at finding suitable resources at the run-time for the accomplishment of an activity as the engine steps through the process definition. Resources of different kinds (human and material, for example) constitute the information system of our interest, their management consists of resource modeling and effective allocation upon users' requests. Since resource allocation needs to follow certain general guidelines (authority, security, for example) - no matter who or what application issues requests: so those general guidelines are better considered as part of the resources' semantics. That is the reason why we are interested in resource policy management in RM. Resource policies are general guidelines every individual resource allocation must observe. They differ from process specific policies which are only applied to a particular process. The policy manager is a module within the resource manager, responsible for efficiently managing a (potentially large) set of policies and enforcing them in resource allocation. We propose to enforce policies by query rewriting. A resource query is sent to the policy manager where relevant policies are first retrieved, then either additional selection criteria are appended to the initial query (in the case of requirement policies) or a new query is returned (in the case of substitution policies). Therefore, the policy manager can be seen as both a regulator and a facilitator where a resource query is either &amp;quot;polished&amp;quot; or given alternatives in a controlled way before submitted for actual resource retrieval. By doing so, returned resources can always be guaranteed to fully comply with the resource usage guidelines. We studied several issues related to resource policies in Work ow Systems. A policy language was proposed allowing users to specify policies of different types. To enforce the policy, a resource query is first rewritten based on relevant policies, before submitted to the resource manager for actual retrieval. The originality of the present work is on the resource policy model, the policy enforcement mechanism and policy management techniques including relational representation of, and efficient access to, a large policy set. It seems that the interval-based representation proposed in the paper provides a general framework for effective storage and efficient retrieval of large Boolean expression sets. A prototype was implemented in Java on NT 4.0, with experimental policies managed in an Oracle database. An alternative implementation would load policies into the main memory (periodically or at start-up time), an in-memory query optimizer ought to be devised in this case. Comparisons of pros/cons of these two implementations are worth further investigating.References [1] W. Du, G. Eddy and M.-C. Shan, &amp;quot;Distributed Resource Management in Work ow Environments&amp;quot;, Proc. of Database Systems for Advanced Applications (DAS-FAA), Melbourne, Australia, April, 1997. [2] Y. -N. Huang and M.-C. Shan, &amp;quot;Policies in a Resource Manager of Work ow Systems: Modeling, Enforcement and Management&amp;quot;, HP Tech. Report, HPL-98-156, Palo Alto, CA. [3] M. -C. Shan, J. Davis and W. Du, &amp;quot;HP Workflow Research: Past, Present and Future&amp;quot;, Proc. of NATO ASI on Workflow Systems and Interoperability, Springer-Verlag, Turkey, August 1997. [4] WFMC, &amp;quot;The Work ow Reference Model&amp;quot;, http://www.aiim.org/wfmc/DOCS/refmodel/rmv1-16.html.</abstract></paper><paper><title>TP-Monitor-Based Workflow Management System Architecture</title><author><AuthorName>Christoph Bussler</AuthorName><institute><InstituteName>The Boeing Compan</InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Workflow Management System (WFMS) implementations traditionally follow a client/server architecture with monolithic servers (workflow engines). This poster presents a WFMS architecture based on a TP-Monitor environment which partitions the workflow engine into several resource managers (RMs) individually managed by a TP-Monitor environment. The RMs together form the workflow engine serving user requests.</abstract></paper><paper><title>Efficient Mining of Partial Periodic Patterns in Time Series Database</title><author><AuthorName>Jiawei Han</AuthorName><institute><InstituteName>Simon Fraser Universit</InstituteName><country></country></institute></author><author><AuthorName>Yiwen Yin</AuthorName><institute><InstituteName>Simon Fraser Universit</InstituteName><country></country></institute></author><author><AuthorName>Guozhu Dong</AuthorName><institute><InstituteName>Wright State Universit</InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Partial periodicity search, i.e., search for partial periodic patterns in time-series databases, is an interesting data mining problem. Previous studies on periodicity search mainly consider finding full periodic patterns, where every point in time contributes (precisely or approximately) to the periodicity. However, partial periodicity is very common in practice since it is more likely that only some of the time episodes may exhibit periodic patterns.We present several algorithms for efficient mining of partial periodic patterns, by exploring some interesting properties related to partial periodicity, such as the Apriori property and the max-subpattern hit set property, and by shared mining of multiple periods. The max-subpattern hit set property is a vital new property which allows us to derive the counts of all frequent patterns from a relatively small subset of patterns existing in the time series. We show that mining partial periodicity needs only two scans over the time series database, even for mining multiple periods. The performance study shows our proposed methods are very efficient in mining long periodic patterns.</abstract></paper><paper><title>STING+: An Approach to Active Spatial Data Mining</title><author><AuthorName>Wei Wang</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Jiong Yang</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Richard Muntz</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Spatial data mining presents new challenges due to the large size of spatial data, the complexity of spatial data types, and the special nature of spatial access methods. Most research in this area has focused on efficient query processing of static data. This paper introduces an active spatial data mining approach which extends the current spatial data mining algorithms to efficiently support user-defined triggers on dynamically evolving spatial data. To exploit the locality of the effect of an update and the nature of spatial data, we employ a hierarchical structure with associated statistical information at the various levels of the hierarchy and decompose the user-defined trigger into a set of sub-triggers associated with cells in the hierarchy. Updates are suspended in the hierarchy until their cumulative effect might cause the trigger to fire. It is shown that this approach achieves three orders of magnitude improvement over the naive approach that re-evaluates the condition over the database for each update, while both approaches produce the same result without any delay. Moreover, this scheme can support incremental query processing as well.</abstract></paper><paper><title>Efficient Time Series Matching by Wavelets</title><author><AuthorName>Kin-Pong Chan</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Wai-Chee Fu</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Time series stored as feature vectors can be indexed by multi-dimensional index trees like R-Tree for fast retrieval. Due to the dimensionality curse problem, transformations are applied to time series to reduce the number of dimensions of the feature vectors. Different transformations like Discrete Fourier Transform (DFT), Discrete Wavelet Transform (DWT), Karhunen-Loeve (K-L) transform or Singular Value Decomposition (SVD) can be applied. While the use of DFT and K-L transform or SVD have been studied in the literature, to our knowledge, there is no in-depth study on the application of DWT. In this paper, we propose to use Haar Wavelet Transform for time series indexing. The major contributions are: (1) we show that Euclidean distance is preserved in the Haar transformed domain and no false dismissal will occur in range query, (2) we show that Haar transform can outperform DFT through experiments, (3) a new similarity model is suggested to accommodate vertical shift of time series, and (4) a two-phase method is proposed for efficient n-nearest neighbor query in time series databases.</abstract></paper><paper><title>Enhancing Semistructured Data Mediators with Document Type Definitions</title><author><AuthorName>Yannis Papakonstantinou</AuthorName><institute><InstituteName>University of California at San Dieg</InstituteName><country></country></institute></author><author><AuthorName>Pavel Velikhov</AuthorName><institute><InstituteName>University of California at San Dieg</InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Mediation is an important application of XML. The MIX mediator uses Document Type Definitions (DTDs) to assist the user in query formulation and query processors in running queries more efficiently.We provide an algorithm for inferring the view DTD from the view definition and the source DTDs. We develop a metric of the quality of the inference algorithm's view DTD by formalizing the notions of soundness and tightness. Intuitively, tightness is similar to precision, i.e., it deteriorates when &amp;quot;many&amp;quot; objects described by the view DTD can never appear as content of the view.In addition we show that DTDs have some inherent deficiencies that prevent the development of tight DTDs. We propose &amp;quot;DTDs with specialization&amp;quot; as a way to resolve this problem.</abstract></paper><paper><title>Estimating the Usefulness of Search Engines</title><author><AuthorName>Weiyi Meng</AuthorName><institute><InstituteName>State University of New York at Binghamto</InstituteName><country></country></institute></author><author><AuthorName>King-Lup Liu</AuthorName><institute><InstituteName>University of Illinois at Chicag</InstituteName><country></country></institute></author><author><AuthorName>Clement Yu</AuthorName><institute><InstituteName>University of Illinois at Chicag</InstituteName><country></country></institute></author><author><AuthorName>Wensheng Wu</AuthorName><institute><InstituteName>University of Illinois at Chicag</InstituteName><country></country></institute></author><author><AuthorName>Naphtali Rishe</AuthorName><institute><InstituteName>Florida International Universit</InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>In this paper, we present a statistical method to estimate the usefulness of a search engine for any given query. The estimates can be used by a metasearch engine to choose local search engines to invoke. For a given query, the usefulness of a search engine in this paper is defined to be a combination of the number of documents in the search engine that are sufficiently similar to the query and the average similarity of these documents. Experimental results indicate that the proposed estimation method is quite accurate.</abstract></paper><paper><title>Query Routing in Large-Scale Digital Library Systems</title><author><AuthorName>Ling Liu</AuthorName><institute><InstituteName>Oregon Graduate Institute of Science and Technolog</InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Modern digital libraries require user-friendly and yet responsive access to the rapidly growing, heterogeneous, and distributed collection of information sources. The increasing volume and diversity of digital information available online have led to a growing problem that conventional data management systems do not have, namely finding which information sources out of many candidate choices are the most relevant to answer a given user query. We refer to this problem as the query routing problem. In this paper we introduce the notation and issues of query routing, and present a practical solution for designing a scalable query routing system based on multi-level progressive pruning strategies. The key idea is to create and maintain user query profiles and source capability profiles independently, and to provide algorithms that can dynamically discover relevant information sources for a given query through the smart use of user query profiles and source capability profiles, including the mechanisms for interleaving query routing with query parallelization and query execution process to continue the pruning at run-time. Comparing with the keyword-based indexing techniques adopted in most of the search engines and software, our approach offers fine-granularity of interest matching, thus it is more powerful and effective for handling queries with complex conditions.</abstract></paper><paper><title>Database Extensions for Complex Forms of Data</title><author><AuthorName>Samuel DeFazio</AuthorName><institute><InstituteName>Oracle Corporatio</InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>To adequately support text, image, spatial, message and other complex forms of data, modern database management systems must provide an extensive set of data integration features. The emerging object-relational database systems provide features for defining, storing, updating, indexing, and retrieving complex data types with full transaction semantics. This talk will describe these features in the context of OracleSi database technology with examples from existing e-commerce and emerging XML data.</abstract></paper><paper><title>Using XML in Relational Database Applications</title><author><AuthorName>Susan Malaika</AuthorName><institute><InstituteName>IB</InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>This talk will review relational database XML features and will describe their use in database applications. Aspects that will be considered include the creation, validation, transformation, storage and retrieval of XML documents, the inclusion of existing and new relational data in XML documents, and the impact of XML Links.</abstract></paper><paper><title>Document Warehousing Based on a Multimedia Database System</title><author><AuthorName>Hiroshi Ishikawa</AuthorName><institute><InstituteName>Fujitsu Laboratories Ltd</InstituteName><country></country></institute></author><author><AuthorName>Kazumi Kubota</AuthorName><institute><InstituteName>Fujitsu Laboratories Ltd</InstituteName><country></country></institute></author><author><AuthorName>Yasuo Noguchi</AuthorName><institute><InstituteName>Fujitsu Laboratories Ltd</InstituteName><country></country></institute></author><author><AuthorName>Koki Kato</AuthorName><institute><InstituteName>Fujitsu Laboratories Ltd</InstituteName><country></country></institute></author><author><AuthorName>Miyuki Ono</AuthorName><institute><InstituteName>Fujitsu Laboratories Ltd</InstituteName><country></country></institute></author><author><AuthorName>Naomi Yoshizawa</AuthorName><institute><InstituteName>Fujitsu Laboratories Ltd</InstituteName><country></country></institute></author><author><AuthorName>Yasuhiko Kanemasa</AuthorName><institute><InstituteName>Fujitsu Laboratories Ltd</InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Nowadays, structured data such as sales and business forms are stored in data warehouses for decision makers to use. Further, unstructured data such as emails, html texts, images, videos, and oftIce documents are increasingly accumulated in personal computer storage due to spread of mailing, Www, and word processing. Such unstructured data, or what we call multimedia documents, are larger in volume than structured data and precious as corporate assets as well. So we need a document warehouse as a software framework where multimedia documents are analyzed and managed for corporate-wide information sharing and reuse like a data warehouse for structured data. We describe a prototype document warehouse system, which supports management of simple and compound documents, keyword-based and content-based retrieval, rule-based classification, SOM-based clustering, and XML data query and view rules.</abstract></paper><paper><title>The ECHO Method: Concurrency Control Method for a Large-Scale Distributed Database</title><author><AuthorName>Yukari Shirota</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Atsushi Iizawa</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Hiroko Mano</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Takashi Yano</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>When constructing a large-scale database system, data replication is useful to give users efficient access to that data. However, for databases with a very large number of replica sites, using traditional networking concurrency control protocols makes communication too costly for practical use. In this paper, we propose a new protocol called ECHO for concurrency control of replica data distributed on a large scale. Using broadcasting, such as satellite broadcasting, terrestrial broadcasting, and cable television, the ECHO method can keep communication costs constant, regardless of the number of sites. The ECHO method also has a backup mechanism for failed broadcast reception using the communication network.</abstract></paper><paper><title>Data Mining from an Al Perspective</title><author><AuthorName>Ross Quinlan</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Data Mining, or Knowledge Discovery in Databases as it is also called, is claimed as an offspring by three disciplines: databases, statistics, and the machine learning subfield of artificial intelligence. (The term originated in statistics with distinctly pejorative overtones -data mining was characterized as fossicking in data without a guiding model.) Statistics is obviously relevant because that field has always focused on construction of models from data. Databases, too, is clearly central because current applications of data mining can involve very large corpora of information that are not necessarily in flat file form. So what' s left to be claimed by artificial intelligence and, in particular, machine learning? This talk will provide a definitely non-impartial answer to this question from the standpoint of a long-time ML practitioner.</abstract></paper><paper><title>Constraint-Based Rule Mining in Large, Dense Databases</title><author><AuthorName>Roberto J. Bayardo, Jr.</AuthorName><institute><InstituteName>Jr."&gt;Roberto J. Bayardo, Jr.</InstituteName><country></country></institute></author><author><AuthorName>Rakesh Agrawal</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Dimitrios Gunopulos</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Constraint-based rule miners find all rules in a given data-set meeting user-specified constraints such as minimum support and confidence. We describe a new algorithm that directly exploits all user-specified constraints including minimum support, minimum confidence, and a new constraint that ensures every mined rule offers a predictive advantage over any of its simplifications. Our algorithm maintains efficiency even at low supports on data that is dense (e.g. relational data). Previous approaches such as Apriori and its variants exploit only the minimum support constraint, and as a result are ineffective on dense data due to a combinatorial explosion of &amp;quot;frequent itemsets&amp;quot;.</abstract></paper><paper><title>Parallel Classification for Data Mining on Shared-Memory Multiprocessors</title><author><AuthorName>Mohammed J. Zaki</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Ching-Tien Ho</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Rakesh Agrawal</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>We present parallel algorithms for building decision-tree classifiers on shared-memory multiprocessor (SMP) systems. The proposed algorithms span the gamut of data and task parallelism. The data parallelism is based on attribute scheduling among processors. This basic scheme is extended with task pipelining and dynamic load balancing to yield faster implementations. The task parallel approach uses dynamic subtree partitioning among processors. Our performance evaluation shows that the construction of a decision-tree classifier can be effectively parallelized on an SMP machine with good speedup.</abstract></paper><paper><title>Mining Optimized Support Rules for Numeric Attributes</title><author><AuthorName>R. Rastogi</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>K. Shim</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>In this paper, we generalize the optimized support association rule problem by permitting rules to contain disjunctions over uninstantiated numeric attributes. For rules containing a single numeric attribute, we present a dynamic programming algorithm for computing optimized association rules. Furthermore, we propose a bucketing technique for reducing the input size, and a divide and conquer strategy that improves the performance significantly without sacrificing optimality. Our experimental results for a single numeric attribute indicate that our bucketing and divide and conquer enhancements are very effective in reducing the execution times and memory requirements of our dynamic programming algorithm. Furthermore, they show that our algorithms scale up almost linearly with the attribute's domain size as well as the number of disjunctions.</abstract></paper><paper><title>Using Java and CORBA for Implementing Internet Databases</title><author><AuthorName>Athman Bouguettaya</AuthorName><institute><InstituteName>Queensland University of Technolog</InstituteName><country></country></institute></author><author><AuthorName>Mourad Ouzzani</AuthorName><institute><InstituteName>Queensland University of Technolog</InstituteName><country></country></institute></author><author><AuthorName>Lily Hendra</AuthorName><institute><InstituteName>Queensland University of Technolog</InstituteName><country></country></institute></author><author><AuthorName>Boualem Benatallah</AuthorName><institute><InstituteName>James Cook Universit</InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>We describe an architecture called WebFINDIT that allows dynamic couplings of Web accessible databases based on their content and interest. We propose an implementation using WWW, Java, JDBC, and CORBA's ORBS that communicate via the CORBA's HOP protocol. The combination of these technologies offers a compelling middleware infrastructure to implement wide-area enterprise applications. In addition to a discussion of WebFINDIT's core concepts and implementalion architecture, we also discuss an experience of using WebFINDIT in a healthcare application.</abstract></paper><paper><title>Mobile Agents for WWW Distributed Database Access</title><author><AuthorName>Stavros Papastavrou</AuthorName><institute><InstituteName>University of Cypru</InstituteName><country></country></institute></author><author><AuthorName>George Samaras</AuthorName><institute><InstituteName>University of Cypru</InstituteName><country></country></institute></author><author><AuthorName>Evaggelia Pitoura</AuthorName><institute><InstituteName>University of Ioannin</InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>The popularity of the web as a universal access mechanism for network information has created the need for developing web-based DBMS client/server applications. However, the current commercial applet-based methodologies for accessing database systems offer limited flexibility, scalability and robustness. In this paper, we propose a new framework for Web- based distributed access to database systems based on Java-based mobile agents. The framework supports light-weight, portable and autonomous clients as well as operation on slow or expensive networks. The implementation of the framework shows that its performance is comparable to, and in some case outperforms, the current approach. In fact, in a wireless and dial-up environments and for average size transactions, a client/agent/server adaptation of the framework provided a performance improvement of approximately a factor often. For the fixed network the gains were about 40% and 30% respectively.</abstract></paper><paper><title>Working Together in Harmony - An Implementation of the CORBA Object Query Service and its Evaluation</title><author><AuthorName>U. Rohm</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>K. Bohm</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract></abstract></paper><paper><title>Fast Approximate Search Algorithm for Nearest Neighbor Queries in High Dimensions</title><author><AuthorName>Sakti Pramanik</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Jinhua Li</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>In this paper, we present a fast approximate nearest neighbor (NN) search index structure called the AB-tree, which uses heuristics to decide whether or not to access a node in the index tree based on the intersecting angle and the weight of the node. The goal of the NN search algorithm presented in this paper is to decrease unnecessary node accesses in the search due to overlap among bounding regions in existing index structures. We have observed the following three properties of bounding hyperspheres that motivated the creation of the proposed heuristics for NN search.</abstract></paper><paper><title>Data Warehouse Maintenance Under Concurrent Schema and Data Updates</title><author><AuthorName>Elke A. Rundensteiner</AuthorName><institute><InstituteName>Worcester Polytechnic Institute, M</InstituteName><country></country></institute></author><author><AuthorName>Xin Zhang</AuthorName><institute><InstituteName>Worcester Polytechnic Institute, M</InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract></abstract></paper><paper><title>Data Warehouse Evolution: Trade-offs between Quality and Cost of Query Rewritings</title><author><AuthorName>Amy J. Lee</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Andreas Koeller</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Anisoara Nica</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Elke A. Rundensteiner</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1999</year><conference>International Conference on Data Engineering</conference><citation></citation><abstract>Query rewriting has been used as a query optimization technique for several decades to reduce the computational cost of a query. It has generally been assumed that any rewritten query will generate the identical query result as the original query, in terms of both the query interface and the query extent. Hence, this is called &amp;quot;equivalent query rewriting&amp;quot;.Recently, query rewriting with relaxed semantics has been proposed as a means of retaining the validity of a data warehouse (i.e., materialized queries) in a changing envi-ronment [2, 3, 4]. Attributes in the query interface can be classified as essential or dispensable (if it cannot be retained) according to the query definer's preferences. Simi-larly, preferences for query extent can be specified, for example, to indicate whether a subset of the original result is acceptable or not. A query rewriting is said to be acceptable if it preserves the essential information of the original query and satisfies the constraint on the view extent. Since each rewriting may preserve the original query to a different degree, a potentially large number of acceptable yet non-equivalent query rewritings may be found. Therefore, we need to systematically select the most promising rewriting out of all possible ones. Research issues that must be an-swered for solving this problem are outlined below.We have found that the two most important factors influencing the desirability of a query rewriting are: the information preserved by the