Lecture Notes in Computer Science Edited by G. Goos, J. Hartmanis, and J. van Leeuwen 2435 3 Berlin Heidelberg New Y...

Author: Yannis Manolopoulos | Pavol Navrat

65 downloads 832 Views 5MB Size Report

This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!

Report copyright / DMCA form

DOWNLOAD PDF

Lecture Notes in Computer Science Edited by G. Goos, J. Hartmanis, and J. van Leeuwen

2435

3

Berlin Heidelberg New York Barcelona Hong Kong London Milan Paris Tokyo

Yannis Manolopoulos Pavol Návrat (Eds.)

Advances in Databases and Information Systems 6th East European Conference, ADBIS 2002 Bratislava, Slovakia, September 8-11, 2002 Proceedings

13

Series Editors Gerhard Goos, Karlsruhe University, Germany Juris Hartmanis, Cornell University, NY, USA Jan van Leeuwen, Utrecht University, The Netherlands Volume Editors Yannis Manolopoulos Aristotle University, Department of Informatics 54006 Thessaloniki, Greece E-mail: [email protected] Pavol Návrat Slovak University of Technology, Department of Computer Science and Engineering Ilkovicova 3, 81219 Bratislava, Slovakia E-mail: [email protected]

Cataloging-in-Publication Data applied for Die Deutsche Bibliothek - CIP-Einheitsaufnahme Advances in databases and information systems : 6th East European conference ; proceedings / ADBIS 2002, Bratislava, Slovakia, September 8 - 11, 2002. Yannis Manolopoulos ; Pavol Návrat (ed.). - Berlin ; Heidelberg ; New York ; Barcelona ; Hong Kong ; London ; Milan ; Paris ; Tokyo : Springer, 2002 (Lecture notes in computer science ; Vol. 2435) ISBN 3-540-44138-7

CR Subject Classification (1998): H.2, H.3, H.4, H.5, J.1 ISSN 0302-9743 ISBN 3-540-44138-7 Springer-Verlag Berlin Heidelberg New York This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer-Verlag. Violations are liable for prosecution under the German Copyright Law. Springer-Verlag Berlin Heidelberg New York a member of BertelsmannSpringer Science+Business Media GmbH http://www.springer.de © Springer-Verlag Berlin Heidelberg 2002 Printed in Germany Typesetting: Camera-ready by author, data conversion by Christian Grosche, Hamburg Printed on acid-free paper SPIN 10870148 06/3142 543210

Preface This volume is devoted to advances in databases and information systems, one of the many active research areas in Computer Science within the broader ﬁeld of Computing (or Informatics, as it is also called). The chapters in this monograph were actually papers on the program of the 6th Conference on Advances in Databases and Information Systems (ADBIS), held on September 8–11, 2002 in Bratislava, Slovakia. The series of ADBIS Conferences is a successor of the annual international workshops under the same title, which were organized by the Moscow ACM SIGMOD Chapter during 1993–1996. In 1997, the 1st East European Conference on Advances in Databases and Information Systems was held in St. Petersburg, Russia, and the series was continued in Poznan, Poland in 1998, Maribor, Slovenia in 1999, Prague, Czech Republic in 2000, Vilnius, Lithuania in 2001, and now in Bratislava, Slovakia in 2002. The ADBIS Conference has become the premier event gathering researchers Central and Eastern Europe working in the area, providing an internationally recognized forum for presentation of their research results. More than that, the ADBIS conference has evolved into one of the important European conferences in the area, but also one which is attended by researchers from all over the world. There is no better way to support the above statements than to give basic data about the ADBIS 2002 Conference. It was organized by the Slovak University of Technology (STU) in Bratislava (and, in particular, its Faculty of Electrical Engineering and Information Technology) in cooperation with the ACM SIGMOD, the Moscow ACM SIGMOD Chapter, and the Slovak Society for Computer Science. It attracted 115 submissions from 35 countries on all continents, alas, except Africa. The submissions were subject to a rigorous review process with each paper having been reviewed by three and sometimes even more referees. The ADBIS Conference is known for its continuous eﬀort to set and comply with high quality standards with respect to the accepted papers. This makes the selection process even more diﬃcult for the Program Committee (PC) and, eventually, the PC cochairs and volume editors, since many submitted papers could not be included in this volume, although they were considered as good ones in general. After many live and online discussions, 25 full papers and 4 short papers were accepted for inclusion in this volume, constituting the ADBIS 2002 Conference proceedings. The high number of submissions is a clear sign that the ADBIS Conference series has acquired a worldwide interest and recognition. The authors of this volume come from 22 countries on four continents. Interestingly enough, Eastern Europe is no longer the most heavily represented region. This shows that while the ADBIS Conference maintains its focus, facilitating collaboration between researchers from that region and other parts of the world, it has also already become a fully international event that is standard by all the relevant criteria.

VI

Preface

Besides these 29 regular papers, this volume includes also three invited papers that were presented at the conference as invited lectures. We are happy that we could include invited papers on such attractive topics in the area, as Web Site Modelling, Privacy and Security in ASP and Web Service Environments, and Infrastructure for Information Spaces, presented by very prominent authorities in the ﬁeld. The conference program was complemented by two tutorials and several research communications. We should like to thank: – all the reviewers, and the PC members in particular, who made this volume and, in fact, the 2002 ADBIS Conference possible by volunteering to review in accordance with strict criteria of scientiﬁc merit; – the Steering Committee of the ADBIS Conferences, and, in particular, its Chairman, Leonid Kalinichenko, for their guidance and advice; – the Organizing Committee, and, in particular, its Chairwoman Maria Bielikova, for their very eﬀective support in the technical preparation of this proceedings and in making the conference happen; – Springer-Verlag for publishing these proceedings, and Alfred Hofmann, in particular, for eﬀective support in producing them; – last, but not least, the authors of the chapters in this volume, for contributing such excellent papers reporting their recent research results. We hope that these proceedings will be useful to the researchers and academics that work in the area of Databases and Information Systems. Thus, we anticipate that in the future the interest of the research community in the ADBIS Conference series will continue to increase.

June 2002

Yannis Manolopoulos Pavol N´avrat

Organization

The Sixth Conference on Advances in Databases and Information Systems (ADBIS), held on September 8–11, 2002 in Bratislava, Slovakia, was organized by the Slovak University of Technology (and, in particular, its Faculty of Electrical Engineering and Information Technology) in Bratislava in cooperation with ACM SIGMOD, the Moscow ACM SIGMOD Chapter, and the Slovak Society for Computer Science.

General Chair Ludov´ıt Moln´ ar (Rector, Slovak University of Technology in Bratislava, Slovakia)

Program Committee C-Chairs Yannis Manolopoulos (Aristotle University of Thessaloniki, Greece) Pavol N´avrat (Slovak University of Technology in Bratislava, Slovakia)

Program Committee Leopoldo Bertossi (Carleton University, Ottawa, Canada) Maria Bielikova (Slovak University of Technology in Bratislava, Slovakia) Omran A. Bukhres (Indiana University – Purdue University, Indianapolis, USA) Albertas Caplinskas (Inst. of Mathematics and Informatics, Vilnius, Lithuania) Wojciech Cellary (Poznan University of Economics, Poland) Bogdan Czejdo (Loyola University, New Orleans, USA) Marjan Druzovec (University of Maribor, Slovenia) Johann Eder (University of Klagenfurt, Austria) Heinz Frank (University of Klagenfurt, Austria) Remigijus Gustas (Karlstad University, Sweden) Tomas Hruska (Brno University of Technology, Czech Republic) Leonid Kalinichenko (Russian Academy of Sciences, Russia) Wolfgang Klas (University of Vienna, Austria) Matthias Klusch (German Research Center for Artiﬁcial Intelligence, Saarbr¨ ucken, Germany) Mikhail Kogalovsky (Russian Academy of Sciences, Russia) Karol Matiasko (University of Zilina, Slovakia) Mikhail Matskin (Norwegian Univ. of Science and Tech., Trondheim, Norway) Tomaz Mohoric (University of Ljubljana, Slovenia) Tadeusz Morzy (Poznan University of Technology, Poland) Nikolay Nikitichenko (National Taras Shevchenko University of Kiev, Ukraine) Boris Novikov (University of St. Petersburg, Russia)

VIII

Preface

Maria Orlowska (University of Queensland, Australia) Euthimios Panagos (AT&T Labs, USA) Oscar Pastor (Valencia University of Technology, Spain) Guenther Pernul (University of Essen, Germany) Jaroslav Pokorny (Charles University, Prague, Czech Republic) Henrikas Pranevichius (Kaunas University of Technology, Lithuania) Colette Rolland (Universit´e Paris 1 Panth´eon-Sorbonne, France) George Samaras (University of Cyprus, Nicosia, Cyprus) Klaus-Dieter Schewe (Massey University, New Zealand) Joachim W. Schmidt (Technical University Hamburg-Harburg, Germany) Timothy K. Shih (Tamkang University, China) Myra Spiliopolou (Leipzig Graduate School of Management, Germany) Julius Stuller (Academy of Sciences, Czech Republic) Bernhard Thalheim (Brandenburg University of Technology, Cottbus, Germany) Aphrodite Tsalgatidou (University of Athens, Greece) Vladimir Vojtek (Slovak University of Technology in Bratislava, Slovakia) Gottfried Vossen (University of Muenster, Germany) Benkt Wangler (University of Skoevde, Sweden) Tatjana Welzer (University of Maribor, Slovenia) Viacheslav Wolfengagen (Inst. for Contemporary Education, Moscow, Russia) Vladimir Zadorozhny (University of Pittsburgh, USA) Alexander Zamulin (Russian Academy of Sciences, Russia)

Additional Reviewers Eleni Berki Susanne Boll Panagiotou Chirstoforos Peter Dolog Georgios Evangelidis Holger Grabow Sebastian Graf Birgit Hofreiter Marcus Huetten Dimitrios Katsaros Susanne Kjernald Christian Koncilia Zbyszko Krolikowski George Laskaridis Sebastian Link Alexandros Nanopoulos Igor Nekrestyanov Apostolos N. Papadopoulos Ekaterina Pavlova Vicente Pelechano

Torsten Priebe Jarogniew Rykowski Wasim Sadiq Torsten Schlichting Krasten Schulz Oleg Seleznev Mattias Strand Konrad Thalheim Yannis Theodoridis Dimitrios Theotokis Marek Trabalka Alexei Tretiakov Jose Maria Turull Torres Costas Vassilakis Michael Gr. Vassilakopoulos Utz Westermann Wojciech Wiza Marek Wojciechowski Maciej Zakrzewicz

Preface

IX

Organizing Committee Chair M´ aria Bielikov´a (Slovak University of Technology in Bratislava, Slovakia) Members Peter Dolog (Slovak University of Technology in Bratislava, Slovakia) Miroslav Galbavy (Slovak University of Technology in Bratislava, Slovakia) Maria Hricova (Slovak University of Technology in Bratislava, Slovakia) Tibor Krajcovic (Slovak University of Technology in Bratislava, Slovakia) Alexandros Nanopoulos (Aristotle University of Thessaloniki, Greece) Pavol N´avrat (Slovak University of Technology in Bratislava, Slovakia) Gabriela Polcicova (Slovak University of Technology in Bratislava, Slovakia) Maria Smolarova (Slovak University of Technology in Bratislava, Slovakia) Branislav Steinmuller (Slovak University of Technology in Bratislava, Slovakia)

ADBIS Steering Committee Chair Leonid Kalinichenko (Russia) Members Andras Benczur (Hungary) Radu Bercaru (Romania) Albertas Caplinskas (Lithuania) Johann Eder (Austria) Janis Eiduks (Latvia) Hele-Mai Haav (Estonia) Mirjana Ivanovic (Yugoslavia) Mikhail Kogalovsky (Russia) Yannis Manolopoulos (Greece)

Rainer Manthey (Germany) Tadeusz Morzy (Poland) Pavol N´avrat (Slovakia) Boris Novikov (Russia) Jaroslav Pokorny (Czech Republic) Boris Rachev (Bulgaria) Anatoly Stogny (Ukraine) Tatjana Welzer (Slovenia) Viacheslav Wolfengagen (Russia)

Table of Contents

Invited Lectures Time: A Coordinate for Web Site Modelling . . . . . . . . . . . . . . . . . . . . . . . . . . . Paolo Atzeni

1

Trust Is not Enough: Privacy and Security in ASP and Web Service Environments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Claus Boyens, Oliver G¨ unther

8

Infrastructure for Information Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 Hans-J¨ org Schek, Heiko Schuldt, Christoph Schuler, Roger Weber

Data Mining and Knowledge Discovery An Axiomatic Approach to Deﬁning Approximation Measures for Functional Dependencies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 Chris Giannella Intelligent Support for Information Retrieval in the WWW Environment . . 51 Robert Koval, Pavol N´ avrat An Approach to Improve Text Classiﬁcation Eﬃciency . . . . . . . . . . . . . . . . . . 65 Shuigeng Zhou, Jihong Guan Semantic Similarity in Content-Based Filtering . . . . . . . . . . . . . . . . . . . . . . . . 80 Gabriela Polˇcicov´ a, Pavol N´ avrat Data Access Paths for Frequent Itemset Discovery . . . . . . . . . . . . . . . . . . . . . 86 Marek Wojciechowski, Maciej Zakrzewicz

Mobile Databases Monitoring Continuous Location Queries Using Mobile Agents . . . . . . . . . . . 92 Sergio Ilarri, Eduardo Mena, Arantza Illarramendi Optimistic Concurrency Control Based on Timestamp Interval for Broadcast Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 Ukhyun Lee, Buhyun Hwang A Flexible Personalization Architecture for Wireless Internet Based on Mobile Agents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 George Samaras, Christoforos Panayiotou Multiversion Data Broadcast Organizations . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 Oleg Shigiltchoﬀ, Panos K. Chrysanthis, Evaggelia Pitoura

XII

Table of Contents

Spatiotemporal and Spatial Databases Revisiting R-Tree Construction Principles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 Sotiris Brakatsoulas, Dieter Pfoser, Yannis Theodoridis Approximate Algorithms for Distance-Based Queries in High-Dimensional Data Spaces Using R-Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 Antonio Corral, Joaquin Ca˜ nadas, Michael Vassilakopoulos Eﬃcient Similarity Search in Feature Spaces with the Q-Tree . . . . . . . . . . . . 177 Elena Jurado, Manuel Barrena Spatio-Temporal Geographic Information Systems: A Causal Perspective . . 191 Baher A. El-Geresy, Alia I. Abdelmoty, Christopher B. Jones An Access Method for Integrating Multi-scale Geometric Data . . . . . . . . . . . 204 Joon-Hee Kwon, Yong-Ik Yoon

Multidimensional Databases and Information Systems OLAP Query Evaluation in a Database Cluster: A Performance Study on Intra-Query Parallelism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 Fuat Akal, Klemens B¨ ohm, Hans-J¨ org Schek A Standard for Representing Multidimensional Properties: The Common Warehouse Metamodel (CWM) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232 Enrique Medina, Juan Trujillo A Framework to Analyse and Evaluate Information Systems Speciﬁcation Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248 Albertas Caplinskas, Audrone Lupeikiene, Olegas Vasilecas

Object Oriented and Deductive Databases Flattening the Metamodel for Object Databases . . . . . . . . . . . . . . . . . . . . . . . 263 Piotr Habela, Mark Roantree, Kazimierz Subieta A Semantic Query Optimization Approach to Optimize Linear Datalog Programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277 Jos´e R. Param´ a, Nieves R. Brisaboa, Miguel R. Penabad, ´ Angeles S. Places An Object Algebra for the ODMG Standard . . . . . . . . . . . . . . . . . . . . . . . . . . 291 Alexandre Zamulin

Data Modeling and Workﬂows Many-Dimensional Schema Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305 Thomas Feyer, Bernhard Thalheim

Table of Contents

XIII

Object-Oriented Data Model for Data Warehouse . . . . . . . . . . . . . . . . . . . . . . 319 Alexandre Konovalov A Meta Model for Structured Workﬂows Supporting Workﬂow Transformations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326 Johann Eder, Wolfgang Gruber

Web Databases and Semistructured Data Towards an Exhaustive Set of Rewriting Rules for Xquery Optimization: BizQuery Experience . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340 Maxim Grinev, Sergey Kuznetsov Architecture of a Blended-Query and Result-Visualization Mechanism for Web-Accessible Databases and Associated Implementation Issues . . . . . . . . 346 Mona Marathe, Hemalatha Diwakar Accommodating Changes in Semistructured Databases Using Multidimensional OEM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 360 Yannis Stavrakas, Manolis Gergatsoulis, Christos Doulkeridis, Vassilis Zafeiris A Declarative Way of Extracting XML Data in XSL . . . . . . . . . . . . . . . . . . . . 374 Jixue Liu, Chengfei Liu

Advanced Systems and Applications Towards Variability Modelling for Reuse in Hypermedia Engineering . . . . . 388 Peter Dolog, M´ aria Bielikov´ a Complex Temporal Patterns Detection over Continuous Data Streams . . . . 401 Lilian Harada

Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415

