Logic and Database Theory Prof. Dr. Nicole Schweikardt

Logic in Computer Science, Dept. of Computer Science, Humboldt-University Berlin

Research:

Processing huge data sets has emerged to a major challange for computer science — last but not least due to the fact that external memory has become an extremely cheap resource in recent years. Huge data sets occur in many application areas, for example in collections of research results (e.g., medical databases such as medline and swiss-prot), in the form of sensor data, or in stock tickers. Often, data is not available in the form of a classical database, but only in semistructured form, e.g., as XML document. Such semistructured data can be represented in a natural way by trees. Due to size of the data, a computer's main memory might be too small to hold a tree representation of all the data. Therefore, at any point in time, only a small fraction of the data is available in main memory, whereas the major amount of data solely resides in external memory. In many applications we even have the situation that data is only available bit by bit, in the form of a data stream. One such application, for example, is a stock ticker that constantly produces new data items. For efficiently processing such data, new techniques, extending those known from classical relational databases, need to be developed. Our logic and database theory research group investigates the foundations of processing huge, semistructured data, with an emphasis on the following topics: query optimisation, properties of query languages, and complexity theory for huge data set processing. In the following, some details on these topics are given. Complexity Theory for Huge Data Set Processing:  Information theory and communication complexity of problems impose bounds on the efficiency of processing large data sets. Aims of this research project are to develop machine models and complexity classes for classifying the resources necessary for processing huge data sets and data streams, and to prove lower bounds on the costs produced by external memory accesses that are inherently necessary for solving certain problems. Properties of Query Languages:  This research project's aim is to investigate properties (such as, e.g., expressive power, succinctness, evaluation complexity, and complexity of the query containment problem) of various query languages. Some of these aspects are already well-understood for node selecting languages such as XPath or Monadic Datalog. However, for data transformation languages, which allow the formulation of considerably more complex queries, e.g., joins, these aspects are far from being solved. Query Optimisation:  Relational database management systems usually use algebraic and cost based methods to rewrite queries into equivalent queries that can be evaluated more efficiently. The aim of this research project is to develop methods for optimising queries against semistructured data such as, e.g., XML documents. A key task is to investigate, how schema information, i.e. information on the structure of the data, can be used for query optimisation. The Logic and Database Theory group is supported by the German Research Foundation (DFG).

Staff:

Head: Prof. Dr. Nicole Schweikardt   Secretary: Birgit Eisenmann   Research Assistant: Dipl.-Inf. André Hernich   Student: André Böhm

Publications:

André Hernich Nicole Schweikardt

Teaching:

Summer 2007: Logic and Complexity Course (Monday 1-3 p.m., room 1'305 and Wednesday 3-5 p.m., room 1'307, Erwin Schrödinger-Zentrum) Exercises in Logic and Complexity (Monday 3-5 p.m., room 1'305, Erwin Schrödinger-Zentrum) Research Seminar Logic in Computer Science (usually Fridays, 11 a.m. - 1 p.m., room 4.410, Johann von Neumann-Haus) Seminar ("Oberseminar") Theoretical Computer Science (usually Fridays, 1-3 p.m., room 3.101, Johann von Neumann-Haus) Teaching in previous terms

Links:

Conferences and Workshops: IEEE Symposium on Logic in Computer Science (LICS) 22nd Annual IEEE Symposium on Logic in Computer Science (LICS'07) 34th International Colloquium on Automata, Languages and Programming (ICALP'07) 26th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS'07) 11th International Conference on Database Theory (ICDT'07) 2006 Federated Logic Conference (FLoC'06) Seminar on Circuits, Logic, and Games, Schloss Dagstuhl, 8.-10. November 2006 Workshop on Algorithms for Data Streams, IIT Kanpur, Indien, 18.-20. Dezember 2006 Research groups: Logic and Database Theory at Humboldt-University Berlin (Prof. Dr. Nicole Schweikardt) Logic in Computer Science at Humboldt-University Berlin (Prof. Dr. Martin Grohe) Logic and Discrete Systems at Humboldt-University Berlin (Prof. Dr. Stephan Kreutzer) Database Group at Saarland University (Prof. Dr. Christoph Koch) Logic in Computer Science at Dortmund University (Prof. Dr. Thomas Schwentick) Laboratory for Foundations of Computer Science, School of Informatics, University of Edinburgh, Edinburgh Theoretical Computer Science, Department of Mathematics and Computer Science, Johannes Gutenberg-University, Mainz (Prof. Dr. Clemens Lautemann) Miscellaneous: Leonid Libkin's Database Principles Column of SIGMOD Record

Contact:

Prof. Dr. Nicole Schweikardt Humboldt-Universität zu Berlin Institut für Informatik Arbeitsgruppe Logik und Datenbanktheorie Unter den Linden 6 10099 Berlin Phone: +49-30-2093 3086       Secretary:   +49-30-2093 3080 Fax: +49-30-2093 3081 E-Mail:   schweika@informatik.hu-berlin.de Url: http://www.informatik.hu-berlin.de/~schweika

Location: Johann von Neumann-Haus Raum 4.426 (Haus 4, 4. Stock) Rudower Chaussee 25 12489 Berlin (Adlershof) How to find this