Anastasia Ailamaki, Ecole Polytechnique Federale de Lausanne (EPFL) in Switzerland
April 12, 2011, Tuesday: 9:00 – 10:30
Location: Niedersachsen Halle B
As the number of compute elements per chip increases exponentially, embarrassingly parallel hardware calls for embarrassingly scalable database applications on chip multiprocessors. Despite that database systems have long optimized for parallel execution, however, known methods are of bounded utility in harvesting scalable performance from the available raw parallelism. Common sense is often contradicted; for instance, increasing on-chip cache size or aggressively sharing data among processors is often detrimental to performance. As the number of hardware contexts grows, favoring scalability over single-thread performance leads to higher overall gains.
This talk presents lessons learned when trying to scale database workloads on chip multiprocessors. When transforming a database storage manager from a single-threaded Atlas into a multi-threaded Lernaean Hydra which scales to infinity, major rethinking of basic constructs at all system levels is in order. At the system level, choosing a mechanism to access critical sections becomes crucial: spinning wastes cycles, while blocking incurs high overhead. When processing transactions, concurrency needs to be converted into parallelism – a challenging task, even for transactional workloads that are inherently concurrent. Often, parallelism needs to be extracted from seemingly serial operations; extensive research in distributed systems proves to be very useful in this context. When processing queries, service-oriented architectures provide an excellent framework to exploit available parallelism. The tradeoffs and trends in the above research directions will be discussed using examples from the StagedDB/CMP and ShoreMT projects at EPFL.
Anastasia Ailamaki has received a B.Sc. degree in Computer Engineering from the Polytechnic School of the University of Patra, Greece (1990), M.Sc. degrees from the Technical University of Crete, Greece (1993) and from the University of Rochester, NY (1996), and a Ph.D. degree in Computer Science from the University of Wisconsin-Madison (2000). In 2001 she joined the Computer Science Department at Carnegie Mellon University, first as an assistant and then as an associate professor. In 2008 she joined the Ecole Polytechnique Federale de Lausanne (EPFL) in Switzerland as a full professor, where she is Director of the Data-Intensive Applications and Systems (DIAS) Laboratory. Her research interests are in the broad area of database systems and applications, with emphasis on database system behavior on modern processor hardware and disks. She is interested in building systems to strengthen the interaction between the database software and the underlying hardware and I/O devices, including flash technology. In addition, she works on automating database design and computational database support for scientific applications. Past interests include storage device modeling and performance prediction and internet query caching.
Anastasia has received a Sloan Research Fellowship (2005), six best-paper awards (VLDB 2001, Performance 2002, VLDB PhD Workshop 2003, ICDE 2004, FAST 2005, and ICDE 2006 (demo)), an NSF CAREER award (2002), and IBM Faculty Partnership awards in 2001, 2002, and 2003. In 2007, she received a Finmeccanica endowed chair from the Computer Science Department at Carnegie Mellon, and a European Young Investigator Award from the European Science Foundation. She is a member of IEEE and ACM, and has also been a CRA-W mentor.
Georg Gottlob, University of Oxford, UK
April 13, 2011, Wednesday: 9:00 – 10:30
Location: Niedersachsen Halle B
Ontological queries are evaluated against an enterprise ontology rather than directly on a database. The evaluation and optimization of such queries is an intriguing new problem for database research. In this paper we discuss two important aspects of this problem: query rewriting and query optimization. Query rewriting consists of the compilation of an ontological query into an equivalent query against the underlying relational database. The focus here is on soundness and completeness. We review previous results and present a new rewriting algorithm for rather general types of ontological constraints (description logics). In particular, we show how a conjunctive query (CQ) against an enterprise ontology can be compiled into a union of conjunctive queries (UCQ) against the underlying database. Ontological query optimization, in this context, attempts to improve this process so to produce possibly small and cost-effective output UCQ. We review existing optimization methods, and propose an effective new method that works for Linear Datalog, a description logic that encompasses well-known description logics of the DL-Lite family.
Georg Gottlob is a Professor of Computing Science at Oxford University and an Adjunct Professor at TU Wien. His interests include data extraction, database theory, graph decomposition techniques, AI, knowledge representation, logic and complexity. More recently, Gottlob has been interested in ontology-enhanced databases and ontological query-answering. He and his co-workers have introduced the Datalog+/- language family that uses Datalog variants for uniformly expressing both ontological rules and database integrity constraints. Gottlob has received the Wittgenstein Award from the Austrian National Science Fund, is an ACM Fellow, an ECCAI Fellow, a Fellow of the Royal Society, and a member of the Austrian Academy of Sciences, the German National Academy of Sciences, and the Academia Europaea. He chaired the Program Committees of IJCAI 2003 and ACM PODS 2000, was the Editor in Chief of the Journal Artificial Intelligence Communications, and is currently a member of the editorial boards of journals, such as CACM and JCSS. He is the main founder of Lixto, a company that provides tools and services for web data extraction. Gottlob was rexcently awarded an ERC Advanced Investigator's Grant.
Johannes Gehrke, Cornell University, USA
April 14, 2011, Thursday: 9:00 – 10:30
Location: Niedersachsen Halle B
Scalability is a fundamental problem in the development of computer games and massively multiplayer online games (MMOs). Players always demand more --- more polygons, more physics particles, more interesting AI behavior, more monsters, more simultaneous players and interactions, and larger virtual worlds.
Most game developers think of databases as persistence solutions, designed to store and read game state. But the advantages of database systems go way beyond persistence. Database research has dealt with the question of efficiently processing declarative languages, and the resulting research questions have touched many areas of computer science.
In this talk, I will show how the idea of declarative processing from databases can be applied to computer games and simulations. I will then discuss how we can use ideas from optimistic concurrency control to scale interactions between players in MMOs, and I will conclude by describing how we can use these techniques to build elastic transaction processing infrastructure for the cloud.
Johannes Gehrke is a Professor in the Department of Computer Science at Cornell University and an Adjunct Associate Professor at the University of Tromsø in Norway. Johannes' research interests are in the areas of database systems and data mining. With Raghu Ramakrishnan, he co-authored the undergraduate textbook Database Management Systems (McGrawHill, 2002), currently in its third edition. Johannes has received a National Science Foundation Career Award and an Arthur P. Sloan Fellowship, and he served as program co-chair of SIGKDD 2004 and VLDB 2007. From 2007 to 2008, he was Chief Scientist at FAST, A Microsoft Subsidiary, where he is still serving as technical advisor.