Time: A Coordinate for Web Site Modelling Paolo Atzeni Dipartimento di Informatica e Automazione Universit` a di Roma Tre Via della Vasca Navale, 79, 00146 Roma, Italy http://www.dia.uniroma3.it/~atzeni/ [email protected]

Abstract. The adoption of high level models has been advocated by many authors as instrumental in Web site development as a strong support to both design and maintenance. We will discuss how the speciﬁcation of Web sites at the logical level can greatly beneﬁt from the introduction of speciﬁc features for the representation of time, which could also support the notions of versions and editions of objects in the site. Moreover, time can be seen as a “coordinate” of Web models, a more general notion that includes various forms of specializations and variations, such as those related to location, language, user preferences, device type.

1

Introduction

The usefulness of high-level models for the intensional description of Web sites has been advocated by various authors, including Atzeni et al. [1,2], Ceri et al. [3], which both propose logical models in a sort of traditional database sense, and Fernandez et al. [4], which instead propose an approach based on semistructured data. Speciﬁcally, we focus our attention on data-intensive Web sites, where more structured models can deﬁnitely be useful: they can be described by means of schemes (logical hypertext scheme and associated presentation) and can be obtained by applying suitable algebraic transformations to the data stored in an underlying database (see Atzeni et al. [5]). In this context, we want to consider the issues related to the management of time-varying information, along the lines that in the database ﬁeld lead to the interesting area of temporal databases (see Jensen and Snodgrass [6] for a recent survey). Indeed, work has already been done on temporal aspects in the Web (for example by Dyreson [7] and Grandi and Mandreoli [8]), but mainly in the context of the management of documents and with use of XML. Instead, we would like to see how a structured model for the Web could beneﬁt from the experience in temporal databases. Speciﬁcally, we assume that the logical structure of a Web site can be described by means of a complex-object data model with object identity, with some degree of ﬂexibility, but all described in the scheme. We (Atzeni et al. [1]) have proposed such a model, called ADM, with the following features: Y. Manolopoulos and P. N´ avrat (Eds.): ADBIS 2002, LNCS 2435, pp. 1–7, 2002. c Springer-Verlag Berlin Heidelberg 2002

2

Paolo Atzeni

– pages with the same structure and diﬀerent content are described by a page scheme, with the url as identiﬁer and a set of attributes; – attributes can be (i) simple, with a type that can be a standard one (such as text, number, image) or link; (ii) complex: lists, which can be structured (that is, involve several attributes) and nested; – heterogeneous unions can be used to specify that some attributes are optional and alternative to others and forms are modelled as virtual lists. Following the terminology common in temporal databases, we can say that ADM could be used to describe snapshot Web sites, that is, conventional Web sites with no explicit management of time. The goal of this paper is to express requirements and to comment on possible research directions concerning modelling issues. We will not consider query languages, which indeed constitute a major issue in temporal database management, since in our approach they can be seen as an “implementation” issue: our major goal is to understand which could be the right way to organize information to be oﬀered to Web users; in turn, in a data-intensive site, this information should be extracted from a database, probably by means of time-aware expressions, which could be written in a temporal query language or in a standard query language, but automatically generated by means of a CASE tool [5]. Indeed, we have a situation similar to that reported by Snodgrass [9, p.389] with respect to temporal object-oriented databases: the challenge is to augment a logical model for Web sites in order to capture history of pages and their components, and to publish them in a suitable way. Indeed, since, as we argued above, we assume that Web sites are modelled by means a complex-object model with identity, it is clear that the most interesting ideas for temporal models in this framework should come from models with identity, so temporal extensions of the object model (as discussed by Snodgrass [9, p.389]) or of Entity-Relationship models (surveyed by Gregersen an Jensen [10]). The rest of this paper is organized as follows. In Section 2 we comment on how the known dimensions for time (valid and transaction) are meaningful in this context. In Section 3 we expose the main requirements for the deﬁnition of temporal models for data-intensive Web sites, with respect to ﬁxed schemes. Section 4 is devoted to some additional issues, which include those related to schema versioning and others that speciﬁcally arise in a Web framework. Finally, Section 5 is devoted to concluding remarks which sketch the idea of considering time just as one possible dimension, together with others that could be dealt with in a similar way.

2

Time Dimensions

As clearly discussed in all surveys on temporal databases (for example Snodgrass [9] or Jensen and Snodgrass [6]), there are various dimensions along which time can be considered. Beside user-defined time (the semantics of which is “known only to the user”, and therefore is not explicitly handled), we have valid

Time: A Coordinate for Web Site Modelling

3

time (“the time a fact was true in reality”) and transaction time (“the time the fact was stored in the database”). In a Web site, the motivation for valid time is similar to the one in temporal databases: we are often interested in describing not only snapshots of the world, but also histories about its facts. The slight diﬀerence here is that in temporal databases the interest is in storing histories and in being able to answer queries about both snapshots and histories, whereas in Web sites the challenge is on how histories are oﬀered to site visitors, who browse and do not query. Therefore, this is a design issue, to be dealt with by referring to the requirements we have for the site. The natural (and not expensive) redundancy common in Web sites could even suggest to have a coexistence of snapshots and histories. Transaction time in Web sites is related to the support of the archival nature of the Web, which could be stated, with a bit of exaggeration, as: “once a piece of information is published, it should not be retracted.” While the above claim could in general be questioned, or at least interpreted in various ways, it is clear that in many cases it refers to an important user need: for example, if our university publishes wrong information about the exam calendar, which is later corrected, then students who were misled could strongly argue against the university. In more plain terms, we would often be interested in documenting what was the content of the Web site at a given point in time. As with valid time, this can be handled in various ways, depending on the actual requirements: history could be documented only for some important pieces of information, and, in contrast with what happens in relational databases, it can be managed by complex structures where new data is appended. This can help in documenting the changes on a Web site. In the Web, a couple of additional issues emerge for transaction time which are not relevant in databases. First of all, as Dyreson [7] noted, there are no transactions on the Web, and so it is not obvious how to keep track of events. In general, this can be seen as a problem, a solution for which is the idea of observant systems [7], which can read data but do not really manage them; both Web servers and browsers are observant systems. However, in a data-intensive Web site, the problem can be reasonably handled, if the underlying database is suitably monitored—another motivation for a strong correspondence between a Web site and a database. A second issue, also noted by Dyreson [7], is that, while transaction-time in temporal databases is bounded by the current time, in a Web framework it could also refer to the future, to be used for planning publication; in some sense, it turns out that transaction time in the Web site need not be the same as transaction time in the underlying database, but we believe that we can still take advantage of the correspondence between the two.

3

Modelling Time

The basic ideas are here very similar to those mentioned by Snodgrass [9] about the representation of valid-time support in object oriented databases. The most

4

Paolo Atzeni

natural solution to follow is the direct incorporation of time into the data model, with the introduction of speciﬁc constructs, which could include: – the distinction between temporal and non-temporal page-schemes (with respect to the existence of their instances, not with the variability of their content); for example, it is likely that the home-page of a site is non-temporal, because it always exists (during the life of the site), whereas the instances of the course page-scheme in our department site have a lifespan corresponding to the time when the respective courses exist; – the distinction between temporal and nontemporal attributes: during the lifespan of an object, some attributes have a ﬁxed value, whereas others are allowed to change; given the nested nature of the model, this distinction should be allowed at any level of nesting, but with some limitations: each attribute should either be nontemporal or be temporal either because it is declared temporal or because (exactly) one of the higher level attributes that include it is temporal; – the time granularity associated with each temporal page scheme or attribute: it could be convenient to have diﬀerent granularities: for example, in a school calendar we could have the academic year as the granularity for courses and the week for the seminar schedule; – the way we are interested in oﬀering these pieces of information on the site: • by means of snapshots on speciﬁc instants; for example, in our calendar example, we could be interested in seeing the page of a course with this year’s (or last year’s) instructor and content; • by oﬀering the history of valid values: in the same example, a list of the instructors for a given course throughout the years; • by means of a combined, redundant approach: an index with a list (essentially describing a history) and with snapshot pages; • by a more compact list showing only changes in the values. In each case, links have to be coordinated suitably, if needed; for example, if also instructor pages are temporal, then we could decide to have the instructor link in last year’s version of a course page to last year’s version of the instructor page (provided that the granularity is the same). Clearly, solutions are not obvious, and designer’s choices are important (and the model should leave space for them).

4

More Time-Related Issues

Many other aspects that concern time could be relevant in modelling Web sites. Let us comment on some of them. 4.1

Version Management

In temporal object-oriented databases (Snodgrass [9]), version management is discussed with respect to transaction time. It is not obvious that the same should

Time: A Coordinate for Web Site Modelling

5

hold for Web sites. For example, what does it mean to have versions of the hypertext organization, or versions of the graphical layout? We could be interested in seeing information which was valid last year with today’s organization, or vice versa. This has little to do with transaction time. In some sense (we will come back to this point later), versioning can give rise to diﬀerent coordinates (at least partially independent), which correspond to the oft cited components of a Web site, data, hypertext, presentation [11,4,5]: – changes in the presentation; – changes in the hypertext structure (with possible consequences on the presentation); – changes in the database structure (with consequences on hypertext structure and presentation). This issue clearly deserves speciﬁc attention. It should be noted that, if the design process is supported by a tool that allows the speciﬁcation of transformation primitives [5], then the possible transformations can be known a priori, in the same way as suggested by Kim and Chou [12] for version management of objectoriented databases. With schema versions, the need for accurate management of links becomes even more delicate than in the cases discussed earlier. 4.2

Documenting the Degree of Currency of Information

We often see in Web pages the comment “last updated on ...” While these notes are useful, they only fulﬁll a small fraction of the user needs in this context. Indeed, especially when a page is generated out of a database, what does such a date mean: the last date the page was generated? or the last date a piece of information appearing in the page was changed? if so, what changed when? Also, in most cases, we would like to know what is the “currency reliability” of a page, which could be expressed as: “when was the information in the page last veriﬁed”? These issues are once again delicate and dependent on user needs, they also interact with granularity (which pieces of information do we want to tag in this way, with the right compromise between legibility and detail?), and can beneﬁt from the support of an underlying database. Once more, the crucial issue is to understand how to support the designer in the speciﬁcation of these features. 4.3

Time Support Provided by a Content Management System

It is now widespread the idea that Web sites should be supported by content management systems, which allow users to update the information in the site, by means of speciﬁc services supported by the site itself (with suitable protection). In a data intensive site, this would mean that the updates to the database could be controlled in a tight manner, and not appear in an unrestricted way. In this framework, most of the issues we discussed above could be supported in

6

Paolo Atzeni

an interesting way, including the decision on what should be temporal and what should not, and on which is the appropriate level in nested structures with which time should be attached. Also, the management of the degree of currency could be eﬀectively supported.

5

Conclusions: A More General Perspective

One way to support time (be it valid time or transaction time) in Web sites is by providing support to the navigation of snapshot Web sites: the user speciﬁes in some way the instant he/she is interested in, and then navigation can proceed with reference only to that instant. Indeed, we have implemented a prototype which oﬀers this feature, as well as support for histories and versions (Del Nostro [13]), in a simple way: each page is dynamically generated with a parameter that speciﬁes the instant of interest. We have used a conventional database as a backend, and so the implementation has required eﬀort and eﬃciency has not been considered. However, this approach suggests an interesting point: time can be see as a coordinate for Web sites, in the same way as others, which could include language (a multilingual site has pages that depend on one parameter, the language), device, personal choices, and so forth. Similar issues were considered in the past with the idea of annotations (Sciore [14]) for object-oriented databases and with the management of metadata properties for semistructured data (Dyreson et al. [15]); the notion of context in WebML is also related (Ceri et al. [11]). In conclusion, we do believe that there is a lot of interesting issues to be dealt with in modelling time and other relevant “dimensions” in Web sites, and that they can be pursued in an interesting way if logical models are taken into account, both at Web site level and at an underlying database level: the management of transformations between the two levels could be a major beneﬁt. Acknowledgments I would like to thank Ernest Teniente and Paolo Merialdo, with whom I had some discussions on the topics of this paper, and Pierluigi Del Nostro, who explored some of these concepts and implemented a prototype within his master’s thesis. I am very indebted to Fabio Grandi and Carlo Combi who helped me in ﬁnding interesting references.

References 1. Atzeni, P., Mecca, G., Merialdo, P.: To weave the Web. In: Proceedings 23rd VLDB Conference, August 1997, Athens, Greece, Morgan Kauﬀman, Los Altos (1997) 206–215 2. Atzeni, P., Mecca, G., Merialdo, P.: Managing Web-based data: Database models and transformations. IEEE Internet Computing 6 (2002) 33–37

Time: A Coordinate for Web Site Modelling

7

3. Ceri, S., Fraternali, P., Bongio, A.: Web Modeling Language (WebML): A modeling language for designing Web sites. WWW9/Computer Networks 33 (2000) 137–157 4. Fernandez, M., Florescu, D., Levy, A., Suciu, D.: Declarative speciﬁcation of Web sites with Strudel. The VLDB Journal 9 (2000) 38–55 5. Merialdo, P., Mecca, G., Atzeni, P.: Design and development of data-intensive web sites: The Araneus approach. Technical report, Dipartimento di Informatica e Automazione, Universit` a di Roma Tre (2000) Submitted for publication. 6. Jensen, C., Snodgrass, R.: Temporal data management. IEEE Transactions on Knowledge and Data Engineering 11 (1999) 36–44 7. Dyreson, C.: Observing transaction-time semantics with TTXPath. In: Proceedings 2nd International Conference on Web Information Systems Engineering (WISE 2001), Kyoto, IEEE Computer Society (2001) 193–202 8. Grandi, F., Mandreoli, F.: The Valid Web: An XML/XSL infrastructure for temporal management of Web documents. In: Proceedings International Conference on Advances in Information Systems (ADVIS 2000), Izmir, Turkey, Springer LNCS 1909, Berlin (2000) 294–303 9. Snodgrass, R.: Temporal object-oriented databases: A critical comparison. In Kim, W. (ed.): Modern Database Systems: The Object Model, Interoperability, and Beyond. ACM Press and Addison-Wesley (1995) 386–408 10. H., G., Jensen, C.: Temporal entity-relationship models—A survey. IEEE Transactions on Knowledge and Data Engineering 11 (1999) 464–497 11. Ceri, S., Fraternali, P., Bongio, A., Brambilla, M., Comai, S., Matera, M.: Designing Data-Intensive Web Applications. Morgan Kauﬀman, Los Altos (2002) 12. Kim, W., Chou, H.: Versions of schema for object-oriented databases. In: Proceedings 14th VLDB Conference, Los Angeles, CA, Morgan Kauﬀman, Los Altos (1988) 148–159 13. Del Nostro, P.: La componente temporale nello sviluppo dei siti web (in Italian). Tesi di laurea in ingegneria informatica, Universit` a Roma Tre (2001) 14. Sciore, E.: Using annotations to support multiple kinds of versioning in an objectoriented database system. ACM Transactions on Database Systems 16 (1991) 417–438 15. Dyreson, C., B¨ ohlen, M., Jensen, C.: Capturing and querying multiple aspects of semistructured data. In: Proceedings 25th VLDB Conference, September 1999, Edinburgh, Scotland, Morgan Kauﬀman, Los Altos (1999) 290–301

Trust Is not Enough: Privacy and Security in ASP and Web Service Environments Claus Boyens* and Oliver Gnü ther Institute of Information Systems Humboldt-Universittä zu Berlin Spandauer Str. 1, 10178 Berlin, Germany {boyens,guenther}@wiwi.hu-berlin.de http://www.wiwi.hu-berlin.de/iwi

Abstract. Application service providers (ASPs) and web services are becoming increasingly popular despite adverse IT market conditions. New languages and protocols like XML, SOAP, and UDDI provide the technical underpinnings for a global infrastructure where anybody with a networked computer has access to a large number of digital services. Not every potential customer, however, may feel comfortable about entrusting sensitive personal or corporate data to a service provider in an unprotected manner. Even if there is a high level of trust between customer and provider, there may be legal requirements that require a higher level of privacy. Customers may also want to be prepared for an unforeseen change of control on the provider's side – something that is not an uncommon occurrence especially among start-up companies. This paper reviews several solutions how customers can use a provider's services without giving it access to any sensitive data. After discussing the relative merits of trust vs. technology, we focus on privacy homomorphisms, an encryption technique originally proposed by Rivest et al. that maintains the structure of the input data while obscuring the actual content. We conclude with several proposals how to integrate privacy homomorphisms into existing service architectures.

1

Introduction

Network-based services are software applications that are installed on a server and made available to users via a network, usually the Internet. The input data for these services needs to be made available by the customer (also called consumer or simply user), i.e., the person or institution using the service, to the provider, i.e., the institution hosting the service. Simple services, e.g. for currency conversion or route planning, are common occurrences on the web and are often available for free. More complex offerings are available in the domain of enterprise software, where service architectures allow small- and medium-sized enterprises to use a complex software

* This research was supported by the Deutsche Forschungsgemeinschaft, Berlin-Brandenburg Graduate School in Distributed Information Systems (DFG grant no. GRK 316/2). Y. Manolopoulos and P. Návrat (Eds.): ADBIS 2002, LNCS 2435, pp. 8-22, 2002.  Springer-Verlag Berlin Heidelberg 2002

Trust Is not Enough

9

product even though they do not have the staff or financial resources for a local installation. Network-based services are often marketed under the terms application service provider (ASP) and web services. An ASP is a company that hosts one or more applications and makes them available to customers online. Other common terms for this business model include software leasing and hosted application. While the ASP is often also the author of the software that is for lease, this is not necessarily the case. The software in question can be complex and include a large variety of different subservices. This is demonstrated by the fact that enterprise resource planning (ERP) software is increasingly offered via the ASP model. Technically, most ASPs are based on the exchange of dynamically generated HTML pages via a simple HTTP or HTTPS communication between customer and provider. Well-known examples for the ASP approach include mySAP, the ASP version of SAP’s R/3 ERP system, or Salesforce.com, a provider of services for customer relationship management (CRM) purposes. Web services, on the other hand, display a finer granularity than ASP packages do. Moreover, web services are mainly targeted towards use by other programs, whereas ASP software is more adapted to human-computer interaction via a web browser. In order to be accessible to other software or to software agents, web services usually post a machine-readable description of their functionality and their interfaces. The XML-based Web Service Description Language (WSDL) is increasingly used for this purpose; see http://www.w3.org/TR/wsdl for a detailed documentation. Service descriptions are typically entered into one or more online registries based on an emerging standard called UDDI (Universal Description, Discovery, and Integration, http://www.uddi.org). The self-describing nature of web services is also useful for assembling web services into a service package with enhanced functionalities. While this is already feasible from a technical point of view, there are only a small number of real-world applications that take advantage of this capability. Once a user has located a web service and, if necessary, obtained authorization to use it, the service can be called using a variety of protocols, most commonly the new Simple Object Access Protocol (SOAP, http://www.w3.org/TR/SOAP). A SOAP message is an XML document comprising a SOAP envelope and body. SOAP messages are usually based on a request-response model. In the case of a web service providing stock quotes, for example, the SOAP request may ask for a specific stock quote and the web service responds with a SOAP response embedding the value in question. While the XML-based standards SOAP, WSDL and UDDI provide an efficient infrastructure for web services, one should not underestimate the limitations of these tools with respect to the complexity of the services. Heavy-duty applications such as ERP, B2B collaboration, and workflow management often impose complex transactional and logical constraints on their system environment, which cannot always be captured using simple tools like the ones described above. Special-purpose approaches, such as ebXML (http://www.ebxml.org) or RosettaNet in the e-business domain (http://www.rosettanet.org), are more appropriate for such cases. In the following section, we discuss the general question of privacy and security in online services in some more detail. Section 3 is devoted to trust-based solutions to

10

Claus Boyens and Oliver Günther

the privacy problem, whereas sections 4 and 5 discuss the technical solutions currently available.

2

Privacy and Security in Online Services

Regardless whether one uses a simple web service or a complex software package provided by an ASP, users encounter a fundamental privacy problem. In order to use a service, customers have to furnish the input data to the service provider. This may be done directly, by attaching the data to the service request, or indirectly, by giving the provider access to any relevant files or databases. While the communication can be protected by standard encryption measures (such as SSL), this does not solve the problem that the service provider usually has access to the input data in plaintext form. Even in the simple example of the stock quote service, this implies a certain loss of privacy: by using the service, customers make it known to the service provider that they are interested in a certain stock. A more serious loss of privacy is involved in portfolio management services, including the popular Yahoo service finance.yahoo. com, where tens of thousands of portfolios are stored in a central site. If service architectures are used to provide enterprise-oriented services, such as CRM or ERP applications, customers face the question whether they are willing to forward missioncritical business data to their ASP. Not every potential user of such services may be willing to transfer sensitive personal or business data to an outside party in an unprotected manner. Especially if the service provider is not well known to the customer, this may imply incalculable risks. Simple fraudulence on the part of the service provider may be exceptional but involuntary security lapses are unfortunately not uncommon. Some customers may also face the risk of espionage and blackmailing by vulnerable employees of the service provider. The salary of a well-known executive, for example, or the release date of a long-awaited motion picture may well be data items that are of interest to a great number of people. If they are stored at an ERP service provider, many of the providers’ employees will have access to this data. Even if there is a relationship of trust between customer and service provider, there may be legal stipulations that restrict the data transfer. In most European countries, for example, doctors are allowed to transfer even the most basic patient data to an accounting service only if patients have given their explicit approval. Moreover, customers always have to keep in mind that their service provider may change hands – not an uncommon occurrence especially in the start-up industry. A change of ownership, however, usually implies a change of control over the customers’ data as well. Unless there are specific arrangements to the contrary, the new owners will usually be able to review the data and even sell it to a third party. A recent Amazon press release states, for example: "In the unlikely event that Amazon.com, Inc., or substantially all of its assets are acquired, customer information will of course be one of the transferred assets." The privacy issues become even more complex in a networked environment where web services can communicate freely with each other and with software agents (Ley-

Trust Is not Enough

11

mann et al. 2002). This means concretely that the data made available to some service provider A may be forwarded to another service provider B, because the service run by A deems it useful to avail itself of the services offered by B. A detailed control of which business partners one deals with eventually seems unpractical, if not infeasible in such a world. At the very least it would require the manual or automatic creation of lists of trusted partners. All of this raises the question: Is trust enough? And if that is not the case, what are the technical means for customers to protect their data from their service provider?

3

Trust

So far, the privacy issues associated with online services have either been ignored or resolved on the basis of trust. They have largely been ignored where the data in question is either not particularly sensitive or where the danger of misuse seems small to customers. Hardly anybody, for example, would be concerned about privacy when they ask some web-based service what the weather is like in Berlin right now. Financial information, on the other hand, is usually considered more sensitive. On the other hand, the large majority of Internet users would be willing to trust their bank with their online activities, just as they have trusted their bank back when the transactions were mainly conducted via the local branch. More remarkable, however, is the willingness of users to trust portals like Yahoo with the hosting of their portfolio data. This kind of interaction is purely trust-based – it relies on the implicit knowledge that Yahoo’s business model is partly based on the fact that it treats their customers’ data with considerable regard to privacy (cf. privacy.yahoo.com). On the other hand, the Yahoo data would certainly be available to the Internal Revenue Service in cases where there is sufficient evidence that a Yahoo user is evading taxes. And none of Yahoo’s privacy commitments would hold a priori if they were sold to another company. These are all scenarios that are not particularly unrealistic, while essentially being ignored by the Yahoo user community at large. It is questionable whether this kind of trust-based solution is acceptable for all potential users of such services. In fact, we suspect that many Yahoo users would think twice about using the portfolio management service if there were made more explicitly aware of all potential privacy violations. Trust, on the other hand, is an essential factor when one is doing business with partners. If one can rely on a number of trusted partners, it simplifies procedures and makes an enterprise as a whole more efficient. The question is how to transfer the well-known concept of trust to the Internet and in particular to network-based service architectures. If a customer has to decide whether to trust a service provider, the following issues need to be taken into account: Honesty: A basic premise of a business relationship is the assumption that a business partner is willing to fulfill commitments made in written and possibly also in oral form (even though the latter is usually hard to enforce in legal proceedings). Technical Equipment: Is the service provider’s technical equipment and staff sufficient to fulfill the promises made? Especially smaller service provider may sometimes

12

Claus Boyens and Oliver Günther

make promises in good faith, just to get a customer to sign up, even though the technical infrastructure is not (yet) sufficient to live up to these promises. Technical Qualifications: A related issue concerns the qualifications of the provider’s technical staff. The customer must have trust that the staff is sufficiently knowledgeable in privacy- and security-related matters, such as encryption, firewalls, and database management. Integrity of the Staff: It is not only the technical qualifications that count but also the belief in the ethical integrity of the staff members. In the case of well-known clients, this includes a consideration of the probability of corruption. Trustworthiness of the Provider’s Partners: This is particularly important in the case of web services that may avail themselves of other services run by other providers. If the customer’s data is forwarded by the provider to third parties, this must be made known to customers, so they can apply similar standards for trustworthiness to these third parties. A thorough analysis of all these different issues requires a level of due diligence that is hardly feasible given the time pressures under which such decisions are often taken. As a substitute, potential customers often resort to a more global concept of trustworthiness. Especially large companies that serve as a service provider take advantage of their general reputation to convince customers of their trustworthiness. The same holds for service companies where confidentiality and trustworthiness make up a large part of their nonmonetary capital, such as banks or certified public accountants. On the Internet, this kind of trust in certain institutions has manifested itself in a new type of check box asking “Always trust content from X, Inc.?” that pops up increasingly when one is about to download content from a company’s website. This check box is part of what is called a trust dialog box, a modal security warning that prompts users before software is installed on their computers. A trust dialog box identifies the distributor X of the software component and indicates whether the publisher's authenticity has been verified. The “Always trust ...” check box adds the distributor X to a list of trusted providers. Users thus avoid the trust dialog box during future downloads from X’s web site. This approach could easily be adapted to services. However, it does not prevent adverse third parties to pose as a provider that is widely trusted in order to spread tampered files to a large group of well-believing customers. Another way of replacing individual due diligence is to rely on evaluations of the service provider by other customers. Evaluations collected by the provider itself are less valuable, for obvious reasons, than evaluations collected by an independent agency or marketplace. A well-known application of this principle in the trade with physical goods is the evaluation feature of Ebay (http://www.ebay.com), where customers are encouraged to make their experiences with an Ebay trading partner known to the rest of the customer community. Similar techniques can be applied to the evaluation of services.

Trust Is not Enough

13

Third, there is the possibility to leave the due diligence to an independent agency that evaluates a service provider and, in case of a positive evaluation, certifies the level of privacy users can expect from this provider. Finally, there is what we call the gated community approach, where users restrict themselves to services offered by providers that have been certified to be appropriate for the community they belong to. By transitivity, certified providers are only allowed to use services of certified providers in turn. Examples of such gated communities include company extranets and Internet user communities like AOL.

4

Protection

Whenever consumers access a digital service, they expose themselves to three types of security risks. First, service access must be granted only to authorized users at the appropriate security level, otherwise some users may have access to another user’s data against that will. Usually this is not a technical but an organizational problem concerning database management and local security measures. In many practical situations, especially the latter issue may be problematic. Imagine a patient management system in a hospital. Do all the nurses have different log-ins? Are there different levels of access rights, i.e., different roles for, e.g., the doctors, the head nurse, and the staff nurses? All these questions must be addressed when designing an online service, especially one that involves local management of customer data. Second, confidentiality and integrity must be guaranteed for the data communication between service provider and customers. This is usually the security risk that is easiest to manage. For the TCP/IP protocol stack, there exists an efficient and secure encryption method, the Secure Sockets Layer (SSL), a.k.a. Transport Layer Security (TLS). The basic idea is to use public key infrastructure for secure key exchange and symmetric encryption for fast data transmission. Third, customer data may be subject to attacks by adversaries at the provider’s site. Intruders trying to hack firewalls and other defense mechanisms are just one kind of threads. Other threats include malicious or incompetent system administrators and changes of ownership at the provider’s side. This chapter presents several technical solutions to the privacy problem. We distinguish between hardware-based solutions, such as IBM’s secure coprocessors (Smith and Weingart 1999); database solutions, such as data fragmentation (Hacigumus et al. 2002); and encryption-based solutions that usually employ a variation of the privacy homomorphisms originally proposed by Rivest, Adleman and Dertouzos (1978). 4.1

Secure Coprocessors

One way of protecting sensitive data from the service provider is to keep it in a secure hardware environment that performs the relevant computations but is not accessible to providers once they have installed the service implementation on that secure envi-

14

Claus Boyens and Oliver Günther

ronment. The service-related computations are then performed inside the secure environment in the following way: (1) The input data is delivered to the secure environment. If the data is sensitive, it is transferred in encrypted form using standard public/private key encryption. (2) Hardware inside the secure environment decrypts any encrypted input data and performs the service-related computations. (3) The result is encrypted and shipped to the customer who decrypts it locally. Any time the service provider tries to access the secure environment, any sensitive data will be encrypted or destroyed. Moreover, in order to avoid trojan horse attacks by a tampered service implementation, the secure environment surveys the outgoing communication to make sure that no key information or non-encrypted data leaves the environment. A hardware architecture that comes close to this vision has been marketed by IBM since 1998 under the term secure coprocessor (Smith and Weingart 1999). A secure coprocessor is a computational device that can be trusted to execute software correctly and keep the data confidential even in the case of a physical attack. Its main characteristic is its dynamic and battery-backed RAM that is zeroized in case of tamper. Its services include secure computation of sensitive application parts, storage of key material and provision of modules that accelerate decryption and encryption with common techniques (such as DES, RSA). As the term coprocessor already indicates, it is not designed in order to cope with extensive application requirements but with a few critical processes only. The current version of the IBM 4758 coprocessor (Model 002) includes a 99Mhz 486 CPU and contains 8 MB of secure storage. Current applications include the minting of electronic postage and protection against insider breakins, especially in banks and auction houses. While a step into the right direction, secure coprocessors have not (yet?) been accepted widely by the ASP and web service communities. Main reasons seems to be the implicit performance restrictions, the cost involved and the fact that by using secure coprocessors, one becomes to a certain degree dependent on the supplier of the special-purpose hardware. 4.2

Database Management

Databases play an important role in most privacy-related matters, primarily because they are the system component where the access rights and privileges are encoded. Especially in ASP and web service environments, where different users from different (possibly competing) companies are using the same services on the same servers, it is absolutely essential that their data is stored in such a way that each user sees those and only those data items he is supposed to see. This requires a sophisticated access control system on the part of the database management system and, equally important, a skilled staff on the provider’s site that knows how to use the available tools in the most effective manner. Once again, however, this kind of privacy protection does not help those users that do not trust their service provider. The provider is likely to have database administra-

Trust Is not Enough

15

tor or superuser rights that enable him to access all the data in the database. To protect against misuse by the provider, regardless whether it is due to bad faith or incompetence, requires the sensitive user data to be obscured somehow before it is transferred to the provider. An interesting approach is to fragment the input data, i.e., the customer transfers only a subset of the input data to the service provider. The service provider computes any results or partial results it can obtain, given the data that has been made available. These (partial) results are then sent back to the customer who has to complete the computation locally, using the data that has been kept there for privacy reasons. (Alternatively, the part of the computation to be executed locally could be assigned to a secure coprocessor at the provider’s site.) Approaches along those lines include a software architecture proposed by Asonov (2002), building on Chor et al.’s (1995) concept of private information retrieval. Atallah et al. (2001) and Hacigumus et al. (2002) both suggest system designs that combine fragmentation with encryption, whereas Bobineau et al. (2000) present a concrete architecture in the smartcard context. In statistical databases, variations of the fragmentation approach have been in common use for quite some time; see (Denning 1982) or (Schurig 1999) for overviews. 4.3

Encryption

Encryption for the purpose of protecting communication is standard Internet technology and is supported by a variety of protocols at the network and the transport control layer. Examples include Secure Internet Protocol (IPSec), Secure Socket Layer (SSL), or Pretty Good Privacy (PGP), which is based on the public/private key technology first proposed by Rivest et al. (1978). These kinds of approaches only protect the communication. On the service provider side, the data will be decrypted in order to feed it into the service. If the user does not trust the service provider, encryption may still be of some help. Of course, in this case the provider will not be allowed to simply decrypt the incoming data but will have to work on the encrypted data directly. This imposes some major restrictions on the encryption scheme being used. Following the seminal work of Rivest, Adleman, und Dertouzos (1978) we suggested in Jacobsen et al. (1999) an approach where the input data D is encrypted by the customer before it is transferred to the service provider. In order to do so, the customer uses a transformation (an encryption algorithm) T together with a secret key K to produce the encrypted version of the input data, TK(D). The provider applies a service S to the encrypted data TK (D) – possibly without even knowing that the data is encrypted. The resulting pseudo-solution S(TK (D)) is decrypted using a retransformation UK (which is often, but not always, the inverse of TK) in order to yield the correct result S(D). Fig.1 illustrates this basic idea. A key question is to find appropriate transformations T and U for a given service S. In order to enable the provider to work on the encrypted data, at the very least the data type has to be maintained. The homomorphic encryption functions introduced by Rivest et al., called privacy homomorphisms, fulfill this condition. However, later publications have pointed out several principal limitations of this approach; see, for

16

Claus Boyens and Oliver Günther

example, the work by Ahituv et al. (1987), Brickell and Jacobi (1987), DomingoFerrer (1996a, 1996b, 1997), Sander and Tschudin (1999), and Canny (2001).

User Input Data D ASP:

ASP Transformation TK

Service S

Service S

Solution S(D)

Transformed Input Data TK(D)

Retransformation UK Pseudo-Solution S(TK(D))

Fig. 1. A transformation approach to hide input data from a service provider

We shall discuss these contributions in more detail in the following section. Contrary to the scepticism of Ahituv et al. (1987), however, we still consider privacy homomorphisms as highly useful in many practical applications, in particular in service-based architectures. The key question is what kind of attacks are likely and what level of security is required in these kind of applications. TYPE OF ATTACK No encryption algorithm Ciphertext only

KNOWN TO ATTACKER - Ciphertext to be decoded

- Ciphertext to be decoded - Encryption algorithm Known plaintext - Ciphertext to be decoded - Encryption algorithm - One or more plaintext-ciphertext pairs formed with the secret key Chosen plaintext - Ciphertext to be decoded - Encryption algorithm - Plaintext message chosen by attacker, together with its corresponding ciphertext generated with the secret key Chosen cipher- - Ciphertext to be decoded text - Encryption algorithm - Purported ciphertext chosen by attacker, together with its corresponding decrypted plaintext generated with the secret key Chosen text - Ciphertext to be decoded - Encryption algorithm - Plaintext message chosen by attacker, together with its corresponding ciphertext generated with the secret key - Purported ciphertext chosen by attacker, together with its corresponding decrypted plaintext generated with the secret key Fig. 2. Different classes of cryptographic attacks (based on Stallings 1999, p.25)

As depicted in Fig. 2, cryptographic attacks can be classified based on the information a possible attacker has obtained (Stallings 1999, p.25). Stallings assumes that the

Trust Is not Enough

17

attacker knows at least the encryption algorithm even though that will not always be the case. We have therefore added a sixth category to his hierarchy of attacks, where the attacker only sees the ciphertext to be decoded without knowing the encryption algorithm that has been used. The classical example for this most difficult scenario would be the decryption of military radio messages where the attacker has no knowledge of the actual content of the message nor of the encryption method. In the next scenario, the ciphertext-only attack, the attacker sees the encrypted data and knows which encryption algorithm has been used. The next lower level of difficulty, called known-plaintext attack, gives the attacker one or more random plaintext-ciphertext pairs to work with. Next come the chosen-plaintext and chosen-ciphertext attacks: The chosen-plaintext attack provides the attacker with the encryption of a plaintext of his choice whereas the chosen-ciphertext attack allows him to decrypt a ciphertext he has previously chosen. The chosen-text attack is a combination of both, where the attacker may decrypt and encrypt any text with the secret key. If we apply this terminology to the context of ASPs and web services, the plaintext corresponds to the input data D provided by the user and the ciphertext corresponds to the encrypted data TK(D). The potential attacker (e.g., the service provider or one of its employees) most likely knows the encryption algorithm T that is being applied. He does not know the secret key K, nor is he likely to have any plaintext-ciphertext pairs to work with. In this scenario, it thus suffices that T resists a ciphertext-only attack. In the worst case, the attacker has knowledge of one or more random plaintextciphertext pairs, possibly because he has some background knowledge about the customer’s operations. For example, the attacker may know the name of the customer’s CEO and be able to identify the encrypted version of the CEO’s name in the ciphertext because the organizational structure is still visible. In this case, the attacker has found a (random) plaintext-ciphertext pair, which is likely to help him to crack the code. If ASP or web service customers want to brace himself against this kind of infraction, they have to resort to the more powerful class of encryption algorithms that also withstand known-plaintext attacks. We are thus looking for an encryption algorithm T that maintains the type of the input data and is resistant to at least ciphertext-only attacks, possibly also to knownplaintext attacks. In the following section we shall investigate various possible encryption algorithms and evaluate their properties against this benchmark.

5

Privacy Homomorphisms

5.1

Definition and History

Rivest et al. (1978) introduce privacy homomorphisms as “encryption functions that permit encrypted data to be operated on without preliminary decryption of the operands”. As an example, they present an RSA-related encryption scheme TK that is resistant to chosen-ciphertext attacks and has the additional property that the multiplicative product of two encrypted numbers is equal to the encryption of the corresponding cleartext product: TK (d 1 ) ⋅ TK (d 2 ) = Tk (d1 ⋅ d 2 ) . If one considers “multiplication” as a simple kind of service, TK thus guarantees perfect privacy because the customer

18

Claus Boyens and Oliver Günther

may use the service without revealing neither the factors nor the result to the service provider. Performing addition on encrypted data turned out to be a more complicated issue. Ahituv et al. (1987) show that no additive privacy homomorphism is able to withstand a chosen-plaintext attack. Brickell and Yacobi (1988) managed to break the four additive encryption schemes proposed by Rivest et al. (1978) with known-plaintext and ciphertext-only attacks. In turn, they present an R-additive encryption scheme that permits the addition of up to R numbers and that is resistant against ciphertext-only attacks. In 1996, Domingo-Ferrer finally presented an additive and multiplicative privacy homomorphism (Domingo-Ferrer 1996). His algorithm preserves total order (“≤”) but not the equality predicate. It is secure against known-plaintext attacks, which is the strongest security possible for an algorithm that preserves total order. Two years later, Domingo-Ferrer and Herrera-Joancomartí (1998) presented a PH supporting all field operations (addition, subtraction, multiplication, division) on two encrypted numbers. It is secure against ciphertext-only attacks but not against known-plaintext attacks (which is the strongest kind of attack that can be resisted by an additive PH). Fig. 3 summarizes these results. Note that, while they may look discouraging from a theory point of view, they are not necessarily an argument against using PHs in ASP and web service environments! As noted above, an encryption algorithm that is secure against ciphertext-only attacks is sufficient in most practical applications – not least because it transfers the ultimate responsibility from the service provider to the customer. If a plaintext-ciphertext pair has been known to the attacker, it will be difficult for the customer to deny responsibility for the break-in. AUTHORS Rivest et al. (1978) Brickell and Yacobi (1988)

SERVICE S

S ( d 1 , d 2 ) = d1 × d1 R

S (d1 ,..., d R ) = ∑ d i

SECURE AGAINST REMARKS chosen-ciphertext - based on RSA attack - preserves equality ciphertext-only attack

i =1

DomingoFerrer (1996) DomingoFerrer and HerreraJoanconmartí (1998)

S ( d 1 , d 2 ) = d 1 + d1 S ( d 1 , d 2 ) = d1 × d1 S ( d 1 , d 2 ) = d 1 + d1 S ( d 1 , d 2 ) = d 1 − d1 S ( d 1 , d 2 ) = d1 × d1 S ( d 1 , d 2 ) = d1 ÷ d 1

known-plaintext attack ciphertext-only attack

- preserves total order but not equality - does not preserve total order

Fig. 3. Privacy homomorphisms for different services

5.2

An Example

As an example we present the application discussed by Rivest et al. (1978). They describe a loan company deploying a “time-sharing service” (comparable to a modern

Trust Is not Enough

19

ASP) to store their encrypted customer data. The desired calculations on the encrypted data include (1) the average on outstanding loans, (2) the number of loans exceeding a purported amount and (3) the total sum of payments due in a given period of time. Using privacy homomorphisms, these figures can be computed in a secure manner as follows. (1) Average of outstanding loans: n

S (d1 ,..., d n ) =

∑d i =1

n

i

,

d i outstanding loans

Here, the R-additive homomorphism proposed by Brickell and Yacobi can be used to compute the sum if R ≥ n . The result must be transferred to the customer and where either the decrypted result is divided by n directly, or the result and the number n are encrypted with the proposed field homomorphism and the division is performed by the service provider. (2) Number of loans exceeding a certain amount C: n 1,di ≥C S (d1 ,..., d n ) = ∑ xi , xi =  i =1 0 , d i < C

,

d i outstanding loans

This requires the comparison of encrypted data against a constant. As Rivest et al. have shown, the encryption scheme in question will not be able to withstand even a ciphertext-only attack. Consequently, the comparisons to C need to be performed on plaintext data. Assuming that no information shall be revealed to the service provider, this can only be done at the customer’s site or with the help of a secure coprocessor. (3) Total sum of payments due in a given period of time P: n d  d  S ( 11 ,...,  1n ) = ∑ d 1i ⋅ d 2i i =1  d 21   d 2 n 

d 1i outstanding loan i in Period P, d 2 i interest rate for loan i.

Each pair  d 11  is enciphered with the RSA homomorphism, the multiplication is d   21  done at the server site and the decrypted result is encrypted with the R-additive homomorphism at the customer site. All products are then sent to the server who computes the corresponding sum and returns the result to the customer. There is no single privacy homomorphism that securely copes with all arithmetic operations at a time. The service needs to be split into various steps in order to combine the capabilities of the existing encryption schemes. There are two possibilities: First, the service provider sends the partial results back to the customer who either finishes the operation herself or reencrypts it using the appropriate encryption scheme and sends it back for further processing. This obviously translates into additional communication and handling charges. Second, one could assign the sensitive operations (such as the comparison against a constant, or a sorting operation) to a secure

20

Claus Boyens and Oliver Günther

coprocessor at the server site. This, however, may imply a decrease in performance because of the inherent processing restrictions of the coprocessor. 5.3

Implementation

If one accepts the basic idea that privacy homomorphisms are a useful approach to solving privacy problems in service architectures, one should think about ways to implement this approach. Public key infrastructures (PKIs) are based on the idea to divide encryption algorithm and secret key. In a service architecture context, this would mean that the service provider would offer its customers a special software module that contains all the necessary encryption tools customized for the service in question. Secret key generation, management and employment is then up to the customer. Depending on the service provided, an ASP could also offer a browser plug-in that is signed by a trusted third party. Invoked by special HTML tags, this plug-in would employ the privacy homomorphisms necessary to encrypt and decrypt the data corresponding to the different services. The user or, in the case of enterprise solutions, the system administrator could create and manage the secret keys, which remain unknown to the ASP. Given the fact that browsers often have bulky interfaces, one could alternatively assign the processing to a proxy server. This seems suitable especially for enterprise solutions, where all web traffic needs to pass through proxy servers anyway. Again, the system administrator would be responsible for the management of secret keys. Both approaches assume the existence of locally installed browsers. In the future, this may not always be necessary, as new techniques like the remote GUI only require the presentation layer to be processed at the customer site. With the data management completely shifted to the central facility, transforming sensitive information must then take place at the (untrusted) server location. The deployment of hardware support seems to be inevitable in this case.

6

Conclusions

The purpose of this paper is twofold. On the one hand, we would like to convey to the reader that the current state of security and privacy in net-based services is unsatisfactory. At this point, most services run on the basis of the trust. While there may often be good reasons to trust the service provider, this may not always be the case. Sabotage, insider break-ins, technical incompetence, or changes of ownership may occur even with service providers that are well-known and have a spotless reputation. Customers who make sensitive data available to a provider should always consider to employ technical means of protection as well. Depending on the sensitivity of the data, it may well be worth their money and their effort. On the other hand, we wanted to show that privacy homomorphisms, despite their inherent weaknesses, are an interesting approach to solve some of the problems described in this paper in a reasonably reliable manner. It is true that PHs are often not resistant to attacks where the intruder has access to the encryption algorithm and a

Trust Is not Enough

21

number of cleartext-ciphertext pairs (i.e., “known-plaintext” attacks and easier variations). On the other hand, this may be irrelevant in many service environments because it is the responsibility of the customer not to give access to such information to any potential intruder. PHs allow service providers to market their services while being able to assure any potential customers the complete confidentiality of their transactions – provided they apply appropriate care in handling their encryption algorithms and associated parameters. But this should not be asking too much. Once a service provider has accepted the basic notion of privacy homomorphisms, the question is how to find appropriate homomorphisms for a given collection of services. Some services may be altogether incompatible with the PH approach because the original data is required. Other services may introduce some computational complexity that makes it hard to use non-trivial encryptions. Consider, for example, a service that calculates income taxes. Given the nonlinear nature of most income tax tables, the encryption could not be based on linear transformations. Special-purpose encryption techniques will often be necessary. Our future work will focus on a variety of implementation issues. How can we quickly identify possible PHs for a given service S? How can PHs be implemented efficiently using browser plug-ins or proxy extensions? And how can PHs be combined efficiently with other approaches that share the same goals, such as secure coprocessors or data fragmentation?

References 1. Ahituv, N., Lapid, Y., and Neumann, S., Processing Encrypted Data, Communications of the ACM, Vol.20, pp.777-780, 1987. 2. Asonov, D. Private Information Retrieval. An Overview and Current Trends. In Proceedings ECDPvA Workshop, Informatik 2001, Vienna, Austria, September 2001. 3. Atallah, M.J., Pantazopoulos, K.N., Rice, J.R., and Spafford, E.H., Secure Outsourcing of Scientific Computations, Advances in Computers, 54, Chapter 6, pp. 215-272, July 2001. 4. Bobineau, C., Bouganim, L., Pucheral, P., and Valduriez, P., PicoDBMS: Scaling down Database Techniques for the Smartcard. In Proceedings 26th VLDB Conference, Cairo, Egypt, 2000. 5. Brickell, E., and Yacobi, Y., On Privacy Homomorphisms, in: D. Chaum and W.L. Price, eds., Advances in Cryptology-Eurocrypt ’87, Springer, Berlin, 1988. 6. Canny, J., Collaborative Filtering with Privacy. http://www.millennium.berkeley.edu/retreat/files/Sharing0601.ppt, 2001. 7. Chor, B., Goldreich, O., Kushilevitz, E., and Sudan, M.: Private Information Retrieval. In Proceedings 36th IEEE FOCS Conference, pp.41-50, New York, 1995 8. Denning, D., Cryptography and Data Security, Addison-Wesley, 1982. 9. Domingo-Ferrer J., A New Privacy Homomorphism and Applications, Information Processing Letters, Vol.60, No.5, pp.277-282, December 1996. 10. Domingo-Ferrer, J., Multi-application Smart Cards and Encrypted Data Processing, Future Generation Computer Systems, Vol.13, pp.65-74, June 1997. 11. Domingo-Ferrer, J., and Herrera-Joanconmartí, A Privacy Homomorphism Allowing Field Operations on Encrypted Data, Jornades de Matemàtica Discreta i Algorísmica, Barcelona 1998.

22

Claus Boyens and Oliver Günther

12. Hacigumus, H., Mehrotra, S., Iyer, B., and Li, C., Executing SQL over Encrypted Data in the Database Service Provider Model, In Proceedings ACM SIGMOD Conference, June 2002. 13. Jacobsen, H.-A., G. Riessen, and Günther, O., MMM - Middleware for Method Management on the WWW, In Proceedings WWW8 Conference, 1999. 14. Leymann, F., Roller, D., and Schmidt, M.-T., Web services and Business Process Management. IBM Systems Journal, Vol.41, No.2, 2002. 15. Rivest, R., Adleman, L., and Dertouzos, M.L., On Data Banks and Privacy Homomorphisms. In Foundations of Secure Computations. Academic Press, New York, 1978. 16. Rivest, R., Shamir, A., and Adleman, L. A Method for Obtaining Digital Signatures and Public-key Cryptosystems. Communications of the ACM, Vol.21, No.2, 1978. 17. Sander, T., and Tschudin, C., On Software Protection Via Function Hiding, In Proceedings 2nd Workshop on Information Hiding, LNCS Springer, 1998. 18. Schurig, S., Geheimhaltung in Statistischen Datenbanken, Shaker, 1998. 19. Smith, S.W., and Weingart, S.H., Building a High-Performance, Programmable Secure Coprocessor. In Computer Networks, Special Issue on Computer Network Security, No.31, pp. 831-860, 1999. 20. Stallings, W., Cryptography and Network Security: Principles and Practice. Prentice-Hall, 1999.

Infrastructure for Information Spaces Hans-J¨org Schek, Heiko Schuldt, Christoph Schuler, and Roger Weber Database Research Group, Institute of Information Systems Swiss Federal Institute of Technology (ETH) ETH Zentrum, CH–8092 Zurich, Switzerland {schek,schuldt,schuler,weber}@inf.ethz.ch

Abstract. In the past, we talked about single information systems. In the future, we expect an ever increasing number of information systems and data sources, reaching from traditional databases and large document collections, information sources contained in web pages, down to information systems in mobile devices as they will occur in a pervasive computing environment. Therefore not only the immense amount of information demands new thoughts but also the number of diﬀerent information sources. Essentially, their coordination poses a great challenge for the development of future tools that will be suitable to access, process, and maintain information. We talk about the continuous, “inﬁnite” information, shortly called the “information space”. Information in this space is distributed, heterogeneous and undergoes continuous changes. So, the infrastructure for information spaces must provide convenient tools for accessing information, for developing applications for analyzing, mining, classifying, and processing information, and for transactional processes that ensure consistent propagation of information changes and simultaneous invocations of several (web) services within a transactional workﬂow. As far as possible, the infrastructure should avoid global components. Rather, a peer-to-peer decentralized coordination middleware must be provided that has some self-conﬁguration and adaptation features. In this paper we will elaborate some of the aspects related to process-based coordination within the information space and report on research from our hyperdatabase research framework and from experiences in ETHWorld, an ETH wide project that will establish the ETH information space. Nevertheless, this paper is rather visionary and is intended to stimulate new research in this wide area.

1

Introduction

Until recently, information processing was dominated by single, well-delimited albeit possibly distributed information systems. In the future, we see a strong reinforcement of the current trend from these single information systems towards an ever increasing number of information systems and data sources, reaching from traditional databases and large document collections, information sources contained in web pages, down to information systems in mobile devices and embedded information in mobile “smart” objects as they will occur in a pervasive computing environment. As a consequence of this development, the amount of Y. Manolopoulos and P. N´ avrat (Eds.): ADBIS 2002, LNCS 2435, pp. 23–36, 2002. c Springer-Verlag Berlin Heidelberg 2002

24

Hans-J¨ org Schek et al.

stored information is exploding. However, not only the immense amount of information demands new thoughts but also the number of diﬀerent information sources and their coordination poses a great challenge for the development of future tools that will be suitable to access, process, and maintain information. The reason being is that information will not be static but rather continuously updated, extended, processed and/or reﬁned. We talk about the continuous, “inﬁnite” information, shortly called the “information space”. Information in this space is distributed, heterogeneous and undergoes continuous changes. For all these reasons, the infrastructure for information spaces must provide convenient tools for accessing information via sophisticated search facilities and for combining or integrating search results from diﬀerent sources (1), for developing applications for analyzing, mining, classifying and processing information (2), and for transactional processes that ensure consistent propagation of information changes and simultaneous invocations of several (web) services within a transactional workﬂow (3). The latter requirement is needed in order to automatically keep track of dependencies within the information space. Dependencies might exist when data is replicated at several sources or when derived data, e.g., in the form of sophisticated index structures, has to be maintained. As far as possible the infrastructure should avoid global components and thus also potential bottlenecks. Rather, a peer-to-peer decentralized coordination middleware must be provided that has some self-conﬁguration and adaptation features to various applications and their load characteristics (4). This urgent requirement stems from the fact that the information space is not at all static but rather might change its character over time. Hence, an infrastructure that supports aspects like a high degree of ﬂexibility and self-conﬁguration can dynamically adapt to changes in the environment without explicit intervention and/or tuning. In this paper we will elaborate some of the aspects in area (3) and (4) and report on research from our hyperdatabase research framework [16] and from experiences in ETHWorld [4,17], an ETH wide project that will establish the ETH virtual campus, a large-scale information space. In particular, we will present the prototype system OSIRIS (Open Service Infrastructure for Reliable and Integrated process Support) and we will show how the advanced concepts identiﬁed for the management and organization of large-scale information spaces are realized in a peer-to-peer environment and by applying sophisticated publish/subscribe techniques. Nevertheless, this paper is rather visionary and is intended to stimulate new research in this wide area. The remainder of this paper is organized as follows: In Section 2, we introduce the notion of information space and highlight the problems associated with the management of data and services out of which the information space is built. Moreover, we discuss the basic foundations and prerequisites of the architecture we propose for managing large-scale information spaces. In Section 3, we present OSIRIS, our hyperdatabase prototype system in detail, and we introduce the ETHWorld project in which OSIRIS is currently being used. Section 4 discusses related work and Section 5 concludes.

Infrastructure for Information Spaces

2

25

Organizing and Maintaining Information Spaces: Problems and Challenges

In this section, we introduce the notion of information space and discuss the challenges for an infrastructure for information space maintenance and management and show how such an infrastructure can be implemented. 2.1

Information Spaces

Information spaces are collections of semantically related data and services. We diﬀerentiate between three abstractions of information spaces: Firstly, the global information space which comprises the universe of all documents and services that can be accessed, mainly via the Internet but also from other sources like databases, etc. Secondly, community information spaces (or, synonymously, intranet information spaces) which are deﬁned by the data and services of a closed, coherent part of the global information space. Thirdly, personal information spaces which are individual views on a community information space tailored to the needs of a user in his/her current context. Usually, the set of documents, data, and services of an information space is distributed and heterogeneous. In addition, information spaces are dynamic. This means that updates and deletions of data and documents as well as the new generation of documents have to be considered. To this end, the peers hosting information provide appropriate services by which these operations are encapsulated and made available to the users. Since documents within the information space are usually not independent, the local invocation of such services has several side-eﬀects and therefore also aﬀects other documents without the user being aware of these dependencies. Such dependencies occur, e.g. when data is replicated and indexed via search engines within the information space or when certain documents are derived from others. The task of information space maintenance is to keep track of these dependencies and to automatically re-establish consistency within the information space whenever necessary. A mayor diﬀerence between the global information space and community information spaces is that the latter are manageable in the sense that all existing dependencies are known such that they can be tracked. For this reason, we focus on the management of community information spaces; however, the basic mechanisms we propose for information space maintenance can also be applied to the global information space. An example of a community information space is ETHWorld, the virtual campus of ETH that we will describe in more detail below. As a further and more general example for a community information space, consider the information space of a large-scale international company. The documents, out of which the company’s information space is built, are product descriptions and technical documentation in some proprietary formats stored in ﬁle systems, product catalogs and inventory control data residing in databases, information within the company’s intranet and on some information available over the Internet, as well as information stored in e-mail archives, etc. In addition, information is replicated at several places, and local caches exist, e.g., to support mobile devices.

26

Hans-J¨ org Schek et al.

However, information may be added, changed, deleted by diﬀerent individuals at diﬀerent subsidiaries and no global control on the consistency of the overall community information space is possible. For instance, the update of some product description in a product database must be propagated to the replicas of all subsidiaries as well as to the information on the company web server. Obviously, such dependencies within the information space have to be tracked and consistency between original and replicated and/or derived data has to be guaranteed. Therefore, the infrastructure of the information space has to support the execution of coordination processes. These are applications which are deﬁned on top of the existing services, i.e., which use these services as building blocks. The goal of these coordination processes is to free the users of the information space from dealing with dependencies. Rather, appropriate processes have to be executed automatically after services are invoked so as to maintain the overall information space. The prerequisite for this is that i.) the necessary processes are properly deﬁned and ii.) they are linked to the appropriate event necessitating coordination eﬀorts. In particular, the latter requirement demands that service invocations can be monitored. Such services which seamlessly support the task of information space maintenance will be called cooperative services. Conversely, non-cooperative services are those that do not allow for automating coordination processes. Consequently, a basic requirement for sophisticated information space maintenance and management is that all services having side-eﬀects within the information space are cooperative ones. Processes combining and virtually integrating single services can themselves be considered as high-level services within the information space. 2.2

Infrastructure for Information Spaces: Hyperdatabases

How must a proper infrastructure for information spaces look like? Clearly, we may think of a monolithic database that stores all information and that provides all the necessary services for all clients. However, this would not match the requirements for information spaces, mainly for two reasons. First, information is distributed by deﬁnition. It would not be feasible to force all information providers to store their data at a single place. Second, a monolithic system would not scale to the increasing demands of an information space. Recent advances in networking, storage, and computing power demonstrate that we are able to communicate and store vast amounts of data, but a single machine’s power cannot catch up with the increased demands of larger data sets and larger communication rates. A useful metric for the rate of technological changes is the average period during which speed or capacity doubles or halves in price. For storage and networking, this period is around 12 and 9 months, respectively. The one for computing power lies at around 18 months. Obviously, computing power is falling behind. Consequently, a monolithic database solution for an information space is not appropriate, but we still want its beneﬁts, yet at a higher level of abstraction. As a developer of such an information space, we want something similar to data independence but for services. We want transactional guarantees but for processes (workﬂows) over distributed components using existing services. We want recovery and fault tolerance but at the process level. In a

Infrastructure for Information Spaces

27

Fig. 1. The Hyperdatabase (HDB) is a Layer on top of Networking nutshell, we would like to have a database over components and services, and a database over databases: a Hyperdatabase (HDB) [16,17]. Essentially, organizing an information space means providing a coherent, integrated, and consistent view on a vast amount of information that is produced, stored, and even updated by distributed components within a networked environment. Due to the physical distribution of information sources and services, a core functionality of an HDB for the information space is coordination. This means that the HDB has to keep track of changes, to continuously propagate these changes, and to derive and update particular views of the overall (community) information space. As a consequence, HDB functionality is distributed over the participating components and located as additional layer on top of the network layer (see Figure 1). Following the analogy of transactional processes being the HDB abstraction of database transactions, a HDB as coordinator has to run such transactional processes and to guarantee their correct termination. In addition, the HDB oﬀers a simple way to add and administer specialized components (cf. Figure 2). The services provided by these components can be combined to form application-aware processes with speciﬁc execution guarantees (recovery, exception handling, alternative executions, consistency, concurrency control, etc.). Commonly, such processes are triggered by events like insertion, update, or connect/disconnect. Computationally expensive tasks may easily be scaled out to a cluster of workstations (computational services). The traditional approach to implementing systems providing functionality similar to the functionality required from an HDB consists of decentralized storage and service components and a centralized control component (coordinator,

28

Hans-J¨ org Schek et al.

Fig. 2. Architecture of a Community Information Space

workﬂow or process engine). When enriching such a process engine with transactional semantics (e.g., [3,12,18]), the result will be a system that provides all the required execution guarantees and thus will seamlessly support the task of information space maintenance. However, the central control component disallows for scaling the system to the demands and sizes of an information space as all steps of all processes are routed through this (bottleneck) component. As insinuated above, computational power does not advance as quickly as storage and networking technologies. Consequently, the maximum number of clients, processes, and information providers will be limited by the computational capabilities of the central control component. Another problem arises from the lack of resource management. Computational expensive processes demand for an infrastructure as provided by grids. A grid infrastructure pools complex tasks which are assigned to resources whenever they signal ”idle state” or ”ﬁnished last task”. But like in workﬂow systems, a grid relies on a central component which assigns tasks to is subsidiary components. On the other hand, this central component holds enough global metadata on the tasks and resources to ensure an optimal assignment of tasks to resources and achieve a maximum throughput of tasks per time unit. But still, communication mainly incurs between the central component and the decentralized resources. Peer-to-peer systems have recently attracted large interest from researches, companies and Internet users. The ﬁrst successful application of peer-to-peer systems, ﬁle sharing, demonstrated the potential of an entirely decentralized architecture. Protocols like the ones of Gnutella [6] or FastTrack [5] require no central control or repository component but still provide clients with suﬃciently accurate information about the state of their speciﬁc information space. Moreover, since communication takes place without any central component involved, peer-to-peer systems easily scale up to any size. Clearly, peer-to-peer communi-

Infrastructure for Information Spaces

29

cation is a demand for an HDB that must scale to the sizes of large information spaces. However, unlike in ﬁle sharing applications, an HDB requires a more or less consistent, complete, and accurate view of the overall (community) information space. While clients of a ﬁle sharing system will tolerate missing entries in their results, this clearly is not the case for applications and processes in the information space for which overall consistency is of primary concern. Peer-to-peer communication enables unlimited scalability, but to ensure correctness and completeness, an HDB must rely on accurate global metadata. But peers should not have to access global metadata on a centralized component whenever they want to perform an action. Rather, the peers should be provided with replicas of the portion of global metadata they need to fulﬁll their tasks. Clearly, this demands for a sophisticated replication scheme within the HDB. Although replication appears to be expensive at ﬁrst glance, the characteristics of an information space and recent advances in networking technologies enable such a solution. For instance, if a peer must invoke a service s, it must know which providers of s currently exist. Hence, the peer is given a replica of the list of providers of s from the global metadata. In particular, we assume that the number of processes to be executed and therefore the number of service invocations considerably exceeds the number of changes of global metadata such that metadata replication pays oﬀ. In addition, the freshness of replicated data may in certain cases be relaxed. For instance, a peer can live with a slightly outdated list as long as it can ﬁnd at least one service provider. Summarizing the previous discussion, an implementation of an HDB should encompass the following ﬁve essential concepts (in brackets, we have listed the areas from which we have borrowed the respective concepts): – Sophisticated process management enriched by execution guarantees (transactional workﬂow or process management). – Resource management to enable optimal execution of computational expensive tasks (grid computing). – Peer-to-peer communication at the process level. No central component shall be involved in the navigation of processes or routing of process steps (peerto-peer systems). – Accurate global metadata to provide a consistent and complete view (transactional process management and grid computing). – Decentralized replication of metadata with freshness guarantees.

3

Managing the Information Space of ETHWorld

In the following, we describe the OSIRIS system developed at the database group of ETH. Moreover, we highlight the problems associated with maintaining the information space of a virtual campus, an environment where the OSIRIS system is currently being applied.

30

Hans-J¨ org Schek et al.

Fig. 3. The OSIRIS Architecture 3.1

The OSIRIS System

When implementing an HDB infrastructure for the management and maintenance of an information space, support for the various requirements we have identiﬁed in the previous section is vital for its success. To this end, the OSIRIS system (Open Service Infrastructure for Reliable and Integrated process Support) [19] provides basic support for executing processes with dedicated execution guarantees but also accounts for the inherent distribution that can be found within the information space and the need for a highly scalable system. The latter requirement is stemming from the fact that services may be dynamically added to or revoked from the system such that the infrastructure should provide certain self-adaptation features [21]. In a nutshell, OSIRIS consists of two kinds of components: i.) a small HDB layer added to each component providing a service within the community information space (these components will be shortly denoted as ’service providers’) and ii.) a canonical set of basic repositories managing global metadata describing the system conﬁguration and the applications (processes) to be executed within the information space (c.f. Figure 3). Following the core characteristics of an HDB, the OSIRIS system provides support for process execution in a peer-to-peer style. To this end, metadata on the processes and on the system conﬁguration is replicated. This allows each HDB layer of a service provider to locally drive the execution of a process, i.e., to invoke the next process step after a local service invocation has terminated. As a consequence, no centralized control is involved during process execution.

Infrastructure for Information Spaces

31

The ﬁrst step in providing support for the maintenance of an information space is that the processes to be executed in the information space have to be properly speciﬁed. This is usually done by the administrator of the community information space and is supported in OSIRIS by the graphical workﬂow process modeling tool IvyFrame [9]. After speciﬁcation, the process information is stored in a global process repository (PR). Since processes are the applications that OSIRIS executes within the information space, the process repository can be considered as a kind of software archive. Similarly, another global component (subscription list, SL) manages the diﬀerent service providers of the system, i.e., the system conﬁguration. To this end, each service provider has to register its service(s). Both PR and SL are then used as sources for metadata distribution. After a provider p registers its service si with SL, it receives in return the parts of all process models in which si appears. In particular, these parts contain pairs of subsequent services (si , sk ), i.e., specify the services that have to be immediately invoked after si has terminated. In addition, service provider p will also receive the list of all providers oﬀering service sk which has to be invoked after si . Process execution then takes place only at the level of the HDB layers of the respective service providers: when a process is started, the ﬁrst service is invoked. After its termination, the HDB layer of the provider directly invokes the subsequent service, thereby transferring control to its HDB layer. These mechanisms are stepwise applied until the successful termination of a process. Essentially, OSIRIS uses publish/subscribe techniques to execute processes. Conceptually, each HDB layer generates (publishes) an event after the termination of a service si . This event is converted to an invocation of the subsequent service sk of the current process and transferred to the HDB layer of a service provider which has previously registered a service sk , i.e., has made a subscription of the appropriate event indicating that sk has to be executed. But instead of matching publication and subscriptions by a centralized publish/subscribe broker, this is done locally by the HDB layer. To this end, the replicated metadata allows for a distributed and decentralized implementation of publish/subscribe functionality. Each local HDB layer is equipped with a publish/subscribe broker such that events can be handled locally, based on the replicas of PR and SL. However, a question that immediately arises is how this replicas are kept consistent. For this problem, again publish/subscribe techniques are applied. When the initial subscription of a service provider for service si is done, it is not only registered as provider in SL. Implicitly and transparent to the provider, a second subscription is generated by the system. This subscription declares interest on all metadata of the system associated with this service. Initially, it corresponds to the copy of the metadata on process models and subscribers. However, since the second, implicit subscription is held until the provider revokes its service, it guarantees that each change in the metadata of PR and SL relevant to this particular provider is updated. This is essentially necessary in the following cases: i.) new processes are deﬁned in which si is to be executed, ii.) processes are updated such that the subsequent service after si changes or disappears, iii.) new providers register which oﬀer a service sk that is to be invoked after si in some process, or iv.) service providers revoke their service. In all cases, changes are submitted to the central repositories and generate an event there. This event is

32

Hans-J¨ org Schek et al.

3.Im plicitSubscription on Changes ofSL

3''.Im plicitSubscription on Changes ofLR

✓ ✓ ✓ ✓

✓ ✓ ✓

3'. Im plicitSubscription on Changes ofPR Subscription List(SL)

2.M anage Subscription Load Repository (LR) 4.Distribute SL M etadata

Process Repository (PR) 1.Subscribe (Register Service Sk)

Service Si

HDB Layer

4''.Distribute LR M etadata

Services Sk

N ew Service Sk

HDB Layer

5.Update SL M etadata

4'.Distribute PR M etadata

Existing Service Si

Fig. 4. DIPS Metadata Replication Management

then, due to the second, implicit subscription, transferred to the respective HDB layers of service providers which then update their local replica. The repeated application of publish/subscribe techniques is termed DIPS (Doubled Implicit Publish/Subscribe). The DIPS-based metadata replication management is depicted in Figure 4. The explicit subscription of a service is illustrated by solid arcs, the implicit second subscription by dashed arcs, and the metadata distribution to existing services by dotted arcs. When the local HDB layer has to process the event indicating that a local service si has terminated, it has to choose one concrete service provider among the local replica containing the list of providers having registered for the subsequent service sk . In order to allow for sophisticated load balancing within the community information space, the local replicas not only contain metadata on processes and service providers but also on the (approximated) load of the latter. Hence, the local publish/subscribe engine within the HDB layer is able to choose the provider with the lowest current load. The distribution of metadata on the load of a provider is again done by publish/subscribe techniques. The initial, explicit subscription does not only generate an implicit subscription on changes of PR and SL but also on their loads. These loads are, similarly to PR and SL globally maintained by the load repository, LR (see Figure 4). However, in contrast to the replicas of metadata of PR and SL that have to be kept consistent, load information may only be an approximation of the actual load of the provider. To this end, not each minor change of the load of a provider is published via an appropriate event but only signiﬁcant changes exceeding a

Infrastructure for Information Spaces

33

pre-deﬁned threshold. This information is then made available to all local HDB layers for which the appropriate provider is of interest. In addition to the basic DIPS support for distributing process information, system conﬁguration (registered providers), and load information, OSIRIS provides dedicated transactional execution guarantees by following the ideas of transactional process management [18]. Essentially, this includes a notion of atomicity that is more general than the traditional “all-or-nothing” semantics and guarantees that exactly one out of several alternative executions that are speciﬁed within a process is correctly eﬀected. Finally, a last task to be solved is that processes are automatically started whenever coordination eﬀorts are required in the information space. Each HDB layer of a component oﬀering services which have side-eﬀects such that their invocation necessitates coordination activities has to monitor the invocation of these services. Whenever an invocation is detected, the appropriate event is published such that the ﬁrst step of the respective process needed to enforce consistency is started (in the OSIRIS peer-to-peer way as presented above). Yet, a basic requirement is that each of these services necessitating coordination processes are cooperative ones. 3.2

The ETHWorld Virtual Campus

A concrete application of the OSIRIS HDB infrastructure is in the context of coordinating multimedia information components in the ETHWorld project [4,17]. ETHWorld was established by ETH Z¨ urich to create a virtual campus where students, assistants, professors, researches inside and outside ETH can meet, discuss, exchange information, or work together. A virtual campus, as an example of a large-scale community information space, consists of various documents distributed over a large number of peers. A particular sub-project of the ETHWorld initiative addresses multimedia similarity search with focus on image retrieval and relevance feedback. The goal is to allow for the interactive exploration of the community information space of the virtual campus. To this end, we have built the ISIS system (Interactive SImilarity Search) which provides eﬃcient and eﬀective search methods [8]. Its goals are to i.) identify and build eﬀective content descriptors for various document types, to ii.) develop eﬃcient search methods that allow for complex similarity retrieval [20], and to iii.) build easy-to-use and powerful relevance feedback methods to support query formulation. Since information may be added at any place in the information space but should be accessible by the ISIS search engine as soon as possible (without the delay known from search engines in the Internet), ISIS requires support from OSIRIS with respect to coordination eﬀorts. As a concrete example, the OSIRIS infrastructure has to monitor local insertions of new documents (e.g., in some image database maintained at the ETH library) and to automatically start the execution of a coordination process by publishing its start event. Within this process, a well-deﬁned sequence of steps is executed; each step corresponds to a service invocation (e.g., for extracting color and shape features and for term extraction from text). These features are required to ﬁnally maintain the index

34

Hans-J¨ org Schek et al.

Fig. 5. OSIRIS: Distributed Process Support Infrastructure in ETHWorld allowing for sophisticated search techniques within the information space. Hence, OSIRIS is the infrastructure that, under the cover, provides users with quality of service guarantees for the information she/he wants to access (both in terms of the users of ISIS being served with up-to-date data and in terms of the users of the ETHWorld community information space which do not have to explicitly care about coordination eﬀorts). In Figure 5, the OSIRIS infrastructure for the InsertDocument process is depicted: process execution is driven by the HDB layers of the individual service providers (outer circle) while meta information required for process execution is collected by the global repositories (within the circle). Replication management from the global repositories to the service providers of the outer circle is done using DIPS techniques.

4

Related Work

The dynamic character of the information space necessitates the management of metadata on the services of diﬀerent providers. Our approach which uses a global subscription list component allows the infrastructure to dynamically choose a suitable service instance at process execution time. This allows the system to execute processes in a dynamic way. Approaches dealing with similar paradigms are eFlow [2] and CrossFlow [7]. Existing service description directories like the UDDI Repository [1] could be used to discover external, non-cooperative service providers. To ﬁnd services matching a complex service deﬁnition, additional eﬀort has to be taken. The ISEE [13] system shows how e–service constraints can be used to match suitable service instances. In medical information systems, even

Infrastructure for Information Spaces

35

instances of long–running patient treatment processes have to be continuously updated to the most recent process template deﬁnition so as to provide up-todate treatment knowledge. Therefore, systems from this ﬁeld have to deal with an additional type of dynamic behavior. Running processes have to be migrated to newer deﬁnitions. Systems like HematoWork [14] and ADEPTﬂex [15] address these aspects. Such mechanisms are however orthogonal to OSIRIS and could be seamlessly integrated to additionally enable this kind of applications. OSIRIS provides the guarantee of automated update propagation between autonomous data sources (and even application systems) in the information space. Processes are used to convert data formats and semantics from the source to the target system. The set of services used to deﬁne such update processes provide the functionality needed. Similar conversion ﬂows are used to deﬁne “XML Pipelines” [22], or “Infopipes” [11]. The OSIRIS System uses publish/subscribe techniques both for replication management of system metadata and for process navigation. The approach presented in [10] shows how replication management can be implemented in an eﬃcient way. Using this rule matching algorithm, a large amount of clients can be served which accurate information.

5

Conclusions

In this paper, we have discussed the various requirements for an infrastructure aiming at maintaining and managing community information spaces. The most important task is to guarantee consistency and correctness within the information space by executing appropriate coordination processes whenever necessary. The core of the infrastructure is formed by a hyperdatabase (HDB) which allows for the seamless combination of existing services into processes. Furthermore, we have presented the OSIRIS system, an HDB implementation, which accounts for all these challenging requirements. In OSIRIS, process execution takes place in a peer-to-peer way. OSIRIS distributes replicas of global metadata at each peer in a way that is transparent to the users of the information space. This is realized by applying publish/subscribe techniques for both service providers of the system and for the global metadata repositories. Finally, we have introduced the ETHWorld project aiming at providing the ETH virtual campus. In here, OSIRIS is used as the underlying infrastructure for the community information space of ETHWorld.

References 1. Ariba, IBM, and Microsoft. UDDI Technical White Paper. http://www.uddi.org. 2. F. Casati, S. Ilnicki, L. Jin, V. Krishnamoorthy, and M. Shan. Adaptive and Dynamic Service Composition in eFlow. In Proceedings CAISE Conference, Stockholm, 2000. 3. Q. Chen and U. Dayal. A Transactional Nested Process Management System. In Proceedings 12th IEEE ICDE Conference, pages 566–573, New Orleans, LO, 1996. 4. ETHWorld – The Virtual Campus of ETH Z¨ urich. http://www.ethworld.ethz.ch.

36

Hans-J¨ org Schek et al.

5. FastTrack – P2P Technology. http://www.fasttrack.nu. 6. Gnutella RFC. http://rfc-gnutella.sourceforge.net. 7. P. Grefen, K. Aberer, H. Ludwig, and Y. Hoﬀner. CrossFlow: Cross–Organizational Workﬂow Management for Service Outsourcing in Dynamic Virtual Enterprises. IEEE Data Engineering Bulletin, 24:52–57, 2001. 8. ISIS – Interactive SImilarity Search. http://www.isis.ethz.ch. 9. IvyTeam. IvyFrame: Process Modeling and Simulation. http://www.ivyteam.com. 10. M. Keidl, A. Kreutz, A. Kemper, and D. Kossmann. A Publish and Subscribe Architecture for Distributed Metadata Management. In Proceedings 18th IEEE ICDE Conference, San Jose, CA, 2002. 11. R. Koster, A. Black, J. Huang, J. Walpole, and C. Pu. Infopipes for Composing Distributed Information Flows. In Proceedings International Workshop on Multimedia Middleware (M3 W 2001), Ottawa, Canada, October 2001. 12. F. Leymann. Supporting Business Transactions via Partial Backward Recovery in Workﬂow Management Systems. In Proceedings BTW’95 Conference, pages 51–70, Dresden, Germany, March 1995. Springer Verlag. 13. J. Meng, S. Su, H. Lam, and A. Helal. Achieving Dynamic Inter-organizational Workﬂow Management by Integrating Business Processes, Events, and Rules. In Proceedings 35th Annual Hawaii International Conference on System Sciences (HICSS 2002), Big Island, Hawaii, January 2002. 14. R. M¨ uller and E. Rahm. Rule-Based Dynamic Modiﬁcation of Workﬂows in a Medical Domain. In Proceedings BTW’99 Conference, pages 429–448, Freiburg, Germany, March 1999. Springer Verlag. 15. M. Reichert and P. Dadam. ADEPTﬂex — Supporting Dynamic Changes of Workﬂows without Losing Control. Journal of Intelligent Information Systems, 10(2):93–129, March 1998. 16. H.-J. Schek, K. B¨ ohm, T. Grabs, U. R¨ ohm, H. Schuldt, and R. Weber. Hyperdatabases. In Proceedings 1st International Conference on Web Information Systems Engineering (WISE 2000), pages 14–23, Hong Kong, China, June 2000. 17. H.-J. Schek, H. Schuldt, and R. Weber. Hyperdatabases – Infrastructure for the Information Space. In Proceedings 6th IFIP 2.6 Working Conference on Visual Database Systems (VDB 2002), Brisbane, Australia, May 2002. 18. H. Schuldt, G. Alonso, C. Beeri, and H.-J. Schek. Atomicity and Isolation for Transactional Processes. ACM Transactions on Database Systems, 27(1), March 2002. 19. C. Schuler, H. Schuldt, and H.-J. Schek. Supporting Reliable Transactional Business Processes by Publish/Subscribe Techniques. In Proceedings 2nd International Workshop on Technologies for E–Services (TES 2001), Rome, Italy, September 2001. 20. R. Weber, H.-J. Schek, and S. Blott. A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces. In Proceedings 24th VLDB Conference, New York, NY, 1998. 21. I. Wladawsky-Berger. Advancing the Internet into the Future. Talk at the International Conference Shaping the Information Society in Europe 2002, April 2002. http://www-5.ibm.com/de/entwicklung/academia/index.html. 22. XML pipeline Deﬁnition Language. http://www.w3.org/TR/xml-pipeline.

An Axiomatic Approach to Defining Approximation Measures for Functional Dependencies Chris Giannella Computer Science Department, Indiana University, Bloomington, IN 47405, USA [email protected]

Abstract. We consider the problem of deﬁning an approximation measure for functional dependencies (FDs). An approximation measure for X → Y is a function mapping relation instances, r, to non-negative real numbers. The number to which r is mapped, intuitively, describes the “degree” to which the dependency X → Y holds in r. We develop a set of axioms for measures based on the following intuition. The degree to which X → Y is approximate in r is the degree to which r determines a function from ΠX (r) to ΠY (r). The axioms apply to measures that depend only on frequencies (i.e. the frequency of x ∈ ΠX (r) is the number of tuples containing x divided by the total number of tuples). We prove that a unique measure satisﬁes these axioms (up to a constant multiple), namely, the information dependency measure of [5]. We do not argue that this result implies that the only reasonable, frequency-based, measure is the information dependency measure. However, if an application designer decides to use another measure, then the designer must accept that the measure used violates one of the axioms.

1

Introduction

In the last ten years there has been growing interest in the problem of discovering functional dependencies (FDs) that hold in a given relational instance (table), r [11,12,13,15,17,19,22]. The primary motivation for this work lies in knowledge discovery in databases (KDD). FDs represent potentially novel and interesting patterns existent in r. Their discovery provides valuable knowledge of the “structure” of r. Unlike FD researchers in the 1970s, we are interested in FDs that hold in a given instance of the schema rather than FDs that are pre-deﬁned to hold in any instance of the schema. The FDs of our interest are instance based as they represent structural properties that a given instance of the schema satisﬁes rather than properties that any instance of the schema must satisfy to be considered valid. As such our primary motivation is not in database design, rather, in KDD. In some cases an FD may “almost” hold (e.g. [11] first name → gender). These are approximate functional dependencies (AFDs). Approximate functional

Work supported by National Science Foundation grant IIS-0082407.

Y. Manolopoulos and P. N´ avrat (Eds.): ADBIS 2002, LNCS 2435, pp. 37–50, 2002. c Springer-Verlag Berlin Heidelberg 2002

38

Chris Giannella

dependencies also represent interesting patterns contained in r. The discovery of AFDs can be valuable to domain experts. For example, paraphrasing from [11] page 100: an AFD in a table of chemical compounds relating various structural attributes to carcinogenicity could provide valuable hints to biochemists for potential causes of cancer (but cannot be taken as a fact without further analysis by domain specialists). Before algorithms for discovering AFDs can be developed, an approximation measure must be deﬁned. Choosing the “best” measure is a diﬃcult task, because the decision is partly subjective; intuition developed from background knowledge must be taken into account. As such, eﬀorts made in deﬁning a measure must isolate properties that the measure must satisfy. Assumptions from intuition are taken into account in the deﬁnition of these properties. Based on these properties, a measure is derived. In this paper, we develop an approximation measure following the above methodology. The intuition from which properties are developed is the following. Given attribute sets X and Y , the degree to which X → Y is approximate in r is the degree to which r determines a function from ΠX (r) to ΠY (r).1 By “determines” we mean that each tuple in r is to be regarded as a data point that either supports or denies a mapping choice x ∈ ΠX (r) → y ∈ ΠY (r). We prove that a unique measure (up to a constant multiple) satisﬁes these properties (regarded as axioms). The primary purpose of this paper is to develop a deeper understanding of the concept of FD approximation degree. The paper is laid out as follows. Section 2 describes related work, emphasizing other approximation measure proposals from the literature. Section 3 gives a very general deﬁnition of approximation measures, namely, functions that map relation instances to non-negative real numbers. Based on the fundamental concept of genericity in relational database theory, this deﬁnition is reﬁned so that only attribute value counts are taken into account. Section 4 develops a set of axioms based on the intuition described earlier. It is proven that a unique measure (up to a constant multiple) satisﬁes these axioms. Finally, section 5 gives conclusions.

2

Related Work

This section describes approximation measures that have already been developed in the literature and other related works. The ﬁrst subsection describes previous measures developed based on information theoretic principals. The second subsection describes previous measures developed based on other principals. The third subsection describes other related works. 2.1

Information Theoretic Approaches

Nambiar [18], Malvestuto [16], and Lee [14] independently introduce the idea of applying the Shannon entropy function to measure the “information content” 1

We assume that the reader is familiar with the basic notation for relational database theory, for a review, see [21].

An Axiomatic Approach to Deﬁning Approximation Measures

39

of the data in the columns of an attribute set. They extend the idea to develop a measure that, given an instance r, quantiﬁes the amount of information the columns of X contain about Y . This measure is the conditional entropy between the probability distributions associated with X and Y through frequencies (i.e. x ∈ ΠX (r) is assigned probability equal to the number of tuples containing x divided by the total number of tuples). All three authors show that this measure is non-negative, and is zero exactly when an X → Y is an FD. As such an approximation measure is developed. However, the main thrust of [18], [16], and [14] was to introduce the idea of characterizing the information content using entropy and not to explore the problem of deﬁning an approximation measure for FDs. Cavallo and Pittarelli [3] also develop an approximation measure. Their measure is the conditional entropy normalized to lie between zero and one. However, the main thrust of [3] was to generalize the relational model to allow for probabilistic instances. They do not explore the problem of deﬁning an approximation measure for FDs. Finally, Dalkilic and Robertson [5] (also [4]) independently discover the idea of applying the Shannon entropy function to measure “information content”. They use the conditional entropy to quantify the amount of information the columns of X contain about the columns of Y in r. They call this the information dependency measure. While they make explicit mention of the idea of using the information dependency as an FD approximation measure, they do not explore the idea further. Interestingly, the authors of [3,14], and [18] make little or no mention of the potential applicability to knowledge discovery of entropy as a measure of information content. This is probably due to the fact that, at the time of their writing (all before 1988), KDD had not yet received the attention that it does today. Dalkilic [4], however, does make explicit mention of the potential applicability to KDD. 2.2

Other Approaches

Piatetsky-Shapiro [20] introduce the concept of a probabilistic data dependency, denoted pdep(X, Y ), and use it to develop an approximation measure. Given two arbitrarily chosen tuples, pdep(X, Y ) is the probability that the tuples agree on Y given that they agree on X. The approximation measure developed is the same as the τ measure of Goodman and Kruskal [9]. Piatetsky-Shapiro develops a method of examining the signiﬁcance of probabilistic data dependencies and, as such, touches on the issue of how the measure should be deﬁned (see his section 3.2). However, he does not examine the fundamental assumptions upon which the pdep measure is based. Kivinen and Manilla [13] take a non-probabilistic approach to developing an approximation measure. They propose three measures, all of which are based on counting the number of tuples or pairs of tuples that cause the dependency to break. For example, one of the measures proposed is denoted g3 and is deﬁned as min{|s| : r − s X → Y }/|r|.

40

Chris Giannella

The main thrust of [13], however, is to develop an eﬃcient algorithm that ﬁnds, with high probability, all FDs that hold in a given instance. The problem of how to best deﬁne an approximation measure is not considered. Huhtala et al. [11] develop an algorithm, TANE, for ﬁnding all AFDs whose g3 value is no greater than some user speciﬁed value. Again, though, they do not consider the problem of how to best deﬁne an approximation measure. 2.3

Other Related Works

De Bra and Paredaens [6] describe a method for horizontally decomposing a relation instance with respect to an AFD. The result is two instances; on one instance the AFD holds perfectly and the other represents exceptions. The authors go on to develop a normal form with respect to their horizontal decomposition method. They do not consider the problem of deﬁning an AFD measure. Demetrovics, Katona, and Miklos [7] study a weaker form of functional dependencies that they call partial dependencies. They go on to examine a number of combinatorial properties of partial dependencies. They also investigate some questions about how certain related combinatorial structures can be realized in a database with minimal numbers of tuples or columns. They do not consider the problem of deﬁning an AFD measure. Demetrovics et al. [8] study the average case properties of keys and functional dependencies in random databases. They show that the worst-case exponential properties of keys and functional dependencies (e.g. the number of minimal keys can be exponential in the number of attributes) is unlikely. They do not consider the problem of deﬁning an AFD measure.

3

FD Approximation Measures: General Definition

In this section we deﬁne FD approximation measures in very general terms in order to lay the framework for our axiomatic discussion later. Let S be some relation schema and X, Y be non-empty subsets of S. Let D be some ﬁxed, countably inﬁnite set that serves as a universal domain. Let I(S, D) be the set of all relation instances2 over S whose active domain is contained in D. An approximation measure for X → Y over I(S, D) is a function from I(S, D) to R≥0 (the non-negative reals). Intuitively, the number to which an instance, r, is mapped determines the degree to which X → Y holds in r. In the remainder of this paper, for simplicity, we write “approximation measure” to mean “approximation measure for X → Y over I(S, D)”. 3.1

Genericity

The concept of genericity in relational database theory asserts that the behavior of queries should be invariant on the values in the database up to equality [1]. 2

For our purposes a relation instance could be a bag instead of a set.

An Axiomatic Approach to Deﬁning Approximation Measures

41

In our setting, genericity implies that the actual values from D used in r are irrelevant for approximation measures provided that equality is respected. More formally put: given any permutation ρ : D → D, any approximation measure should map r and ρ(r) to the same value.3 Therefore, the only information of relevance needed from r is the attribute value counts. Given x ∈ ΠX (r), and y ∈ ΠY (r), let c(x) denote the number of tuples, t ∈ r, such that t[X] = x (the count of x); let c(y) denote the count of y; let c(x, y) denote the number of tuples where t[X] = x and t[Y ] = y. 3.2

Intuition

The degree to which X → Y is approximate in r is the degree to which r determines a function from ΠX (r) to ΠY (r). Consider the two instances as seen in ﬁgure 3.2. The one on the left has n tuples (n ≥ 2) while the one on the right has two tuples. Our hypothesis says that the degree to which A → B is approximate in each of these instances is the degree to which each determines a function from {1} to {1, 2}. We have a choice between 1 → 1 and 1 → 2. If we were to randomly draw a tuple from the instance on the right, there would be an equal likelihood of drawing (1, 1, .) or (1, 2, .). Hence the instance does not provide any information to decrease our uncertainty in choosing between 1 → 1 and 1 → 2. On the other hand, if we were to randomly draw a tuple from the and the instance on the left, the likelihood of drawing (1, 1, .) would be n−1 n likelihood of (1, 2, .) would be n1 . Hence, if n is large, then the instance on the left decreases our uncertainty substantially. The tuples of the two instances could be thought of as data points supplying the choice between 1 → 1 or 1 → 2 (e.g. tuple (1, 1, 1) supplies choice 1 → 1). In the next section we unpack our intuition further by developing a set axioms.

AB 1 1 1 1 .. .. . .

C 1 2 .. .

ABC 1 1 1 1 2 2

1 1 n-1 1 2 n Fig. 1. Two instances over schema A, B, C

4

Axioms

This section is divided into three subsections. In the ﬁrst, the boundary case where |ΠX (r)| = 1 is considered and axioms are described that formalize our intuitions. In the second, the general case is considered and one additional axiom is introduced. We close the section with a theorem stating that any approximation measure that satisﬁes the axioms must be equivalent to the information dependency measure [5] up to a constant multiple. 3

ρ(r) denotes the instance obtained by replacing each value a in r by ρ(a).

42

Chris Giannella

4.1

The |ΠX (r)| = 1 Case

The only information of relevance needed from r is the vector [c(y): y ∈ ΠY (r)].4 , or equivalently, the frequency vector: [f (y): y ∈ ΠY (r)], where f (y) = c(y) |r| . We may think of an approximation measure as a function mapping ﬁnite, nonzero, rational probability distributions into R≥0 . Let Q(0, 1] denote the set of rational numbers in (0, 1]. Given integer q ≥ 1, let Fq = {[f1 , . . . , fq ] ∈ Q(0, 1]q : q fi = 1}. Formally, we may think of an approximation measure as a function i=1 ∞ from q=1 Fq to R≥0 . Equivalently, an approximation measure may be thought of as a family, Γ = {Γq |q = 1, 2, . . .}, of functions Γq : Fq → R≥0 . Example 1. Recall the approximation measure g3 described in Subsection 2.2. It can be seen that: g3 (r) = 1 −

x∈ΠX (r)

max{c(x, y) : y ∈ ΠY (r)} . |r|

In the case of |ΠX (r)| = 1, we have g3 (r) = max{f (y) : y ∈ ΠY (r)}. So, g3 can be represented as the family functions Γ g3 , where Γqg3 ([f1 , . . ., fq ]) = max{fj }. Consider the instance as seen on the left in figure 3.2; call this instance s. We 1 n−1 1 n−1 have g3 (s) = Γ2g3 ([ n−1 n , n ]) = max{ n , n } = n . We now develop our axioms. The ﬁrst axiom, called the Zero Axiom, is based on the observation that when there is only one Y value, X → Y holds. In this case, we require that the measure returns zero; formally put: Γ1 ([1]) = 0. The second axiom, called the SymABC metry Axiom, is based on the observa1 1 1 tion that the order in which the fre1 1 2 quencies appear should not aﬀect the ABC 1 1 3 measure. Formally stated: for all q ≥ 1, 1 1 1 1 2 4 and all 1 ≤ i ≤ j ≤ q, we have Γq ( [. . ., 1 1 2 1 2 5 fi , . . ., fj , . . .]) = Γq ( [. . ., fj , . . ., fi , 1 2 3 1 2 6 . . .]). 1 2 4 1 3 7 The third axiom concerns the be1 3 8 havior of Γ on uniform frequency dis1 3 9 tributions. Consider the two instances as seen in ﬁgure 4. The B column frequency distributions are both uniform. Fig. 2. Two instance over schema The instance on the left has frequen- A, B, C cies 12 , 12 while the instance on the right has frequencies 13 , 13 , 13 . 4

The counts for the values of ΠX (r) are not needed, because, we are assuming for the moment that |ΠX (r)| = 1. In the next subsection, we drop this assumption and the counts for the values of ΠX (r) become important.

An Axiomatic Approach to Deﬁning Approximation Measures

43

The degree to which A → B is approximate in the instance on the left (right) is the degree to which the instance determines a function from {1} to {1, 2} ({1} to {1, 2, 3}). In the instance on the left, we have a choice between 1 → 1 and 1 → 2. In the instance on the right, we have a choice between 1 → 1, 1 → 2, and 1 → 3. If we were to randomly draw a tuple from each instance, in either case, each B value would have an equal likelihood of being drawn. Hence, neither instance decreases our uncertainty of making a mapping choice. However, the instance on the left has fewer mapping choices than the instance on the right (1 → 1, 2 vs. 1 → 1, 2, 3). Therefore, A → B is closer to an FD in the instance on the left than in the instance on the right. Since we assumed that an approximation measure maps an instance to zero when the FD holds, then a measure should map the instance on the left to a number no larger than the instance on the right. Formalizing this intuition we have: for all q ≥ q ≥ 2, Γq ( [ q1 , . . ., q1 ]) ≥ Γq ( [ 1q , . . ., 1q ]). This is called the Monotonicity Axiom. For the fourth axiom, denote the single X value of r as x and denote the Y values as y1 , . . . , yq (q ≥ 3). The degree to which X → Y is approximate in r is the degree of uncertainty we have in making the mapping choice x → y1 , . . ., yq . Let us group together the last two choices as G = {yq−1 , yq }. The mapping choice can be broken into two steps: i. choose between y1 , . . . , yq−2 , G and ii. choose between elements of G if G was chosen ﬁrst. The uncertainty in making the ﬁnal mapping choice is then the sum of the uncertainties of the choice in each of these steps. Consider step i. The uncertainty of making this choice is Γq−1 ( [f (y1 ), . . ., f (yq−2 ), f (yq−1 ) + f (yq )]). Consider step ii. If y1 , . . ., yq−2 were chosen in step i., then step ii. is not necessary (equivalently, step ii. has zero uncertainty). If G was chosen in step i., then an element must be chosen from G in step ii. The f (y ) f (yq−1 ) uncertainty of making this choice is Γ2 ( [ f (yq−1 q−1 )+f (yq ) , f (yq−1 )+f (yq ) ]). However, this choice is made with probability (f (yq−1 ) + f (yq )). Hence the uncertainty of f (y ) f (yq−1 ) making the choice in step ii) is (f (yq−1 ) + f (yq ))Γ2 ( [ f (yq−1 q−1 )+f (yq ) , f (yq−1 )f (yq ) ]). Our fourth axiom, called the Grouping Axiom, is: for q ≥ 3, Γq (f1 , . . ., fq ) = fq−1 fq−1 Γq−1 (f1 , . . ., fq−2 , fq−1 + fq ) + (fq−1 + fq ) Γ2 ( fq−1 +fq , fq−1 +fq ). 4.2

The General Case

We now drop the assumption that |ΠX (r)| = 1. Consider the instance, s, as seen in ﬁgure 4.2. The degree to which A → B is approximate in s is determined by the uncertainty in making the mapping choice for each A value, namely, 1 → 1, 2 and 2 → 1, 3, 4. The choice made for the A value, 1, should not inﬂuence the choice for 2 and vice-versa. Hence, the approximation measure on s should be determined from the measure on s1 := σA=1 (s) and s2 := σA=2 (s). Each of these falls into the |Π| = 1 case. However, there are ﬁve tuples with A value 1 and only three with A value 2. So, intuitively, the measure on s1 should contribute more to the total measure on s than the measure on s2 . Indeed, ﬁve-eighths of the tuples in s contribute to making the choice 1 → 1, 2 while only three-eights

44

Chris Giannella

contribute to making the choice 2 → 1, 3, 4. Hence, we assume that the measure on s is the weighted sum of the measures on s1 and s2 , namely, 58 (Measure on s1 ) + 38 (Measure on s2 ). Put in more general terms, the approxiABC mation measure for X → Y in r should be 1 1 1 the weighted sum of the measures for each 1 1 2 rx , x ∈ ΠX (r). Before we can state our ﬁ1 1 3 nal axiom, we need to generalize the nota1 2 4 tion from the |Π| = 1 case. In the |Π| = 1 1 2 5 case, Γq was deﬁned on frequency vectors, 2 1 6 [f1 , . . . , fq ]. However, with the |Π| = 1 as2 3 7 sumption dropped, we need a relative fre2 4 8 quency vector for each x ∈ ΠX (r). Given y ∈ ΠY (r), let f (y|x) denote the relative frequency of y with respect to x: f (y|x) = Fig. 3. Instance, s, over schema c(x,y) c(x) . The relative frequency vector associ- A, B, C ated with x is [f (y|x)): y ∈ ΠY (σX=x (r))]. Notice, Y values that do not appear in any tuple with x are omitted from the relative frequency vector. Moreover, we also need the frequency vector for the X values, [f (x): x ∈ ΠY (r)]. Let ΠX (r) = {x1 , . . . , xp } and |ΠY (σX=xi (r))| = qi . Γq must be generalized to operate on the X frequency vector, [f (x1 ), . . ., f (xp )], and the relative frequency vectors for Y associated with each X value, [f (y|xi ) : y ∈ ΠY (σX=xi (r))]. The next set of deﬁnitions makes precise the declaration of Γ . Given integers p, q1 , . . . , qp ≥ 1, let Q(0, 1]p,q1 ,...,qp denote Q(0, 1]p × (×pi=1 Q(0, 1]qi ). Let Fp,q p ], [f1|1 , . . ., fq1 |1 ], · · · , [f1|p , . . ., fqp |p ]) ∈ p = {([f1 , . . ., f 1q,...,q p i Q(0, 1]p,q1 ,...,qp : j=1 fj|i = fi and i=1 fi = 1}. An approximation measure is a family, Γ = {Γp,q1 ,...,qp : p, q1 , . . ., qp = 1, 2, . . .}, of functions Γp,q1 ,...,qp : Fp,q1 ,...,qp → R≥0 . Our ﬁnal axiom, called the Sum Axiom, is: for all p ≥ 2 and q1 , . . . , qp ≥ 1, Γp,q1 ,...,qp ( [f1 , . . ., fp ], [f1|1 , . . ., fq1 |1 ], · · · , [f1|p , . . ., fqp |p ]) = pi=1 fi Γqi ( [f1|i , . . ., fqi |i ]). FD Approximation Axioms 1. Zero. Γ1 ([1]) = 0. 2. Symmetry. For all 1 ≤ q, 1 ≤ i ≤ j ≤ q, Γq ([. . ., fi , . . ., fj , . . .]) = Γq ([. . ., fj , . . ., fi , . . .]). 3. Monotonicity. For all q ≥ q ≥ 1, Γq ([ q1 ,. . ., q1 ]) ≥ Γq ([ 1q ,. . ., 1q ]). 4. Grouping. For all q ≥ 3, Γq ([f1 , . . ., fq ]) = Γq−1 ([f1 , . . ., fq−2 , fq−1 + fq ])+ fq f q−1 (fq−1 + fq ) Γ2 ([ fq−1 +fq , fq−1 +fq ]). 5. Sum. For all p ≥ 2 and q1 , . . . , qp ≥ 1, Γp,q1 ,...,qp ( [f1 , . . ., fp ], [f1|1 , . . . , fq1 |1 ], · · · , [f1|p , . . . , fqp |p ]) = pi=1 fi Γ1,qi ( [f1|i ,. . ., fqi |i ]).

An Axiomatic Approach to Deﬁning Approximation Measures

45

We arrive at our main result. Theorem 1. Assume Γ satisfies the FD Approximation Axioms, then )], [f (y|x1 ): y ∈ ΠY (σX=x1 (r))], · · · , [f (y|xp ): y ∈ Γp,q1 ,...,qp ( [f (x1 ), . . ., f (xp ΠY (σX=xp (r))]) equals −c x∈ΠX (r) f (x) y∈ΠY (σX=x (r)) f (y|x)log2 (f (y|x)) where c = Γ2 ([ 12 , 12 ]) (c is non-negative a constant). The information dependency measure of [5] (written HX→Y ) is deﬁned as − x∈ΠX (r) f (x) y∈ΠY (σX=x (r)) f (y|x)log(f (y|x)). Theorem 1 shows that if Γ satisﬁes the FD Approximation Axioms, then Γ is equivalent to the cHX→Y (r) for c a non-negative constant. To prove the theorem, we start by proving the result for the case of |ΠX (r)| = 1. Namely, we prove the following proposition (the general result follows by the Sum axiom). Proposition 1. Assume Γ satisfies the FD Approximation Axioms. For all q ≥ q 1, Γq ([f1 , . . ., fq ]) is of the form −Γ2 ([ 12 , 12 ]) j=1 fj log2 (fj ). The case of q = 1 follows directly from the Zero axiom, so, we now prove the proposition for q ≥ 2. The proof is very similar to that of Theorem 1.2.1 in [2], however, for the sake of being self-contained, we include our proof here. We show four lemmas, the forth of which serves as the base case of a straightforward induction proof of the proposition on q ≥ 2. q Lemma 1. For all q ≥ 2, Γq ([ 1q , . . . , 1q ]) = i=2 qi Γ2 ([ 1i , i−1 i ]). Proof: Apply the Grouping axiom q − 2 times.

Lemma 2. For all q ≥ 2, k ≥ 1, Γqk ([ q1k , . . . , q1k ]) = kΓq ([ 1q , . . . , 1q ]). Proof: Let q ≥ 2. I prove the desired result by induction on k ≥ 1. In the base case (k = 1), the result follows trivially. Consider now the induction case (k ≥ 2). By q − 1 applications of Grouping followed by an application of Symmetry we have Γqk ([

q i 1 1 1 1 1 1 i−1 ]). (1) , . . . , ]) = Γ ([ , , . . . , ]) + Γ2 ([ , k q −(q−1) k k k−1 k k k q q q q q q i i i=2

Repeating the reasoning that arrived at equation (1) q k−1 − 1 more times, we have Γqk ([

1 1 1 1 , . . . , k ]) = Γqk −(qk−1 )(q−1) ([ k−1 , . . . , k−1 ]) + qk q q q q i 1 i−1 k−1 ]) (q ) Γ ([ , k 2 i q i i=2 = Γqk−1 ([

1

q

,..., k−1

1

q

]) + k−1

q 1 i−1 i Γ2 ([ , ]). q i i i=2

46

Chris Giannella

By Lemma 1, we have Γqk ([

1 1 1 1 1 1 , . . . , k ]) = Γqk−1 ([ k−1 , . . . , k−1 ]) + Γq ([ , . . . , ]). qk q q q q q

So, by induction, we have Γqk ([

1 1 1 1 1 1 , . . . , k ]) = (k − 1)Γq ([ , . . . , ]) + Γq ([ , . . . , ]) k q q q q q q 1 1 = kΓq ([ , . . . , ]). q q

Lemma 3. For all q ≥

2, Γq ([ 1q , . . . , 1q ])

=

Γ2 ([ 12 , 12 ])log2 (q).

Proof: Let q ≥ 2. Assume Γq ([ 1q , . . . , 1q ]) = 0. Then by Lemma 1, 0 = q i 1 i−1 1 1 i=2 q Γ2 ([ i , i ]). Since Γ2 is non-negative by deﬁnition, then Γ2 ([ 2 , 2 ]) = 0, so, the desired result holds. Assume henceforth that Γq ([ 1q , . . . , 1q ]) > 0. For any integer r ≥ 1, there exists integer k ≥ 1 such that q k ≤ 2r ≤ q k+1 . Therefore, kr ≤ log12 (q) ≤ k+1 r . Moreover, by the Monotonicity axiom, we have Γqk (. . .) ≤ Γ2r (. . .) ≤ Γqk+1 (. . .). So, by Lemma 2, | ΓΓ2q (...) (...)

−

1 log2 (q) |

≤

k r

≤

Γ2 (...) Γq (...)

≤

k+1 r .

Therefore,

1 r.

Letting r → ∞, we have desired.

Γ2 (...) Γq (...)

=

1 log2 (q) .

So, Γq (. . .) = Γ2 (. . .)log2 (q), as

Lemma 4. For any p ∈ Q(0, 1), Γ2 ([p, 1 − p]) = −Γ2 ([ 12 , 12 ])[plog2 (p) + (1 − p)log2 (1 − p)]. Proof: I shall show for all integers s > r ≥ 1, Γ2 ([ rs , 1 − rs ]) = −Γ2 ([ 12 , 12 ])[ rs log2 ( rs )+ (1 − rs )log2 (1 − rs )]. Let s > r ≥ 1. If s = 2, then the result holds trivially, so, assume s ≥ 3. By r − 1 applications of Grouping, followed by single application of Symmetry, followed by another s − r − 1 applications of Grouping we have s−r r 1 i i 1 r s−r 1 i−1 1 i−1 ]) + Γ2 ([ , ]) + Γ2 ([ , ]) Γs ([ , . . . , ]) = Γ2 ([ , s s s s s i i s i i i=2 i=2 s−r s−r i r s−r 1 i−1 = Γ2 ([ , ]) + Γ2 ([ , ]) s s s i=2 s − r i i r

+

ri 1 i−1 Γ2 ([ , ]). s i=2 r i i

By Lemma 1 and Lemma 3, we have 1 s−r 1 r s−r 1 1 r 1 1 ])+ Γ2 ([ , ])log2 (s−r)+ Γ2 ([ , ])log2 (r). Γs ([ , . . . , ]) = Γ2 ([ , s s s s s 2 2 s 2 2 (2)

An Axiomatic Approach to Deﬁning Approximation Measures

47

By Lemma 3, again, we have 1 1 1 1 Γs ([ , . . . , ]) = Γ2 ([ , ])log2 (s). s s 2 2 From equation (2), it follows that r s−r 1 1 s−r r ]) = −Γ2 ([ , ])[ log2 (s − r) + log2 (r) − log2 (s)] Γ2 ([ , s s 2 2 s s r r s−r log2 (s − r) − = −Γ2 (. . .)[( log2 (r) − log2 (s)) + ( s s s s−r log2 (s))] s r r r r = −Γ2 (. . .)[ log2 ( ) + (1 − )log2 (1 − )]. s s s s Now we prove the proposition by induction on q ≥ 2. The base case of q = 2 follows directly from Lemma 4. Consider now the induction case of q ≥ 3. By Grouping we have Γq ([f1 , . . . , fq ]) = Γq−1 ([f1 , . . . , fq−2 , fq−1 + fq ]) + fq−1 fq (fq−1 + fq )Γ2 ([ , ]). fq−1 + fq fq−1 + fq Now we apply the induction assumption to both terms in the right-hand side and get q−2 1 1 Γq ([f1 , . . . , fq ]) = −Γ2 ([ , ])( fi log2 (fi ) + (fq−1 + fq )log2 (fq−1 + fq )) − 2 2 i=1

fq−1 1 1 fq−1 log2 ( )+ (fq−1 + fq )Γ2 ([ , ])( 2 2 fq−1 + fq fq−1 + fq fq−1 fq−1 log2 ( )) fq−1 + fq fq−1 + fq q−2 1 1 = −Γ2 ([ , ])[ fi log2 (fi ) + fq−1 log2 (fq−1 ) + fq log2 (fq )] 2 2 i=1 q 1 1 = −Γ2 ([ , ]) fi log2 (fi ). 2 2 i=1

Remark: All normalized measures violate one of the axioms since the information dependency measure is unbounded (e.g. g3 does not satisfy the Grouping axiom). We leave to future work modiﬁcation the axioms to account for normalized approximation measures.

48

5

Chris Giannella

Conclusions

The primary purpose of this paper was to develop a deeper understanding of the concept of FD approximation degree. To do so, we developed a set of axioms based on the following intuition. The degree to which X → Y holds in r is the degree to which r determines a function from ΠX (r) to ΠY (r). The axioms apply to measures that depend only on frequencies (i.e. the frequency of x ∈ ΠX (r) is c(x) |r| ). We proved that a unique measure (up to a constant multiple) satisﬁes the axioms, namely, the information dependency measure of [5]. Care must be taken in how the result is interpreted. We do not think it should be interpreted to imply that the information dependency measure is the only reasonable, frequency-based, approximation measure. Other approximation measures may be reasonable as well. In fact, the determination of the “reasonability” of a measure is subjective (like the determination of the “interestingness” of rules in KDD). The way to interpret the result is as follows. It implies that frequency-based measures other than information dependencies must violate one of the FD Approximation Axioms. Hence, if a measure is needed for some application and the designers decide to use another measure, then they must accept that the measure they use violates one of the axioms. There are two primary directions for future work. The ﬁrst is to examine how the axioms can be modiﬁed to account for normalized approximation measures (see the remark at the end of Section 4). The second is based on work done to rank the “interestingness” of generalizations (summaries) of columns in relation instances (see [10] and the citations contained therein). The basic idea of this work is that it is often desirable to generalize a column along pre-speciﬁed taxonomic hierarchies; each generalization forms a diﬀerent data set. There are often an large number of ways that a column can be generalized along a hierarchy (e.g. levels of granularity). Moreover, if there are many available hierarchies, then the number of possible generalizations increases yet further; the number can become quite large. Finding the right generalization can signiﬁcantly improve the gleaning of useful information out of column. A common approach to addressing this problem is to develop a measure of interestingness of generalizations and use it to rank them. Moreover, this approach bases the interestingness of a generalization in terms of the diversity of its frequency distribution. No work has been done in taking an axiomatic approach to deﬁning a diversity measure. Our second direction for future work is to take such an axiomatic approach. In conclusion, we believe that the problem of deﬁning an FD approximation measure is interesting and diﬃcult. Moreover, we feel that the study of approximate FDs more generally is worthy of greater consideration in the KDD community. Acknowledgments The author thanks the following people (in no particular order): Edward Robertson, Dirk Van Gucht, Jan Paredaens, Marc Gyssens, Memo Dalkilic, and Dennis

An Axiomatic Approach to Deﬁning Approximation Measures

49

Groth. The author also thanks a reviewer who pointed out several related works to consider.

References 1. Abiteboul S., Hull R., and Vianu V. Foundations of Database Systems. AddisonWesley, Reading, Mass., 1995. 2. Ash R. Information Theory. Interscience Publishers, John Wiley and Sons, New York, 1965. 3. Cavallo R. and Pittarelli M. The Theory of Probabilistic Databases. In Proceedings 13th International Conference on Very Large Databases (VLDB), pages 71–81, 1987. 4. Dalkilic M. Establishing the Foundations of Data Mining. PhD thesis, Indiana University, Bloomington, IN 47404, May 2000. 5. Dalkilic M. and Robertson E. Information Dependencies. In Proceedings 19th ACM SIGMOD-SIGACT-SIGART Symposium on Principals of Database Systems (PODS), pages 245–253, 2000. 6. De Bra P. and Paredaens J. An Algorithm for Horizontal Decompositions. Information Processing Letters, 17:91–95, 1983. 7. Demetrovics J., Katona G.O.H., and Miklos D. Partial Dependencies in Relational Databases and Their Realization. Discrete Applied Mathematics, 40:127–138, 1992. 8. Demetrovics J., Katona G.O.H., Niklosb D., Seleznjevc O., and Thalheimd B. Asymptotic Properties of Keys and Functional Dependencies in Random Databases. Theoretical Computer Science, 40(2):151–166, 1998. 9. Goodman L. and Kruskal W. Measures of Associations for Cross Classiﬁcations. Journal of the American Statistical Association, 49:732–764, 1954. 10. Hilderman R. and Hamilton H. Evaluation of Interestingness Measures for Ranking Discovered Knowledge. In Lecture Notes in Computer Science 2035 (Proceedings Fifth Pacific-Asian Conference on Knowledge Discovery and Data Mining (PAKDD 2001)), pages 247–259, 2001. 11. Huhtala Y., K¨ arkk¨ ainen J., Porkka P., and Toivonen H. TANE: An Eﬃcient Algorithm for Discovering Functional and Approximate Dependencies. The Computer Journal, 42(2):100–111, 1999. 12. Kantola M., Mannila H., R¨ aih¨ a K., and Siirtola H. Discovering Functional and Inclusion Dependencies in Relational Databases. International Journal of Intelligent Systems, 7:591–607, 1992. 13. Kivinen J., Mannila H. Approximate Inference of Functional Dependencies from Relations. Theoretical Computer Science, 149:129–149, 1995. 14. Lee T. An Information-Theoretic Analysis of Relational Databases - Part I: Data Dependencies and Information Metric. IEEE Transactions on Software Engineering, SE-13(10):1049–1061, 1987. 15. Lopes S., Petit J., and Lakhal L. Eﬃcient Discovery of Functional Dependencies and Armstrong Relations. In Lecture Notes in Computer Science 1777 (Proceedings 7th International Conference on Extending Database Technology (EDBT)), pages 350–364, 2000. 16. Malvestuto F. Statistical Treatment of the Information Content of a Database. Information Systems, 11(3):211–223, 1986. 17. Mannila H. and R¨ aih¨ a K. Dependency Inference. In Proceedings 13th International Conference on Very Large Databases (VLDB), pages 155–158, 1987.

50

Chris Giannella

18. Nambiar K. K. Some Analytic Tools for the Design of Relational Database Systems. In Proceedings 6th International Conference on Very Large Databases (VLDB), pages 417–428, 1980. 19. Novelli N. and Cicchetti R. Functional and Embedded Dependency Inference: a Data Mining Point of View. Information Systems, 26:477–506, 2001. 20. Piatatsky-Shapiro G. Probabilistic Data Dependencies. In Proceedings ML-92 Workshop on Machine Discovery, Aberdeen, UK, pages 11–17, 1992. 21. Ramakrishnan R., Gehrke J. Database Management Systems Second Edition. McGraw Hill Co., New York, 2000. 22. Wyss C., Giannella C., and Robertson E. FastFDs: A Heuristic-Driven, DepthFirst Algorithm for Mining Functional Dependencies from Relation Instances. In Lecture Notes in Computer Science 2114 (Proceedings 3rd International Conference on Data Warehousing and Knowledge Discovery (DaWaK)), pages 101–110, 2001.

Intelligent Support for Information Retrieval in the WWW Environment Robert Koval and Pavol Návrat Slovak University of Technology in Bratislava Department of Computer Science and Engineering Ilkovičova 3, SK-812 19 Bratislava, Slovakia [email protected]

Abstract. The main goal of this research was to investigate means of intelligent support for retrieval of web documents. We have proposed the architecture of the web tool system - Trillian, which discovers the interests of users without their interaction and uses them for autonomous searching of related web content. Discovered pages are suggested to the user. The discovery of user interests is based on analysis of documents that users had visited in the past. We have shown that clustering is a feasible technique for extraction of interests from web documents. We consider the proposed architecture to be quite promising and suitable for future extensions.

1. Introduction The World Wide Web (web) has become the biggest source of information for many people. However, many surveys among web users show that one of the biggest problems for them is to find the information they are looking for. The goal of our work is to design a system capable of discovering user’s topics of interest, his or her (we shall use the masculine form for short in the rest of the paper) on-line behaviour, and his browsing patterns, and to use this information to assist him while he is searching for information on the web. Web tools can be classified in many ways. Cheung, Kao, and Lee have proposed one such classification in [2]. They classify web tools in 5 levels (0-4), from a regular browser to an intelligent web tool (assistant). A level 4 web tool is expected to be capable of learning the behaviour of users and information sources. We focus our effort on the most advanced kind (level 4) web tool. Our vision of what our intelligent web tool will be able to do can be described by following scenario: The intelligent web tool observes the user’s on-line behaviour, his browsing patterns and favourite places. The web tool works as a personal agent and gathers the data needed to identify the user’s interests. By analysing the visited documents, their order, structure and any other attributes, it discovers the user’s domains of concern. Web tool can locally store documents visited by the user. This yields some useful advantages such as a full text search over visited content, easier information sources behaviour analysis and in a multi-user environment even a basis for advanced custom Y. Manolopoulos and P. Návrat (Eds.): ADBIS 2002, LNCS 2435, pp. 51-64, 2002.  Springer-Verlag Berlin Heidelberg 2002

52

Robert Koval and Pavol Návrat

caching functionality [14] or collaborative browsing [4,13]. When the user’s topics of interest are acquired, the tool starts looking for relevant information on web autonomously. When it finds relevant documents, they can be presented to the user in a form of suggestion and he is able to evaluate the quality of them either by implicit or explicit relevance feedback. This feedback can be thought of as a contribution to the tool’s total knowledge of the user’s profile. Moreover, the tool has to be able to identify the information sources behaviour. The system has to discover regular changes of an information source so that it could inform the user more precisely about content change or even download whole content in advance. To discover the user’s interests on the web, his movements and behaviour have to be monitored so that the knowledge about his profile can be acquired. Software entities called agents can be used to achieve such a functionality. Motivation of this research is to design and evaluate system or architecture able to assist the users in information retrieval and make web experience convenient for them. We want to design a complex web tool, its architecture and implement some of the designed modules as prototypes to evaluate usefulness of system and discover related tasks and problems.

2. Design In this part we want to focus on the design of the web tool. We shall introduce the architecture of our web tool system, which we shall call by the code-name Trillian. The proposed multi user architecture of the Trillian system is shown in Fig. 1. It consists of six main modules. The user connects to web pages using his standard web browser. User tracking module records his movement and content of the web pages he visits. User profile discovery module is responsible for profile analysis and identification of user’s information needs. Search agents search for data relevant to the user’s preferences and update the document database. Information sources behaviour monitor’s main goal is to identify how the most popular web pages change over time, which is very important for the pre-caching mechanism. The user services module is an interface between the user and the system. The Web Browser. It is a standard software tool for accessing web pages on the internet. The web browser accesses the Internet via a proxy server. The architecture is independent from the version or type of the browser. It is responsible for: navigation through web pages, graphical user interface to Trillian user, web browser extension (optional), client events. Personal Browsing Assistant. This module is the only part of a web tool system, with which the user co-operates. When new pages relevant to the user’s interests are discovered, the browsing assistant displays them to the user. It is responsible for: a user interface for full text search over visited documents, relevance feedback, personal caching control and monitoring control. Web Proxy. In the proposed architecture, web proxy is a common connection point where core system components and functions reside. All HTTP traffic passes through the web proxy and this enables access to the content of the web pages that the user visits.

Intelligent Support for Information Retrieval Web user

WWWspace, Internet

Web proxy

HTTP req./resp.

53

HTTP req./resp.

WWWbrowser application User tracking module

Personal browsing assistant (agent)

HTML documents User services module

Search agents module

Document database - user browsing logs - retrieved documents User profile discovery module

Information source behaviour monitor

Fig. 1. Trillian Architecture

While from a purely technical point of view, assuming that users access the internet via an internet service provider, the proxy can be either located at the ISP or on user’s computer, the choice can make a lot of difference from legal point of view. In particular, there are many privacy issues that may need to be addressed. User Tracking Module. The purpose of this module is to track the user’s browsing and behaviour in web space. It can reside anywhere along the HTTP stream. In our architecture the module is placed on the proxy server and therefore can access the user’s HTTP responses to record the pages he visited and their content. The module records all information necessary to gain important knowledge about the user’s online profile. It can be used in conditions where the usage of the proxy server is not possible. It is responsible for: recording of visited pages and storing them locally in the Trillian document database, recording of clickstream data. User Profile Discovery. This module represents probably the most important and difficult part of the whole Trillian architecture. Its main objective is to discover the

54

Robert Koval and Pavol Návrat

user’s topics of interest. This is done by an analysis of web access logs (clickstream data) and the content of visited web pages. The analysis has to be exhaustive to achieve reasonable results and therefore it has to be executed only in the post processing phase. In our work we have tried to perform some analysis “on the fly”, but speed performance was reduced significantly. The profile discovery process employs several miscellaneous algorithms to reach the desired goal. Methods such as cluster analysis, document cleanup, HTML analysis, browse path construction and others are used. The module is responsible for: Clickstream analysis. The module has to analyse clickstream data to identify information-rich documents among all the received pages. Discover Clusters of User’s Interests. This process is the core part of the whole Trillian system. It is very important to produce meaningful and correct clusters, which best describe user’s profile and interests. The module should analyse visited web pages and identify clusters of similar documents, words or phrases within them. Use Relevance Feedback from Users. During the analysis of visited documents, we can use relevance feedback provided by users from results of the previous analysis. Overall knowledge of the user’s interests can be improved in this way. E.g. we can consider clusters, words, phrases or even whole documents as negative examples, which means, during the subsequent analysis we will not identify similar content as important for the user. One important issue is a possibility that a user changes his interests. Indeed, most of research, including our one, does not sufficiently address this problem. It is clear that when user interests change new clusters have to be formed and some existing ones may have to be deleted. Search Agents Module. This part of the system performs an autonomous prefetching of documents from the web space or web exploration. The module uses a softbot-based mechanism to retrieve documents from the web. It uses information obtained using profile discovery to search for pages relevant to the user’s needs. Information Sources Behaviour Monitor. The web space and its dynamic behaviour cause frequent changes of many documents. The frequency of changes in web content is variable and depends on the particular web site. It varies from several years to several seconds (e.g. stock news). It is responsible for: discovery of page update patterns, pre-fetch pages in advance. The task of discovery of page update patterns is by far not trivial. Among the approaches that can be followed here, let us mention at least temporal web mining. User Services Module. The user services module transforms manipulated and analysed data into a form suitable for the user. It allows the user to provide content relevance feedback and feedback for monitoring and search agents. It is the interface to the core system parts through which the user gets data or controls processes, sets the parameters or explicitly describes his preferences. It is responsible for: full text search, attribute search and feedback mechanism. Central Database. The central database stores all the data required for successful analysis and monitoring of the user and web pages. The system uses a repository architecture template. All the core modules work with the data from the central database and update its contents.

Intelligent Support for Information Retrieval

55

User Tracking. The goal of the user tracking module is to record user’s movement and contents of the documents the user visits. As our empirical experiments show, the main requirements for this module are speed and robustness. Here the underlying assumption is that it is quite easy to identify each distinct user from the log of the proxy server. It should be noted, however, that the IP addresses in the log may not be entirely adequate to distinguish individual users [5]. 2.1 Suffix Tree Clustering (STC) The goal is to discover main document clusters using the analysis of visited documents (their contents) and an analysis of clickstream data. To discover interests of the user we need to perform a complicated analysis composed of several steps. The main step in the analysis process is called clustering. The clustering is used to extract groups (clusters) of words (terms) or phrases, which tend to be of similar meaning. We want to accomplish the following: to extract all textual information from the documents and - analysing their contents - to form groups of similar documents or topics. Similar documents are those, which have something in common (e.g. share a common phrase or topic). This is based on the clustering hypothesis, which states that the documents having a similar content are also relevant to the same query [11]. The query in our case has the meaning of an information need of the user. In the Trillian system, we have chosen to use a variant of a clustering method first introduced by [15] called the suffix tree clustering. The STC is used in the postretrieval step of the information retrieval. A suffix tree of strings is composed of suffixes of those strings. This formulation assumes only existence of one input sequence of strings. In our case we want to distinguish among string sequences from different documents. Therefore for this purpose there is a slightly modified structure called a generalised suffix tree, which is built as a compact trie of all the words (strings) in a document set. Leaf nodes in this situation are marked not only with an identifier of sequence but also carry information about the document from where the sequence originates. There are several possible ways of building a suffix tree. We employ a version of Ukonnen’s algorithm because it uses suffix links for fast traversal of the tree [12]. 2.2 STC Process The STC is composed of 3 main steps: document cleanup, maximal phrase clusters identification and cluster merging. Document Cleanup. Documents have to be preprocessed first before their contents are inserted into the suffix tree. The HTML documents contain a lot of irrelevant tagging information, which has to be removed first. Maximal Phrase Clusters Identification. For efficiency of using the suffix tree structure, maximal phrase clusters should be identified. By maximal phrase cluster we mean a phrase, which is shared by at least two documents. These maximal phrase clusters are represented in the suffix tree by those internal nodes, leaves of which originate from at least two documents (the phrase is shared by these documents).

56

Robert Koval and Pavol Návrat

Afterwards, a score is calculated for each maximal phrase cluster (MPC). The score of the MPC is calculated using following formula:

s (m) =| m | . f (| m p |).∑ tfidf ( wi ) where |m| is the number of documents in a phrase cluster m, wi are the words in a maximal phrase cluster and tfidf(wi) is the score calculated for each word in the MPC. |mp| is the number of non-stop words within the cluster. Function f penalises short word phrases; it is linear for phrases up to 6 words long and is constant for longer phrases. At this stage we can also apply scores of each word calculated by their position in the HTML document (e.g. in

m). On the other hand, the OPS checks begin from the left end of the window. When there is a mismatch, the window is shifted to the right, but generally at least the record that caused the mismatch in the previous window has to be re-checked. Depending on the compatibility of pattern predicates, the checking of records in a new window begins at a record at the left side of the previously mismatched record, causing backtracking. Therefore, in OPS, usually mismatched records have to be re-checked and, even in the best case, any record has to be checked at least once and this best computation is O(n). In the following, in order to demonstrate how our algorithm compares to OPS, we present the searching results for the query and data below that were used in [9] to evaluate OPS. Query: “For IBM stock prices, find all instances where the pattern of two successive drops are followed by two successive increases, and the drops take the price to a value between 40 and 50, and the first increase doesn’t move the price beyond 52.” Stream Data: 55 50 45 51 54 50 47 49 45 42 55 57 59 60 57 Fig. 10 compares the evolution of the values of positions i on the data stream, and j on the pattern, for the naive algorithm, the OPS algorithm and our R2L-basic and R2L-extended algorithms. Of course, the results in Fig. 10 (a) and (b) for the naive approach and OPS are the same as those presented in [9]. The naive approach needed 9 processing windows and 20 checks of pattern predicates against stream records. OPS needed 7 windows and 16 checks. R2L-basic, which does not treat inequalities separately in the conjunctive pattern predicates, needed 8 windows and 11 checks. And R2L-extended that separates inequalities in the conjunctions needed 7 windows and 10 checks, showing the best performance among the four algorithms. For the OPS algorithm, backtracking episodes (i.e., i values decreasing for consecutive points along the processing) do not occur as in the naive approach. However, in OPS, mismatched records are successively re-checked many times (same i values for consecutive points). Although the number of processing windows isn’t smaller than the OPS algorithm, we can see that R2L-basic only re-checks records for the last window where there were no mismatch, that is, where the pattern was completely found. We can see that by analyzing the shape and range predicates separately, in R2L-extended the mismatch at r[3] (i=3) in the first window is followed by a larger shift than for R2L-basic, so that the checking of r[4] at i=4 is skipped.

Complex Temporal Patterns Detection over Continuous Data Streams

w2 (4)

2

w6 (13) w6 (12) w3 w5 (7) (10)

w2 (3)

1

0

w9 (20)

w2 (5)

3

w9 (19)

w7 (15)

w9 (18)

0

1

2

3

4

5

6

7

8

w4 (10)

w2 (3)

1

9 10 11

w7 (16)

w2 (4)

2

0

w1 w2 w3 w4 w5 w6 w7 w8 w9 (1) (2) (6) (8) (9) (11) (14) (16) (17)

w2 (5)

3

w1 (1)

0

w3 (7)

w2 (2)

1

2

3

4

w7 (15)

w5 (11)

w4 (9)

w4 (8)

w3 (6)

413

5

i (a)

w6 (12)

6

w7 (14)

w7 (13)

7

8

9 10 11

i (b)

i-naive

3

w1 w2 w3 w4 (1) (2) (3) (4)

w5 w6 w7 (5) (6) (7)

w8 (8)

w8 (9)

2

w8 (10)

1

0

1

2

3

4

5

6

7

8

w2 w3 w4 (2) (3) (4)

w1 (1)

10 11

w7 (7)

w7 (8)

2

w7 (9)

w7 (10)

0 9

w5 w6 (5) (6)

1

w8 (11)

0

3

0

1

2

3

4

5

6

7

8

9 10 11

i i (c) (d) Fig. 10. Records and Predicates Checks for: (a) Naive (b) OPS (c) R2L-Basic (d) R2L-Extended Algorithms

5

Conclusions

In this paper we describe a novel algorithm for querying complex temporal patterns over data streams. Our algorithm first preprocesses the complex temporal pattern at compile time and generates information on how much to skip processing when mismatches are found at run-time. Patterns are searched over the data stream with a window that slides from left-to-right. The stream records inside the window are checked to see if they satisfy the predicates of the pattern from right-to-left. The precomputation of logical relations among subsequences of pattern predicates drives the determination of efficient shifts for windows and minimizes repeated passes over the same data. The basic idea is similar to the one adopted by the Boyer-Moore algorithm for string-search in texts, and our algorithm can be seen as its generalization for the more general case of complex patterns with conjunctions of inequalities over data streams. Experiments showed that our algorithm outperformed the naive approach often with dramatic improvements. We also found that in many cases, the checking of

414

Lilian Harada

the stream records from right-to-left, as done in our R2L algorithm, shows better performance than the checking from left-to-right, which is in conformance to the results that the Boyer-Moore algorithm is more efficient than the Knuth-Pratt-Morris algorithm in textual applications.

References 1.

Babu, S., Widom, J.: Continuous Queries over Data Streams. ACM SIGMOD Record, Vol. 30, No. 3 (2001) 109-120 2. Bonnet, P., Gehrke J., Seshadri P.: Towards Sensor Database Systems. Proceedings Conference on Mobile Data Management (2001) 3-14 3. Gehrke, J., Korn, F., Srivastava, D.: On Computing Aggregates Over Continual Data Streams. Proceedings ACM SIGMOD Conference (2001) 13-24 4. Gilbert, A.C., et al.: Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries. Proceedings 27th VLDB Conference (2001) 79-88 5. Guo, S., Sun, W., Weiss, M.: On Satisfiability, Equivalence, and Implication Problems Involving Conjunctive Queries in Database Systems. IEEE Transactions on Knowledge and Data Engineering, Vol. 8, No. 4 (1996) 604-616 6. Harada, L.: Pattern Matching on Multi-Attribute Data Streams, submitted (2002) 7. Knuth, D. E., Morris, J. H., Pratt, V. R.: Fast Pattern Matching in Strings. SIAM Journal of Computing, Vol. 6, No. 2 (1977) 323-350 8. Moore, J. S. and Boyer, R. S.: A Fast String Searching Algorithm. Communication of the ACM, Vol. 20, No. 10 (1977) 762-772 9. Sadri, R.,Zaniolo, C., Zarkesh, A., Adibi, J.: Optimization of Sequence Queries in Database Systems. Proceedings ACM PODS Conference (2001) 71-81 10. Sullivan, M., Heybey, A.: Tribeca: A System for Managing Large Databases of Network Traffic. USENIX Annual Technical Conference (1998)

Author Index

Abdelmoty, Alia I. Akal, Fuat 218 Atzeni, Paolo 1

191

Barrena, Manuel 177 Bielikov´ a, M´ aria 388 B¨ ohm, Klemens 218 Boyens, Claus 8 Brakatsoulas, Sotiris 149 Brisaboa, Nieves R. 277 Ca˜ nadas, Joaquin 163 Caplinskas, Albertas 248 Chrysanthis, Panos K. 135 Corral, Antonio 163 Diwakar, Hemalatha 346 Dolog, Peter 388 Doulkeridis, Christos 360 Eder, Johann 326 El-Geresy, Baher A. Feyer, Thomas

191

Gergatsoulis, Manolis 360 Giannella, Chris 37 Grinev, Maxim 340 Gruber, Wolfgang 326 Guan, Jihong 65 G¨ unther, Oliver 8 Habela, Piotr 263 Harada, Lilian 401 Hwang, Buhyun 106

Jones, Christopher B. Jurado, Elena 177

248

Marathe, Mona 346 Medina, Enrique 232 Mena, Eduardo 92 N´ avrat, Pavol

51, 80

Panayiotou, Christoforos 120 Param´ a, Jos´e R. 277 Penabad, Miguel R. 277 Pfoser, Dieter 149 Pitoura, Evaggelia 135 ´ Places, Angeles S. 277 Polˇcicov´ a, Gabriela 80 Roantree, Mark

305

Ilarri, Sergio 92 Illarramendi, Arantza

Lee, Ukhyun 106 Liu, Chengfei 374 Liu, Jixue 374 Lupeikiene, Audrone

263

Samaras, George 120 Schek, Hans-J¨ org 23, 218 Schuldt, Heiko 23 Schuler, Christoph 23 Shigiltchoﬀ, Oleg 135 Stavrakas, Yannis 360 Subieta, Kazimierz 263 Thalheim, Bernhard Theodoridis, Yannis Trujillo, Juan 232

305 149

Vasilecas, Olegas 248 Vassilakopoulos, Michael 92

Weber, Roger 23 Wojciechowski, Marek

163

86

191

Konovalov, Alexandre 319 Koval, Robert 51 Kuznetsov, Sergey 340 Kwon, Joon-Hee 204

Yoon, Yong-Ik

204

Zafeiris, Vassilis 360 Zakrzewicz, Maciej 86 Zamulin, Alexandre 291 Zhou, Shuigeng 65

Advances in Databases and Information Systems: 8th East European Conference, ADBIS 2004, Budapest, Hungary, September 22-25, 2004, Proceedings

Read more

Advances in Databases and Information Systems: Third East European Conference, ADBIS'99, Maribor, Slovenia, September 13-16, 1999, Proceedings

Read more

Advances in Databases and Information Systems: 9th East European Conference, ADBIS 2005, Tallinn, Estonia, September 12-15, 2005, Proceedings

Read more

Advances in Databases and Information Systems: 11th East European Conference, ADBIS 2007, Varna, Bulgaria, September 29-October 3, 2007, Proceedings

Read more

Advances in Databases and Information Systems: 7th East European Conference, ADBIS 2003, Dresden, Germany, September 3-6, 2003, Proceedings

Read more

Advances in Databases and Information Systems: 5th East European Conference, ADBIS 2001, Vilnius, Lithuania September 25-28, 2001 Proceedings

Read more

Advances in Databases and Information Systems: 10th East European Conference, ADBIS 2006, Thessaloniki, Greece, September 3-7, 2006, Proceedings

Read more

Advances in Databases and Information Systems: Second East European Symposium, ADBIS '98, Poznan, Poland, September 7-10, 1998, Proceedings

Read more

Advances in Object-Oriented Information Systems: OOIS 2002 Workshops, Montpellier, France, September 2, 2002 Proceedings

Read more

Advances in Databases and Information Systems, 12 conf., ADBIS 2008

Read more

Advances in Databases and Information Systems - ADBIS 2011

Read more

Advances in Case-Based Reasoning: 6th European Conference, ECCBR 2002 Aberdeen, Scotland, UK, September 4-7, 2002 Proceedings

Read more

Advances in Information Systems: Second International Conference, ADVIS 2002, Izmir, Turkey, October 23-25, 2002. Proceedings

Read more

Object-Oriented Information Systems: 8th International Conference, OOIS 2002, Montpellier, France, September 2-5, 2002, Proceedings

Read more

Cooperative Information Agents VI: 6th International Workshop, CIA 2002, Madrid, Spain, September 18 - 20, 2002. Proceedings

Read more

Advances in Databases and Information Systems: 13th East European Conference, ADBIS 2009, Riga, Latvia, September 7-10, 2009, Proceedings (Lecture ... Applications, incl. Internet Web, and HCI)

Read more

Research and Advanced Technology for Digital Libraries: 6th European Conference, ECDL 2002, Rome, Italy, September 16-18, 2002, Proceedings

Read more

Current Issues in Databases and Information Systems: East-European Conference on Advances in Databases and Information Systems Held Jointly with ... Proceedings

Read more

Engineering and Deployment of Cooperative Information Systems: First International Conference, EDCIS 2002, Beijing, China, September 17-20, 2002. Proceedings

Read more

Recent Advances in Visual Information Systems: 5th International Conference, VISUAL 2002 Hsin Chu, Taiwan, March 11-13, 2002. Proceedings

Read more

Scientific American (September, 2002)

Read more

Databases in Networked Information Systems: Second International Workshop, DNIS 2002, Aizu, Japan, December 16-18, 2002, Proceedings

Read more

Principles of Data Mining and Knowledge Discovery: 6th European Conference, PKDD 2002, Helsinki, Finland, August 19-23, 2002, Proceedings

Read more

Electronic Government: First International Conference, EGOV 2002, Aix-en-Provence, France, September 2-5, 2002. Proceedings

Read more

Database and Expert Systems Applications: 13th International Conference, DEXA 2002, Aix-en-Provence, France, September 2-6, 2002. Proceedings

Read more

Genetic Programming: 5th European Conference, EuroGP 2002, Kinsale, Ireland, April 3-5, 2002. Proceedings

Read more

Advances in Cryptology - EUROCRYPT 2002

Read more

Advances in Cryptology - ASIACRYPT 2002

Read more

Advances in Databases: 19th British National Conference on Databases, BNCOD 19, Sheffield, UK, July 17-19, 2002. Proceedings

Read more

Flexible Query Answering Systems: 5th International Conference, FQAS 2002. Copenhagen, Denmark, October 27-29, 2002, Proceedings

Read more

Recommend Documents

Advances in Databases and Information Systems: 8th East European Conference, ADBIS 2004, Budapest, Hungary, September 22-25, 2004, Proceedings

Lecture Notes in Computer Science Commenced Publication in 1973 Founding and Former Series Editors: Gerhard Goos, Juris ...

Advances in Databases and Information Systems: Third East European Conference, ADBIS'99, Maribor, Slovenia, September 13-16, 1999, Proceedings

Lecture Notes in Computer Science Edited by G. Goos, J. Hartmanis and J. van Leeuwen 1691 3 Berlin Heidelberg New Yo...

Advances in Databases and Information Systems: 9th East European Conference, ADBIS 2005, Tallinn, Estonia, September 12-15, 2005, Proceedings

Lecture Notes in Computer Science Commenced Publication in 1973 Founding and Former Series Editors: Gerhard Goos, Juris ...

Advances in Databases and Information Systems: 11th East European Conference, ADBIS 2007, Varna, Bulgaria, September 29-October 3, 2007, Proceedings

Lecture Notes in Computer Science Commenced Publication in 1973 Founding and Former Series Editors: Gerhard Goos, Juris ...

Advances in Databases and Information Systems: 7th East European Conference, ADBIS 2003, Dresden, Germany, September 3-6, 2003, Proceedings

Lecture Notes in Computer Science Edited by G. Goos, J. Hartmanis, and J. van Leeuwen 2798 3 Berlin Heidelberg New Y...

Advances in Databases and Information Systems: 5th East European Conference, ADBIS 2001, Vilnius, Lithuania September 25-28, 2001 Proceedings

Lecture Notes in Computer Science Edited by G. Goos, J. Hartmanis, and J. van Leeuwen 2151 3 Berlin Heidelberg New Y...

Advances in Databases and Information Systems: 10th East European Conference, ADBIS 2006, Thessaloniki, Greece, September 3-7, 2006, Proceedings

Lecture Notes in Computer Science Commenced Publication in 1973 Founding and Former Series Editors: Gerhard Goos, Juris ...

Advances in Databases and Information Systems: Second East European Symposium, ADBIS '98, Poznan, Poland, September 7-10, 1998, Proceedings

Lecture Notes in Computer Science Edited by G. Goos, J. Hartmanis and J. van Leeuwen 1475 Witold Litwin Tadeusz Morzy...

Advances in Object-Oriented Information Systems: OOIS 2002 Workshops, Montpellier, France, September 2, 2002 Proceedings

Lecture Notes in Computer Science Edited by G. Goos, J. Hartmanis, and J. van Leeuwen 2426 3 Berlin Heidelberg New Y...

Advances in Databases and Information Systems, 12 conf., ADBIS 2008

Lecture Notes in Computer Science Commenced Publication in 1973 Founding and Former Series Editors: Gerhard Goos, Juris ...

Advances in Databases and Information Systems: 6th East European Conference, ADBIS 2002, Bratislava, Slovakia, September 8-11, 2002, Proceedings

Advances in Databases and Information Systems: 8th East European Conference, ADBIS 2004, Budapest, Hungary, September 22-25, 2004, Proceedings

Advances in Databases and Information Systems: Third East European Conference, ADBIS'99, Maribor, Slovenia, September 13-16, 1999, Proceedings

Advances in Databases and Information Systems: 9th East European Conference, ADBIS 2005, Tallinn, Estonia, September 12-15, 2005, Proceedings

Advances in Databases and Information Systems: 11th East European Conference, ADBIS 2007, Varna, Bulgaria, September 29-October 3, 2007, Proceedings

Advances in Databases and Information Systems: 7th East European Conference, ADBIS 2003, Dresden, Germany, September 3-6, 2003, Proceedings

Advances in Databases and Information Systems: 5th East European Conference, ADBIS 2001, Vilnius, Lithuania September 25-28, 2001 Proceedings

Advances in Databases and Information Systems: 10th East European Conference, ADBIS 2006, Thessaloniki, Greece, September 3-7, 2006, Proceedings

Advances in Databases and Information Systems: Second East European Symposium, ADBIS '98, Poznan, Poland, September 7-10, 1998, Proceedings

Advances in Object-Oriented Information Systems: OOIS 2002 Workshops, Montpellier, France, September 2, 2002 Proceedings

Advances in Databases and Information Systems, 12 conf., ADBIS 2008

Advances in Databases and Information Systems - ADBIS 2011

Advances in Case-Based Reasoning: 6th European Conference, ECCBR 2002 Aberdeen, Scotland, UK, September 4-7, 2002 Proceedings

Advances in Information Systems: Second International Conference, ADVIS 2002, Izmir, Turkey, October 23-25, 2002. Proceedings

Object-Oriented Information Systems: 8th International Conference, OOIS 2002, Montpellier, France, September 2-5, 2002, Proceedings

Cooperative Information Agents VI: 6th International Workshop, CIA 2002, Madrid, Spain, September 18 - 20, 2002. Proceedings

Advances in Databases and Information Systems: 13th East European Conference, ADBIS 2009, Riga, Latvia, September 7-10, 2009, Proceedings (Lecture ... Applications, incl. Internet Web, and HCI)

Research and Advanced Technology for Digital Libraries: 6th European Conference, ECDL 2002, Rome, Italy, September 16-18, 2002, Proceedings

Current Issues in Databases and Information Systems: East-European Conference on Advances in Databases and Information Systems Held Jointly with ... Proceedings

Engineering and Deployment of Cooperative Information Systems: First International Conference, EDCIS 2002, Beijing, China, September 17-20, 2002. Proceedings

Recent Advances in Visual Information Systems: 5th International Conference, VISUAL 2002 Hsin Chu, Taiwan, March 11-13, 2002. Proceedings

Scientific American (September, 2002)

Databases in Networked Information Systems: Second International Workshop, DNIS 2002, Aizu, Japan, December 16-18, 2002, Proceedings

Principles of Data Mining and Knowledge Discovery: 6th European Conference, PKDD 2002, Helsinki, Finland, August 19-23, 2002, Proceedings

Electronic Government: First International Conference, EGOV 2002, Aix-en-Provence, France, September 2-5, 2002. Proceedings

Database and Expert Systems Applications: 13th International Conference, DEXA 2002, Aix-en-Provence, France, September 2-6, 2002. Proceedings

Genetic Programming: 5th European Conference, EuroGP 2002, Kinsale, Ireland, April 3-5, 2002. Proceedings

Advances in Cryptology - EUROCRYPT 2002

Advances in Cryptology - ASIACRYPT 2002

Advances in Databases: 19th British National Conference on Databases, BNCOD 19, Sheffield, UK, July 17-19, 2002. Proceedings

Flexible Query Answering Systems: 5th International Conference, FQAS 2002. Copenhagen, Denmark, October 27-29, 2002, Proceedings

Recommend Documents