From Serge.Abiteboul@inria.fr Mon Oct 3 15:15:24 1994 Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by lirmm.lirmm.fr (8.6.9/8.6.4) with ESMTP id PAA01684; Mon, 3 Oct 1994 15:15:21 +0100 Received: from cosmos.inria.fr (cosmos.inria.fr [128.93.11.30]) by concorde.inria.fr (8.6.9/8.6.9) with ESMTP id PAA27064; Mon, 3 Oct 1994 15:15:07 +0100 Received: from chronos.inria.fr (chronos.inria.fr [128.93.11.58]) by cosmos.inria.fr (8.6.8/8.6.6) with ESMTP id PAA07330 for ; Mon, 3 Oct 1994 15:14:40 +0100 From: Serge Abiteboul (VERSO) Received: (abitebou@localhost) by chronos.inria.fr (8.6.8/8.6.6) id PAA01454; Mon, 3 Oct 1994 15:16:15 +0100 Date: Mon, 3 Oct 1994 15:16:15 +0100 Message-Id: <199410031416.PAA01454@chronos.inria.fr> To: bd3@cosmos.inria.fr Subject: ICDT Reply-to: Serge.Abiteboul@inria.fr (Serge Abiteboul) Status: R 5th International Conference on Database Theory (ICDT) Preliminary Program Prague, Czech Republic January 10-13, 1995 Invitation to ICDT '95 ICDT 95 is an international conference on theoretical aspects of databases. Like ICDT 92 (Berlin) this conference follows two series of conferences on database theory that were formed in parallel by different scientific communities in Europe. The first series, known as International Conference on Database Theory, was initiated in Rome in 1986, and continued in Bruges (1988) and Paris (1990). The second series, known as Symposium on Mathematical Fundamentals of Database Systems, was initiated in Dresden (1987), and continued in Visegrad (1989) and Rostock (1991). ICDT is held bi-annually. ******************************************************************* Highlights ******************************************************************* Invited Talks Data on Air: An Introduction to Wireless and Mobile Computing, Tomasz Imielinski, Rutgers University USA Mobile and wireless computing is a new emerging computing paradigm posing many challenging data-management problems on the border of computing and communication. We provide a brief introduction to wireless technology, identify new research challenges and investigate their technical significance. New research problems emerge due to mobility of users, narrow wireless bandwidth and limitations of battery power. Some of these problems may be of interest to the theoretical community and with this focus in mind we discuss in more detail: energy-efficient data management, management of location-dependent data, frequent disconnections and their impact on consistency of data, and organization and access to wireless data broadcast. Tomasz Imielinski is an Associate Professor at the Department of Computer Science, Rutgers University in New Brunswick, NJ, USA. He has received his PhD from Polish Academy of Science (Warsaw) in 1982. He is an author of over 60 papers in the areas of database management systems, mobile and wireless computing and artificial intelligence. His current interests include database mining and mobile wireless computing. He is a principle investigator of the DataMan project at Rutgers University, involving data management issues in mobile computing. Dr. Imielinski has served on numerous program committees and was a general chairman of the ACM SIGMOD Conference. Spatial Databases, the Final Frontier, Jan Paredaens, University of Antwerp, Belgium During the last decade the need to manage two- and three-dimensional information has grown substantially. Although a lot of effort has been put in applications and implementations, the fundamental results in this field are still scarce. An overview is given of different possible data models to handle spatial information. Recent results are discussed. Finally a number of new promissing research topics in this area are given. Jan Paredaens studied mathematics and Computer Science at the University of Brussels and got a Ph. D. in 1974. He was a research member at Philips Lab in Brussels and became full professor at the University of Antwerp in 1979. He is also associated with the Technical University of Eindhoven, The Netherlands. At these Universities he has research and educational positions in databases and fundamental aspects of computer sience. Prof. Dr. J. Paredaens is author of five books in computer science, mainly on programming languages and databases. He also published about 100 papers in international journals, conferences and workshops. His research activities are mainly focussed on properties of relational and object-oriented databases, expressive power of query and update languages, visual interfaces for information processing and spatial databases. He has been a member of the program committee of numerous international conferences and is involved in several international scientific journals. Tutorials Parallel Database Systems, Gerhard Weikum University of the Saarland, Saarbruecken, Germany Parallel database technology has evolved to a point where commercial systems appear to be fairly mature. Algorithms and run-time mechanisms for both speeding up query response time and scaling up transaction throughput are well understood. However, using a parallel database system effectively under real application workloads poses a number of complex optimization problems with respect to query processing policies, data placement, and resource management. These policy issues are still largely unexplored, from a theoretical as well as practical perspective. This tutorial will give an overview of the state of the art in parallel database technology, and will point out important avenues of further research. Gerhard Weikum is a Full Professor in the Department of Computer Science of the University of the Saarland at Saarbruecken, Germany, where he is leading a research group on database systems and information systems. Former affiliations include the Department of Computer Science at the Swiss Federal Institute of Technology (ETH) Zurich, Switzerland, and the Microelectronics and Computer Technology Corporation (MCC) at Austin, Texas. At ETH Zurich, Dr. Weikum was leading the COMFORT project which involved building a self-tuning database system with capabilities for automatic data placement in parallel and distributed storage systems, adaptive load control, and the tuning of inter- versus intra-transaction parallelism. Dr. Weikum is an Associate Editor of ACM Transactions on Database Systems, and he has served on the program committee of several international conferences. Languages for Polynomial-time Queries -- an ongoing Quest, Phokion Kolaitis During the past twenty years, a major direction of research in database theory has focused on the development of progressively more powerful languages for relational queries. Much of the work in this area has concentrated on the problem of finding languages that capture exactly the queries that are computable in polynomial-time in the size of the database. The quest for such languages has resulted into an extensive interaction between database theory, finite-model theory, and computational complexity. Although satisfactory answers have been obtained in certain important special cases, a solution to the general problem remains elusive. The aim of this tutorial is to describe some of the main results obtained so far and to present a status report on this problem. Phokion G. Kolaitis is an Associate Professor of Computer and Information Sciences at the University of California, Santa Cruz, U.S.A. His research interests include finite- model theory, computational complexity, and database theory. He is currently serving on the editorial boards of the Chicago Journal of Theoretical Computer Science and the Journal of Logic and Computation. In 1993 he was awarded a John Simon Guggenheim Memorial Foundation Fellowship. ********************************************************************* ICDT '95 is organized by Faculty of Electrical Engineering, Czech Technical University of Prague; Christian Doppler Laboratorium fuer Expertensysteme Wien, Vienna University of Technology; ICDT '95 cooperates with Arbeitsgruppe EMISA (2.5.2) der Gesellschaft fuer Informatik (GI) e.V.; European Association for Theoretical Computer Science (EATCS); Institute of Computer Science of the Academy of Science of the Czech Republic; The Joint Center of CTU Prague and FAW Linz; Charles University, Prague; A Best Student Paper Award was granted to ICDT '95 by The Extending Database Technology (EDBT) Foundation ICDT '95 is sponsored by IDOMENEUS Network Esprit Network of Excellence; COMPULOG NET Network of Excellence in Computational Logic; Christian Doppler Laboratorium fuer Expertensysteme; For further information contact Dr. Marcela Bezouskova Dept. of Control Engineering Faculty of Electrical Engineering Czech Technical University Karlovo nam. 13 CZ - 12135 PRAGUE 2 phone: +42 2 295664 or +42 2 24357488 fax: +42 2 290159 e-mail: k335@lab.felk.cvut.cz ------------------------------------------------------------------ Scientific Program Tuesday, January 10, 1995 ------------------------- Registration: 10.00--20.00 Tutorial I: 14.00--16.00 Parallel Database Systems, Gerhard Weikum Coffee Break Tutorial II: 16.30--18.30 Languages for Polynomial-time Queries -- an ongoing Quest, Phokion Kolaitis 20.30 Informal get together Wednesday, January 11,1995 -------------------------- Invited Lecture I: 9.00-10.00 Chair: Moshe Vardi Data on Air: An Introduction to Wireless and Mobile Computing, Tomasz Imielinski Coffee Break Session 1: Optimization 10.20--11.20 Chair: Jaroslav Pokorny Distributed Query Optimization in Loosly Coupled Multidatabase Systems, Silvio Salza, Giovanni Barone, Tadeusz Morzy On the Complexity of Generating Optimal Left-Deep Processing Trees with Cross Products, Sophie Cluet, Guido Moerkotte Session 2: Nonmonotonic Semantics I 11.30--12.30 Chair: Victor Marek Querying Disjunctive Database Through Nonmonotonic Logics, Piero A. Bonatti, Thomas Eiter DATALOG Queries with Stratified Negation and Choice: from P to D^P, Sergio Greco, Domenico Sacca, Carlo Zaniolo Lunch Break Session 3: Query Languages I 14.15--15.45 Chair: Mars K. Valiev On the Kolmogorov Complexity of Boolean Query Languages, Jerzy Tyszkiewicz On Two Forms of Structural Recursion, Dan Suciu, Limsoon Wong Delta-Languages for Sets and sub-PTIME Graphs Transformers, Vladimir Sazonov, Alexei Lisitsa Coffee Break Session 4: Concurrency Control 16.15--17.45 Chair: Gottfried Vossen Partial Strictness in Two-Phase Locking, Eljas Soisalon-Soininen, Tatu Yloenen Unified Transaction Model for Semantically Rich Operations, Radek Vingralek, Haiyen Ye, Yuri Breitbart, Hans-J"org Schek The Dynamic Two Phase Commitment (D2PC) Protocol, Yoav Raz Dinner Break Open Problems Session 20.15 open end Chair: Bernhard Thalheim Thursday, January 12, 1995 -------------------------- Session 5: Query Languages II 9.00--10.30 Chair: Jan Van den Bussche Domain-independent Queries on Databases with External Functions, (Best Student Paper) Dan Suciu An Algebra for Pomsets, Stephane Grumbach, Tova Milo On the Power of Stratified Logic Programs with Value-Invention for Expressing Database Transformations, Luca Cabibbo Coffee Break Session 6: Advanced Models 11.00--12.30 Chair: Georg Lausen A Stable Model Semantics for Behavioral Inheritance in Deductive Object Oriented Languages, Michele Bugliesi, Hassan M. Jamil A Rewriting Technique for the Analysis and the Optimization of Active Databases, Danilo Montesi, Riccardo Torlone Sorted HiLog: Sorts in Higher-Order Logic Data Languages, Weidong Chen, Michael Kifer Lunch Break Session 7: Probabilistic Methods 14.15--15.45 Chair: Thomas Eiter Average Keys and Functional Dependencies in Random Databases, Janos Demetrovics, G.O.H. Katona, D. Miklos, Oleg Seleznjev, Bernhard Thalheim Uniformly-Distributed Random Generation of Join Orders, Cesar A.Galindo-Legaria, Arjan Pellenkoft, Martin L. Kersten A Probabilistic View of Datalog Parallelization, Sergio Lifschitz, Victor Vianu Coffee Break Session 8: Constraints and Dependencies 16.15--17.45 Chair: Bernhard Thalheim A First Step Towards Implementing Dynamic Algebraic Dependencies, Nicole Bidoit, S. De Amo Constraint-Generating Dependencies, Marianne Baudinet, Jan Chomicki, Pierre Wolper Optimization Using Tuple Subsumption, Venky Harinarayan, Ashish Gupta Friday, January 12, 1995 ------------------------ Invited Lecture II: 9.00--10.00 Chair: Georg Gottlob Spatial Databases, the Final Frontier, Jan Paredaens Coffee Break Session 9: Nonmonotonic Semantics II 10.20--11.20 Chair: Carlo Zaniolo Deterministic and Non-Deterministic Stable Model Semantics for Unbound DATALOG Queries, Domenico Sacca Revision programming, database updates and integrity constraints, Victor W. Marek, Miroslav Truszcynski Session 10: Datalog Analysis 11.30--12.30 Chair: Foto Afrati Some Positive Results for Boundedness of Multiple Recursive Rules, Ke Wang Increment Boundedness and Nonrecursive Incremental Evaluation of Datalog Queries, Guozhu Dong, Jianwen Su Lunch Break Session 11: Query Languages III 14.15--15.45 Chair: Stephane Grumbach Approximation in Databases, Leonid Libkin Datalog Queries over Set Constraint Databases, Peter Z. Revesz Space Usage in Functional Query Languages, Serge Abiteboul, Gerd Hillebrand Conference End -------------------------------------------------------------------- General Information * Location The Conference will be held in Hotel Krystal, J. Martiho 2, Prague 6 - Veleslavin, Phone: +42 2 3162761, Fax: +42 2 3164215. Accommodation in this hotel is available and is highly recommended by the organizers. The hotel can be reached as follows. From the City Center Take subway line A until the terminal stop "Dejvicka", then take tram number 2 or 26 or bus 119 on Evropska street in the direction of the airport and get out at stop "Koospol". From the train station Take line C to Museum, then change to line A until the terminal stop Dejvicka, then take tram number 2 or 26 or bus 119 on Evropska street in the direction of the airport and get out at stop Koospol. From the Airport Either take a taxi (approximately 300 Crowns) or take bus number 119 to the stop "Koospol" * Language The official conference language is English; no simultaneous translation will be provided. * Proceedings The conference proceedings will appear as a volume of the Lecture Notes in Computer Science (LNCS) series, published by Springer-Verlag, and will be available at the conference. Each registered participant will receive a copy of the proceedings (except for students). After the conference, the proceedings of ICDT '95 will be available from your local bookstore. * Special Events We plan to hold an informal get-together party on Tuesday, January 10, 1995. It will start at the conference location site at 20.30. On Thursday evening, conference participants are invited to join a concert of Czech Chamber Music followed by a conference dinner. Transportation will be provided and the events are covered by the conference fee. The price for additional tickets is ATS 500 (see registration form). * Open Problems Session There will be an "Open Problems Session" where participants can illustrate open problems in database theory. The session will be chaired by Bernhard Thalheim. Participants who would like to present open problems may submit a short description of their problem in LaTeX to him (thalheim@informatik.tu-cottbus.de). The problems presented during the problems session will be summarized by Bernhard Thalheim and presented after ICDT to a larger community. * Registration Procedure People wishing to attend the conference should fill out the enclosed registration form and return it together with the proper payment to the address below. E-mail registration with credit card payment (VISA, EuroCard, MasterCard) is strongly prefered. Katrin Seyr ICDT'95 Dept. of Information Systems Vienna Univ. of Technology Paniglgasse 16 A - 1040 VIENNA Phone: +43 1 58801 6112 Fax: +43 1 5055304 Email: seyr@vexpert.dbai.tuwien.ac.at It is suggested to register for the conference at your earliest convenience. As soon as both registration form and fees have been received, a written or email confirmation will be sent. Please make sure that your society affiliation (membership number) and/or university affiliation are shown on your registration form, or that proof of your full-time student status comes together with it. Otherwise, a discount on the conference fee cannot be granted. A separate form must be completed by each participant. Registration by phone, fax or email is acceptable only if the applicable payment is transmitted in parallel (VISA, MasterCard and EuroCard). On--site registration will be available at the conference office during ICDT '95, starting Tuesday, January 10, 10.00 am. Registration Desk and Conference Office opening hours Tuesday, January 10: 10.00 -- 20.00 Wednesday, January 11: 8.00 -- 18.00 Thursday, January 12: 9.00 -- 17.00 Friday, January 13: 9.00 -- 15.00 Fees Since the financial situation for participants from universities and public research labs is usually more difficult than for those employed by an industrial enterprise, we charge the latter a slightly higher conference fee. Members of GI and its sister associations can take advantage of a fee reduction due to the financial backup provided by this organization. conference fees ---------------------------------------------------------------------- |registration postmarked | before or on Dec. 10 | after Dec. 10 | |and fee sent | | | |--------------------------------------------------------------------- |members of GI, EATCS and | ATS 4.200 | ATS 5.000 | |university affiliates | | | |others | ATS 4.500 | ATS 5.200 | |students | ATS 2.500 | ATS 2.800 | ---------------------------------------------------------------------- The conference fee includes admission to all sessions including the two tutorials, a copy of the proceedings (not included in the student fee), refreshments during the breaks and the special events. Please note that ATS 100 correspond to aproximately US$ 9 or DM 14. --------------------------------------------------------------------- | | Single | Double | --------------------------------------------------------------------- |Rooms at the Hotel Krystal per day | ATS 500.- | ATS 700.- | --------------------------------------------------------------------- Other hotels can be booked through the local agency by contact Dr. Marcela Bezouskova by email (k335@lab.felk.cvut.cz) or fax (+42 2 290159). A Special Note for East-European Participants A limited number of free participations for people from Eastern Europe (free conference attendance and accommodation) will be offered. To become eligible for this support, please fill out the application you find elsewhere in this brochure and send it to Katrin Seyr by mail, fax, or email before December 1, 1994. Methods of Payment All fees including hotel fees for Hotel Krystal have to be paid in Austrian currency (ATS) either by * credit card (mail to Katrin Seyr) * bank transfer (free of charges for us, please) to the following account: Bank: & Creditanstalt Bank Code: & 11000 Account No.: & 0964-35100/00 Receiver: & ICDT'95 European participants can make their payments using a Eurocheque written in the applicable amount in Austrian Shillings (ATS); in that case, please do not forget to include your Eurocheque card number on the back. Registrations for which no payment is received within reasonable time will not be accepted. Cancellation and Refund Cancellations must be made in written form to Katrin Seyr. If a cancellation notification is received before December 10, 80% of the fees will be refunded; no refunds will be made thereafter. For registered participants who cannot attend, the proceedings will be mailed after the conference. * Hotel Information and Meals The organizers recommend the Hotel Krystal for accommodation. The Hotel Krystal is a hotel partially owned by the Prague Universities and offers very convenient rates. The hotel meets the *** standard. Participants wishing to make a reservation for a hotel with higher standards please contact Dr. Marcela Bezouskova from the organizing committee by email or fax. Except for the Conference Dinner meals are not included in the conference fee. However, cheap lunch tickets for the Hotel self-service restaurant can be purchased in Czech crowns at the conference registration desk. In addition, there are two other small restaurants in the hotel. There is an exchange office in the lobby of the Hotel Krystal. * About Prague Prague, the capital of the Czech Republic, is considered to be one of the most beautiful cities in Europe. Its magical atmosphere is determined by the happy and tolerant coexistence of the buildings, sculptures and monuments of ten centuries - from rotundas, proud gothic cathedrals, renaissance palaces, rich baroque churches up to the representative buildings in the style of "art nouveau" or in one of the other architectural styles of this century. At the beginning of the 19th century, Bernardo Bolzano counted 103 towers and spires in Prague and the town subsequently acquired the name "Prague of hundred spires". Now the number is estimated to be about 500. During one thousand years of Prague history, nature and architects have joined their forces to form a unique open-air gallery, the heart of which is shaped by its medieval disposition on both sides of the Vltava (Moldau) river. The inspired visitor should not be surprised during walks through Prague if he/she succeeds to spot the trails of one of its famous inhabitants. It could be Johannes Kepler in discussion with Tycho de Brahe, Golem - the first robot constructed by the Prague rabbi Loew, W.A. Mozart, Franz Kafka or Karel Capek. Ever-present tunes of Smetana and Dvorak give Prague a special touch. The narrow lanes of the Old Town, Charles Bridge, the magnificent panorama of Hradcany and the palaces of the Lesser Town invite one for a pleasant walk with an occasional stop at one of Prague's typical ale-houses and wine-taverns. Most tourists do not escape the temptation for a bit of shopping when passing elegant shop-windows with attractive traditional goods (crystal, records or hand-crafted products) or open-air markets. Today, Prague has a population of roughly 1.3 million and it covers an area of almost 500 square kilometers. It is on the same latitude as Bonn, Cracow or the southermost point of Great Britain (50 North). The average annual temperature is 9.3 degrees of Celsius (about 18 degrees in summer, and 0 in winter). It is probable that in January the town will get a soft cap of snow. Prague has 3 opera houses, 3 large concert halls, more than 20 theaters, plenty of small music clubs, 17 museums and 10 permanent galleries. Places of highest tourist interest are on the Royal Route running from the Powder Tower through Celetna Street, Old Town Square across Charles Bridge through the Lesser Town up to the Hradcany Castle. One should not miss the Jewish Town, the National Gallery with fine collection of Czech Gothic art, representative collections of European old art as well as a beautiful collection of French art assembled with exquisite taste. ----------------------------------------------------------------- Organization Organization Committee Chairpersons Vladimir Marik (Czech Republic) Olga Stepankova (Czech Republic) Organization Committee Members Marcela Bezouskova (Czech Republic) Marie Duzi (Czech Republic) Jitka Espandrova (Czech Republic) Marcus Herzog (Austria) Dusan Husek (Czech Republic) Ludmila Kolarova (Czech Republic) Lenka Lhotska (Czech Republic) Jaroslav Pokorny (Czech Republic) Katrin Seyr (Austria) Wolfgang Slany (Austria) Open Problems Bernhard Thalheim (Germany) Program Committee Chairpersons Georg Gottlob (Austria) Moshe Vardi (USA) Program Committee Members Paolo Atzeni (Italy) Jan Van den Bussche (Belgium) Stefano Ceri (Italy) Jan Chomicki (USA) Janos Demetrovics (Hungary) Georg Gottlob (Austria) Stephane Grumbach (France) Ravi Krishnamurthy (USA) Georg Lausen (Germany) Heikki Mannila (Finland) Marina Moscarini (Italy) Jaroslav Pokorny (Czech Republic) Doron Rotem (USA) Joachim Schmidt (Germany) Odet Shmueli (Israel) Letitia Tanca (Italy) Bernhard Thalheim (Germany) Mars Valiev (Russia) Moshe Vardi (USA) Gottfried Vossen (Germany) Peter Widmayer (Switzerland) -------------------------------------------------------------- ICDT '95 Registration Form Mail to: Katrin Seyr email: seyr@vexpert.dbai.tuwien.ac.at ----------------------- cut here ----------------------------- Name:.......................................................... Affiliation:................................................... Address:....................................................... Country:....................................................... Phone:...................Fax:.................................. Email:......................................................... Member of GI/EATCS (mention one):.............................. Membership No:................................................. Credit Card No:................Expiration date:................ Please mark the fees you are paying: Note: If you mark the "university affiliate" fee below, you have to provide your university address above. If you want to take advantage of the student fee, you have to prove your status by including a university certificate. ---------------------------------------------------------------------- |registration postmarked | before or on Dec. 10 | after Dec. 10 | |and fee sent | | | |--------------------------------------------------------------------- |members or | | | |university affiliates | ___ ATS 4.200 | ___ ATS 5.000 | |others | ___ ATS 4.500 | ___ ATS 5.200 | |students | ___ ATS 2.500 | ___ ATS 2.800 | ---------------------------------------------------------------------- |Hotel Krystal | ___ ATS 500 for single room per day | | from ___ to ___ | ___ ATS 700 for double room per day | ---------------------------------------------------------------------- |additional concert & dinner ___ ATS 500 No. of tickets: ___ | ---------------------------------------------------------------------- Total amount paid: _________________________ ATS Please indicate method of payment: _______ payment by Credit Card _______ payment made by bank transfer (see Methods of Payment); date of transfer: _________ ------------------------ cut here ---------------------------------- ICDT '95 Scholarship Application Mail to: Katrin Seyr email: seyr@vexpert.dbai.tuwien.ac.at ------------------------ cut here ---------------------------------- Name:............................................................... Date of Birth:...................................................... Citizenship:........................................................ Affiliation and Status:............................................. Attendance to the conference from _______________ to _______________ Current Interest and Experience in the Field: .................................................................... .................................................................... .................................................................... .................................................................... .................................................................... .................................................................... .................................................................... .................................................................... .................................................................... .................................................................... .................................................................... I apply for a scholarship providing free participation in ICDT '95. Date: ___________ Note: A scholarship can only cover the conference fee, and the accommodation but neither travel nor living expenses. --------------------------- end include file ----------------------------- From abitebou@calvados.inria.fr Mon Nov 28 12:35:14 1994 Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by lirmm.lirmm.fr (8.6.9/8.6.4) with ESMTP id MAA07728; Mon, 28 Nov 1994 12:35:13 +0100 Received: from cosmos.inria.fr (cosmos.inria.fr [128.93.11.30]) by concorde.inria.fr (8.6.9/8.6.9) with ESMTP id MAA14216; Mon, 28 Nov 1994 12:34:39 +0100 Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by cosmos.inria.fr (8.6.8/8.6.6) with ESMTP id MAA05970 for ; Mon, 28 Nov 1994 12:34:22 +0100 Received: from calvados.inria.fr (calvados.inria.fr [128.93.11.59]) by concorde.inria.fr (8.6.9/8.6.9) with ESMTP id MAA14201 for ; Mon, 28 Nov 1994 12:34:21 +0100 Received: (from abitebou@localhost) by calvados.inria.fr (8.6.8/8.6.6) id MAA28279; Mon, 28 Nov 1994 12:34:19 +0100 Date: Mon, 28 Nov 1994 12:34:19 +0100 From: Serge Abiteboul Message-Id: <199411281134.MAA28279@calvados.inria.fr> To: bd3@calvados.inria.fr Subject: International Conference on Database Theory Reply-to: Serge.Abiteboul@inria.fr (Serge Abiteboul) Status: R 5th International Conference on Database Theory (ICDT) Program Prague, Czech Republic January 10-13, 1995 Invitation to ICDT '95 ICDT '95 is an international conference on theoretical aspects of databases. As ICDT '92 (Berlin) this conference follows two series of conferences on database theory that were formed in parallel by different scientific communities in Europe. The first series, known as International Conference on Database Theory, was initiated in Rome in 1986, and continued in Bruges (1988) and Paris (1990). The second series, known as Symposium on Mathematical Fundamentals of Database Systems, was initiated in Dresden (1987), and continued in Visegrad (1989) and Rostock (1991). ICDT is held bi-annually. ******************************************************************* Highlights ******************************************************************* Invited Talks Data on Air: An Introduction to Wireless and Mobile Computing, Tomasz Imielinski, Rutgers University USA Mobile and wireless computing is a new emerging computing paradigm posing many challenging data-management problems on the border of computing and communication. We provide a brief introduction to wireless technology, identify new research challenges and investigate their technical significance. New research problems emerge due to mobility of users, narrow wireless bandwidth and limitations of battery power. Some of these problems may be of interest to the theoretical community and with this focus in mind we discuss in more detail: energy-efficient data management, management of location-dependent data, frequent disconnections and their impact on consistency of data, and organization and access to wireless data broadcast. Tomasz Imielinski is an Associate Professor at the Department of Computer Science, Rutgers University in New Brunswick, NJ, USA. He has received his PhD from the Polish Academy of Science (Warsaw) in 1982. He is the author of over 60 papers in the areas of database management systems, mobile and wireless computing and artificial intelligence. His current interests include database mining and mobile wireless computing. He is a principle investigator of the DataMan project at Rutgers University, involving data management issues in mobile computing. Dr. Imielinski has served on numerous program committees and was a general chairman of the ACM SIGMOD Conference. Spatial Databases, the Final Frontier, Jan Paredaens, University of Antwerp, Belgium During the last decade the need to manage two- and three-dimensional information has grown substantially. Although a lot of effort has been put in applications and implementations, the fundamental results in this field are still scarce. An overview is given of different possible data models to handle spatial information. Recent results are discussed. Finally a number of new promissing research topics in this area are given. Jan Paredaens studied mathematics and computer science at the University of Brussels and got a Ph. D. in 1974. He was a research member at Philips Lab in Brussels and became a full professor at the University of Antwerp in 1979. He is also associated with the Technical University of Eindhoven, The Netherlands. At these Universities he has research and educational positions in databases and fundamental aspects of computer sience. Prof. Dr. J. Paredaens is the author of five books in computer science, mainly on programming languages and databases. He also published about 100 papers in international journals, conferences and workshops. His research activities are mainly focused on properties of relational and object-oriented databases, expressive power of query and update languages, visual interfaces for information processing and spatial databases. He has been a member of the program committee of numerous international conferences and is involved in several international scientific journals. Tutorials Parallel Database Systems, Gerhard Weikum University of the Saarland, Saarbruecken, Germany Parallel database technology has evolved to a point where commercial systems appear to be fairly mature. Algorithms and run-time mechanisms for both speeding up query response time and scaling up transaction throughput are well understood. However, using a parallel database system effectively under real application workloads poses a number of complex optimization problems with respect to query processing policies, data placement, and resource management. These policy issues are still largely unexplored, from a theoretical as well as a practical perspective. This tutorial will give an overview of the state of the art in parallel database technology, and will point out important avenues of further research. Gerhard Weikum is a full professor in the Department of Computer Science of the University of the Saarland at Saarbruecken, Germany, where he is leading a research group on database systems and information systems. Former affiliations include the Department of Computer Science at the Swiss Federal Institute of Technology (ETH) Zurich, Switzerland, and the Microelectronics and Computer Technology Corporation (MCC) at Austin, Texas. At ETH Zurich, Dr. Weikum was leading the COMFORT project which involved building a self-tuning database system with capabilities for automatic data placement in parallel and distributed storage systems, adaptive load control, and the tuning of inter- versus intra-transaction parallelism. Dr. Weikum is an associate editor of ACM Transactions on Database Systems, and he has served on the program committee of several international conferences. Languages for Polynomial-time Queries -- an Ongoing Quest, Phokion Kolaitis During the past twenty years, a major direction of research in database theory has focused on the development of progressively more powerful languages for relational queries. Much of the work in this area has concentrated on the problem of finding languages that capture exactly the queries that are computable in polynomial-time in the size of the database. The quest for such languages has resulted in an extensive interaction between database theory, finite-model theory, and computational complexity. Although satisfactory answers have been obtained in certain important special cases, a solution to the general problem remains elusive. The aim of this tutorial is to describe some of the main results obtained so far and to present a status report on this problem. Phokion G. Kolaitis is an associate professor of Computer and Information Sciences at the University of California, Santa Cruz, U.S.A. His research interests include finite- model theory, computational complexity, and database theory. He is currently serving on the editorial boards of the Chicago Journal of Theoretical Computer Science and the Journal of Logic and Computation. In 1993 he was awarded a John Simon Guggenheim Memorial Foundation Fellowship. ********************************************************************* ICDT '95 is organized by Faculty of Electrical Engineering, Czech Technical University of Prague; Christian Doppler Laboratorium fuer Expertensysteme Wien, Vienna University of Technology; ICDT '95 cooperates with Arbeitsgruppe EMISA (2.5.2) der Gesellschaft fuer Informatik (GI) e.V.; European Association for Theoretical Computer Science (EATCS); Institute of Computer Science of the Academy of Science of the Czech Republic; The Joint Center of CTU Prague and FAW Linz; Charles University, Prague; A Best Student Paper Award was granted to ICDT '95 by The Extending Database Technology (EDBT) Foundation ICDT '95 is sponsored by International Thomson Publishing UK; IDOMENEUS Network Esprit Network of Excellence; COMPULOG NET Network of Excellence in Computational Logic; Christian Doppler Laboratorium fuer Expertensysteme; For further information contact Dr. Marcela Bezouskova Dept. of Control Engineering Faculty of Electrical Engineering Czech Technical University Karlovo nam. 13 CZ - 12135 PRAGUE 2 phone: +42 2 295664 or +42 2 24357488 fax: +42 2 290159 e-mail: k335@lab.felk.cvut.cz ------------------------------------------------------------------ Scientific Program Tuesday, January 10, 1995 ------------------------- Registration: 10.00--20.00 Tutorial I: 14.00--16.00 Parallel Database Systems, Gerhard Weikum Coffee Break Tutorial II: 16.30--18.30 Languages for Polynomial-time Queries -- an Ongoing Quest, Phokion Kolaitis 20.30 Informal get together Wednesday, January 11,1995 -------------------------- Invited Lecture I: 9.00-10.00 Chair: Moshe Vardi Data on Air: An Introduction to Wireless and Mobile Computing, Tomasz Imielinski Coffee Break Session 1: Optimization 10.20--11.20 Chair: Jaroslav Pokorny Distributed Query Optimization in Loosly Coupled Multidatabase Systems, Silvio Salza, Giovanni Barone, Tadeusz Morzy On the Complexity of Generating Optimal Left-Deep Processing Trees with Cross Products, Sophie Cluet, Guido Moerkotte Session 2: Nonmonotonic Semantics I 11.30--12.30 Chair: Victor Marek Querying Disjunctive Database Through Nonmonotonic Logics, Piero A. Bonatti, Thomas Eiter DATALOG Queries with Stratified Negation and Choice: from P to D^P, Sergio Greco, Domenico Sacca, Carlo Zaniolo Lunch Break Session 3: Query Languages I 14.15--15.45 Chair: Mars K. Valiev On the Kolmogorov Complexity of Boolean Query Languages, Jerzy Tyszkiewicz On Two Forms of Structural Recursion, Dan Suciu, Limsoon Wong Delta-Languages for Sets and sub-PTIME Graphs Transformers, Vladimir Sazonov, Alexei Lisitsa Coffee Break Session 4: Concurrency Control 16.15--17.45 Chair: Gottfried Vossen Partial Strictness in Two-Phase Locking, Eljas Soisalon-Soininen, Tatu Yloenen Unified Transaction Model for Semantically Rich Operations, Radek Vingralek, Haiyen Ye, Yuri Breitbart, Hans-J"org Schek The Dynamic Two Phase Commitment (D2PC) Protocol, Yoav Raz Dinner Break Open Problems Session 20.15 open ended Chair: Bernhard Thalheim Thursday, January 12, 1995 -------------------------- Session 5: Query Languages II 9.00--10.30 Chair: Jan Van den Bussche Domain-independent Queries on Databases with External Functions, (Best Student Paper) Dan Suciu An Algebra for Pomsets, Stephane Grumbach, Tova Milo On the Power of Stratified Logic Programs with Value-Invention for Expressing Database Transformations, Luca Cabibbo Coffee Break Session 6: Advanced Models 11.00--12.30 Chair: Georg Lausen A Stable Model Semantics for Behavioral Inheritance in Deductive Object Oriented Languages, Michele Bugliesi, Hassan M. Jamil A Rewriting Technique for the Analysis and the Optimization of Active Databases, Danilo Montesi, Riccardo Torlone Sorted HiLog: Sorts in Higher-Order Logic Data Languages, Weidong Chen, Michael Kifer Lunch Break Session 7: Probabilistic Methods 14.15--15.45 Chair: Thomas Eiter Average Keys and Functional Dependencies in Random Databases, Janos Demetrovics, G.O.H. Katona, D. Miklos, Oleg Seleznjev, Bernhard Thalheim Uniformly-Distributed Random Generation of Join Orders, Cesar A.Galindo-Legaria, Arjan Pellenkoft, Martin L. Kersten A Probabilistic View of Datalog Parallelization, Sergio Lifschitz, Victor Vianu Coffee Break Session 8: Constraints and Dependencies 16.15--17.45 Chair: Bernhard Thalheim A First Step Towards Implementing Dynamic Algebraic Dependencies, Nicole Bidoit, S. De Amo Constraint-Generating Dependencies, Marianne Baudinet, Jan Chomicki, Pierre Wolper Optimization Using Tuple Subsumption, Venky Harinarayan, Ashish Gupta Concert and Dinner Friday, January 12, 1995 ------------------------ Invited Lecture II: 9.00--10.00 Chair: Georg Gottlob Spatial Databases, the Final Frontier, Jan Paredaens Coffee Break Session 9: Nonmonotonic Semantics II 10.20--11.20 Chair: Carlo Zaniolo Deterministic and Non-Deterministic Stable Model Semantics for Unbound DATALOG Queries, Domenico Sacca Revision programming, database updates and integrity constraints, Victor W. Marek, Miroslav Truszcynski Session 10: Datalog Analysis 11.30--12.30 Chair: Foto Afrati Some Positive Results for Boundedness of Multiple Recursive Rules, Ke Wang Increment Boundedness and Nonrecursive Incremental Evaluation of Datalog Queries, Guozhu Dong, Jianwen Su Lunch Break Session 11: Query Languages III 14.15--15.45 Chair: Stephane Grumbach Approximation in Databases, Leonid Libkin Datalog Queries over Set Constraint Databases, Peter Z. Revesz Space Usage in Functional Query Languages, Serge Abiteboul, Gerd Hillebrand Conference End -------------------------------------------------------------------- General Information * Location The Conference will be held in Hotel Krystal, J. Martiho 2, Prague 6 - Veleslavin, Phone: +42 2 3162761, Fax: +42 2 3164215. Accommodation in this hotel is available and is highly recommended by the organizers. The hotel can be reached as follows. From the City Center Take subway line A until the terminal stop "Dejvicka", then take tram number 2 or 26 or bus 119 on Evropska street in the direction of the airport and get out at stop "Koospol". From the train station Take line C to Museum, then change to line A until the terminal stop Dejvicka, then take tram number 2 or 26 or bus 119 on Evropska street in the direction of the airport and get out at stop Koospol. From the Airport Either take a taxi (approximately 300 Crowns) or take bus number 119 to the stop "Koospol" * Language The official conference language is English; no simultaneous translation will be provided. * Proceedings The conference proceedings will appear as a volume of the Lecture Notes in Computer Science (LNCS) series, published by Springer-Verlag, and will be available at the conference. Each registered participant will receive a copy of the proceedings (except for students). After the conference, the proceedings of ICDT '95 will be available from your local bookstore. * Special Events We plan to hold an informal get-together party on Tuesday, January 10, 1995. It will start at the conference location site at 20.30. On Thursday evening, conference participants are invited to join a concert of Czech Chamber Music followed by a conference dinner. Transportation will be provided and the events are covered by the conference fee. The price for additional tickets is ATS 500 (see registration form). * Open Problems Session There will be an "Open Problems Session" where participants can illustrate open problems in database theory. The session will be chaired by Bernhard Thalheim. Participants who would like to present open problems may submit a short description of their problem in LaTeX to him (thalheim@informatik.tu-cottbus.de). The problems presented during the problems session will be summarized by Bernhard Thalheim and presented after ICDT to a larger community. * Registration Procedure People wishing to attend the conference should fill out the enclosed registration form and return it together with the proper payment to the address below. E-mail registration with credit card payment (VISA, EuroCard, MasterCard) is strongly prefered. Katrin Seyr ICDT'95 Dept. of Information Systems Vienna Univ. of Technology Paniglgasse 16 A - 1040 VIENNA Phone: +43 1 58801 6112 Fax: +43 1 5055304 Email: seyr@vexpert.dbai.tuwien.ac.at It is suggested to register for the conference at your earliest convenience. As soon as both registration form and fees have been received, a written or email confirmation will be sent. Please make sure that your society affiliation (membership number) and/or university affiliation are shown on your registration form, or that proof of your full-time student status comes together with it. Otherwise, a discount on the conference fee cannot be granted. A separate form must be completed by each participant. Registration by phone, fax or email is acceptable only if the applicable payment is transmitted in parallel (VISA, MasterCard and EuroCard). On--site registration will be available at the conference office during ICDT '95, starting Tuesday, January 10, 10.00 am. Registration Desk and Conference Office opening hours Tuesday, January 10: 10.00 -- 20.00 Wednesday, January 11: 8.00 -- 18.00 Thursday, January 12: 9.00 -- 17.00 Friday, January 13: 9.00 -- 15.00 Fees Since the financial situation for participants from universities and public research labs is usually more difficult than for those employed by an industrial enterprise, we charge the latter a slightly higher conference fee. Members of GI and its sister associations can take advantage of a fee reduction due to the financial backup provided by this organization. conference fees ---------------------------------------------------------------------- |registration postmarked | before or on Dec. 10 | after Dec. 10 | |and fee sent | | | |--------------------------------------------------------------------- |members of GI, EATCS and | ATS 4.200 | ATS 5.000 | |university affiliates | | | |others | ATS 4.500 | ATS 5.200 | |students | ATS 2.500 | ATS 2.800 | ---------------------------------------------------------------------- The conference fee includes admission to all sessions including the two tutorials, a copy of the proceedings (not included in the student fee), refreshments during the breaks and the special events. Please note that ATS 100 correspond to aproximately US$ 9 or DM 14. --------------------------------------------------------------------- | | Single | Double | --------------------------------------------------------------------- |Rooms at the Hotel Krystal per day | ATS 500.- | ATS 700.- | --------------------------------------------------------------------- Other hotels can be booked through the local agency by contact Dr. Marcela Bezouskova by email (k335@lab.felk.cvut.cz) or fax (+42 2 290159). A Special Note for East-European Participants A limited number of free participations for people from Eastern Europe (free conference attendance and accommodation) will be offered. To become eligible for this support, please fill out the application you find elsewhere in this brochure and send it to Katrin Seyr by mail, fax, or email before December 1, 1994. Methods of Payment All fees including hotel fees for Hotel Krystal have to be paid in Austrian currency (ATS) either by * credit card (mail to Katrin Seyr) * bank transfer (free of charges for us, please) to the following account: Bank: Creditanstalt Bank Code: 11000 Account No.: 0964-35110/00 Receiver: ICDT'95 European participants can make their payments using a Eurocheque written in the applicable amount in Austrian Shillings (ATS); in that case, please do not forget to include your Eurocheque card number on the back. Registrations for which no payment is received within reasonable time will not be accepted. Cancellation and Refund Cancellations must be made in written form to Katrin Seyr. If a cancellation notification is received before December 10, 80% of the fees will be refunded; no refunds will be made thereafter. For registered participants who cannot attend, the proceedings will be mailed after the conference. * Hotel Information and Meals The organizers recommend the Hotel Krystal for accommodation. The Hotel Krystal is a hotel partially owned by the Prague Universities and offers very convenient rates. The hotel meets the *** standard. Participants wishing to make a reservation for a hotel with higher standards please contact Dr. Marcela Bezouskova from the organizing committee by email or fax. Except for the Conference Dinner meals are not included in the conference fee. However, cheap lunch tickets for the Hotel self-service restaurant can be purchased in Czech crowns at the conference registration desk. In addition, there are two other small restaurants in the hotel. There is an exchange office in the lobby of the Hotel Krystal. * About Prague Prague, the capital of the Czech Republic, is considered to be one of the most beautiful cities in Europe. Its magical atmosphere is determined by the happy and tolerant coexistence of the buildings, sculptures and monuments of ten centuries - from rotundas, proud gothic cathedrals, renaissance palaces, rich baroque churches up to the representative buildings in the style of "art nouveau" or in one of the other architectural styles of this century. At the beginning of the 19th century, Bernardo Bolzano counted 103 towers and spires in Prague and the town subsequently acquired the name "Prague of hundred spires". Now the number is estimated to be about 500. During one thousand years of Prague history, nature and architects have joined their forces to form a unique open-air gallery, the heart of which is shaped by its medieval disposition on both sides of the Vltava (Moldau) river. The inspired visitor should not be surprised during walks through Prague if he/she succeeds to spot the trails of one of its famous inhabitants. It could be Johannes Kepler in discussion with Tycho de Brahe, Golem - the first robot constructed by the Prague rabbi Loew, W.A. Mozart, Franz Kafka or Karel Capek. Ever-present tunes of Smetana and Dvorak give Prague a special touch. The narrow lanes of the Old Town, Charles Bridge, the magnificent panorama of Hradcany and the palaces of the Lesser Town invite one for a pleasant walk with an occasional stop at one of Prague's typical ale-houses and wine-taverns. Most tourists do not escape the temptation for a bit of shopping when passing elegant shop-windows with attractive traditional goods (crystal, records or hand-crafted products) or open-air markets. Today, Prague has a population of roughly 1.3 million and it covers an area of almost 500 square kilometers. It is on the same latitude as Bonn, Cracow or the southermost point of Great Britain (50 North). The average annual temperature is 9.3 degrees of Celsius (about 18 degrees in summer, and 0 in winter). It is probable that in January the town will get a soft cap of snow. Prague has 3 opera houses, 3 large concert halls, more than 20 theaters, plenty of small music clubs, 17 museums and 10 permanent galleries. Places of highest tourist interest are on the Royal Route running from the Powder Tower through Celetna Street, Old Town Square across Charles Bridge through the Lesser Town up to the Hradcany Castle. One should not miss the Jewish Town, the National Gallery with fine collection of Czech Gothic art, representative collections of European old art as well as a beautiful collection of French art assembled with exquisite taste. ----------------------------------------------------------------- Organization Organization Committee Chairpersons Vladimir Marik (Czech Republic) Olga Stepankova (Czech Republic) Organization Committee Members Marcela Bezouskova (Czech Republic) Marie Duzi (Czech Republic) Jitka Espandrova (Czech Republic) Marcus Herzog (Austria) Dusan Husek (Czech Republic) Ludmila Kolarova (Czech Republic) Lenka Lhotska (Czech Republic) Jaroslav Pokorny (Czech Republic) Katrin Seyr (Austria) Wolfgang Slany (Austria) Open Problems Bernhard Thalheim (Germany) Program Committee Chairpersons Georg Gottlob (Austria) Moshe Vardi (USA) Program Committee Members Paolo Atzeni (Italy) Jan Van den Bussche (Belgium) Stefano Ceri (Italy) Jan Chomicki (USA) Janos Demetrovics (Hungary) Georg Gottlob (Austria) Stephane Grumbach (France) Ravi Krishnamurthy (USA) Georg Lausen (Germany) Heikki Mannila (Finland) Marina Moscarini (Italy) Jaroslav Pokorny (Czech Republic) Doron Rotem (USA) Joachim Schmidt (Germany) Odet Shmueli (Israel) Letitia Tanca (Italy) Bernhard Thalheim (Germany) Mars Valiev (Russia) Moshe Vardi (USA) Gottfried Vossen (Germany) Peter Widmayer (Switzerland) -------------------------------------------------------------- ICDT '95 Registration Form Mail to: Katrin Seyr email: seyr@vexpert.dbai.tuwien.ac.at ----------------------- cut here ----------------------------- Name:.......................................................... Affiliation:................................................... Address:....................................................... Country:....................................................... Phone:...................Fax:.................................. Email:......................................................... Member of GI/EATCS (mention one):.............................. Membership No:................................................. Credit Card (mark one) ____ VISA ____ EuroCard ____ MasterCard Credit Card No:................Expiration date:................ Please mark the fees you are paying: Note: If you mark the "university affiliate" fee below, you have to provide your university address above. If you want to take advantage of the student fee, you have to prove your status by including a university certificate. ---------------------------------------------------------------------- |registration postmarked | before or on Dec. 10 | after Dec. 10 | |and fee sent | | | |--------------------------------------------------------------------- |members or | | | |university affiliates | ___ ATS 4.200 | ___ ATS 5.000 | |others | ___ ATS 4.500 | ___ ATS 5.200 | |students | ___ ATS 2.500 | ___ ATS 2.800 | ---------------------------------------------------------------------- |Hotel Krystal | ___ ATS 500 for single room per day | | from ___ to ___ | ___ ATS 700 for double room per day | ---------------------------------------------------------------------- |additional concert & dinner ___ ATS 500 No. of tickets: ___ | ---------------------------------------------------------------------- Total amount paid: _________________________ ATS Please indicate method of payment: _______ payment by Credit Card _______ payment made by bank transfer (see Methods of Payment); date of transfer: _________ ------------------------ cut here ---------------------------------- ICDT '95 Scholarship Application Mail to: Katrin Seyr email: seyr@vexpert.dbai.tuwien.ac.at ------------------------ cut here ---------------------------------- Name:............................................................... Date of Birth:...................................................... Citizenship:........................................................ Affiliation and Status:............................................. Attendance to the conference from _______________ to _______________ Current Interest and Experience in the Field: .................................................................... .................................................................... .................................................................... .................................................................... .................................................................... .................................................................... .................................................................... .................................................................... .................................................................... .................................................................... .................................................................... I apply for a scholarship providing free participation in ICDT '95. Date: ___________ Note: A scholarship can only cover the conference fee, and the accommodation but neither travel nor living expenses.