Database Seminar Series (2004-2005)

From the mid 1980s to the mid 1990s, a major theme in database theory was the study of Datalog, the language of logic programs without function symbols. Unfortunately, most decision problems involving Datalog turned out to be undecidable. Furthermore, well-behaved fragments of Datalog turned out to be rather restrictive and unnatural. Surprisingly, a natural and quite general fragment of Datalog did emerge in the mid 1990s, in the context of semistructured data. This fragment is the class of regular queries, whose basic element is that of regular path query. In his talk I will describe the class of regular queries and its well-behavedness in the context of view-based query processing.

The Shield system is a flexible framework that can prevent most piracy, preserve privacy, and allow even more flexibility than current systems provide (e.g., no regional zones for DVDs). The framework requires that the operating system and hardware protect the piracy detection software which performs episodic communications with a security infrastructure. The protocols are designed to prevent anyone from learning which software a user device has, even when the user device attempts to use pirated software.

Joint work with Michael Rabin

After graduating from Yale in 1977, he worked for IBM designing circuits and microcode for the 3090. He completed his Ph.D. at Harvard in 1984 (thesis advisor: Nat Goodman). Since he enjoys typing, he has written a few books: a professional reference book Database Tuning: principles, experiments, and troubleshooting techniques (2002, Morgan Kaufmann), three books about a mathematical detective named Dr. Ecco entitled The Puzzling Adventures of Dr. Ecco (1988, Freeman, and republished in 1998 by Dover), Codes, Puzzles, and Conspiracy (1992, Freeman), Dr. Ecco's Cyberpuzzles (2002, W. W. Norton), a book of biographies about great computer scientists called Out of Their Minds: the lives and discoveries of 15 great computer scientists (1995, Copernicus/Springer-Verlag), and Pattern Discovery in Biomolecular Data: Tools, Techniques, and Applications published in 1999 by Oxford University Press. In addition, he has co-authored thirty journal papers, 40 conference papers, and six patents. He writes a monthly puzzle column for Scientific American and Dr. Dobb's Journal.

This is joint work with Ninghui Li and Ji-Won Byun (CERIAS, Purdue University)

Her main research interests include security, privacy, database systems, object-oriented technology, multimedia systems. In those areas, Prof. Bertino has published more than 250 papers in all major refereed journals, and in proceedings of international conferences and symposia. Her research has been funded by severa; entities and organizations both in USA and Europe, including NSF, the European Union under the 5th and 6th Research Program Framework, IBM, Telcordia, Microsoft, the Italian Telecom. She is a co-author of the books "Object-Oriented Database Systems - Concepts and Architectures" 1993 (Addison-Wesley International Publ.), "Indexing Techniques for Advanced Database Systems" 1997 (Kluwer Academic Publishers), and "Intelligent Database Systems" 2001 (Addison-Wesley International Publ.). She is a co-editor in chief of the Very Large Database Systems (VLDB) Journal and a member of the advisory board of the IEEE Transactions on Knowledge and Data Engineering. She serves also on the editorial boards of several scientific journals, incuding IEEE Internet Computing, ACM Transactions on Information and System Security, IEEE Transactions on Secure and Dependable Computing, Journal, the Journal of Computer Security, Data & Knowledge Engineering, the International Journal of Cooperative Information Systems, Science of Computer Programming. She has been consultant to several Italian companies on data management systems and applications and has given several courses to industries. She is involved in several projects sponsored by the EU. She has served as Program Committee members of several international conferences, such as ACM SIGMOD, VLDB, ACM OOPSLA, as Program Co-Chair of the 1998 IEEE International Conference on Data Engineering (ICDE), as program chair of 2000 European Conference on Object-Oriented Programming (ECOOP 2000), as program chair of the 7th ACM Symposium of Access Control Models and Technologies (SACMAT 2002), and as program chair of the 2004 Extending Database Technology (EDBT 2004) Conference.

Elisa Bertino is a Fellow member of IEEE and a Fellow member of ACM and has been been named a Golden Core Member for her service to the IEEE Computer Society. She received the 2002 IEEE Computer Society Technical Achievement Award for "For outstanding contributions to database systems and database security and advanced data management systems".

In this talk, I will give an overview of some key small-space pseudo-random sketching techniques for effective query processing over streaming data. The focus will be on some of our own efforts in the area, including our very recent work on communication-efficient continuous query tracking over distributed data streams.

We exploit the different distributed data versions that naturally come about as a result of asynchronous data replication in order to increase concurrency by running conflicting transactions in parallel on different replicas. The two distributed versioning variations I will present have different concurrency versus transparency trade-offs. The first replication scheme avoids making any changes to the database or web server to support replication by implementing concurrency control and conflict avoidance in an intermediate scheduler tier. In the second scheme, the role of the scheduler tier is minimal, while the database tier is modified to closely integrate replication with fine-grained concurrency control.

Our evaluation of distributed versioning replication uses the TPC-W e-commerce benchmark. For small clusters of up to eight database replicas, we perform measurements of a web site implementing the TPC-W specification. We use simulation to extend our measurement results to larger clusters. We show close to ideal scaling for the most common e-commerce workload, the shopping mix, up to 8 database replicas in the experiments and good scaling to up to 60 database replicas in simulation.

The method of choice for top-k similarity queries is the TA family of threshold algorithms. Large disk-resident index lists for content terms and tag names strongly suggest using the TA variant with sorted access only for disk I/O efficiency. This method maintains score intervals for top-k candidates and performs a conservative threshold test based on upper bounds of candidate scores. The talk will present the TA-prob method which applies a probabilistic threshold test for fast approximation of top-k results. It is based on score predictors that compute convolutions of score distributions in the yet to be scanned tails of index lists. This methods provides an order of magnitude improvement in run-time at high and probabilistically controllable levels of precision and recall relative to the TA baseline.

TA-prob has been further enhanced to cope with ontology-based query expansion; by using a new incremental merge technique over index lists for expansion terms, it is much more efficient than the traditional techniques that expand queries before execution starts. TA-prob is also the major building block in the TopX search engine for XML data. TopX supports path conditions for all XPath axes as exact constraints and content term conditions as well as ontology-based relaxation of terms and tag names as similarity conditions for ranked retrieval.

Dr. Weikum's recent working areas include implementation, optimization, and self-organization aspects of distributed information systems such as peer-to-peer systems, dependable workflow management, and intelligent search and organization of semi-structured data on the Web and in intranets. Earlier he held positions at the University of the Saarland in Saarbruecken, Germany, ETH Zurich, Switzerland, with MCC in Austin, Texas, and he was a visiting senior researcher at Microsoft Research in Redmond, Washington.

Dr. Weikum has published more than 100 refereed articles in conferences and journals. He has written a textbook on Transactional Information Systems, jointly authored with Gottfried Vossen and published with Morgan Kaufmann. A paper on self-tuning load control for transaction processing systems that appeared in the 1992 VLDB conference has been awarded with the 2002 VLDB 10-year award for the most influential paper of the conference ten years ago.

Dr. Weikum has served on the editorial boards of various journals including ACM TODS, the premier scientific journal of the database research community, and IEEE-CS TKDE. He is president of the board of trustees of the VLDB Endowment, the steering committee of the International Conference on Very Large Data Bases, one of the two leading international conferences on database and information systems research. He has served on committees of numerous conferences in various roles, including the General co-chair of the 2nd Semiannual Conference on Innovative Data Systems Research (CIDR) in 2005, the PC chair of the ACM SIGMOD International Conference on Management of Data in 2004, the PC co-chair of the IEEE-CS International Conference on Data Engineering in 2000, and the organization of several Dagstuhl Seminars. Dr. Weikum was an invited tutorial speaker at the 5th International Conference on Database Theory (ICDT) in 1995, and an invited keynote speaker at the 6th International Conference on Extending Database Technology (EDBT) in 1998 and the 23rd International Conference on Conceptual Modeling in 2004, as well as the French, German, Indian, and Italian Database Conferences.

We present our algorithm for the case of unstructured systems, thus with minimal assumptions, so it could also apply to other P2P systems as well (DHT, super-peer). Our algorithm requires no global information, does not depend on the existence of certain peers and addresses the volatility of peers during query execution. We validated our algorithm through implementation over a 64-node cluster and simulation using the BRITE topology generator and SimJava. Our performance evaluation shows that our algorithm has logarithmic scale up and improves Top-n query response time very well using P2P parallelism.

Joint work with Reza Akbarinia and Esther Pacitti

Between 1999-2002, he was a professor of computer science at University Paris 6, on leave from INRIA. From 1989 to 1999, he led the Rodin group working on distributed database and multimedia technology. From 1995 to 2000, he also led Dyade, the R&D joint venture between Bull and INRIA to foster technology transfer in the areas of Internet (50 people). In Dyade, he contributed to the design and the transfer of the Disco (Distributed Information Search Component) prototype to the KelKoo startup. From 1985 to 1989, he was a senior scientist at Microelectronics and Computer Technology Corp. (MCC) in Austin, Texas. There he participated in the design and implementation of the Bubba parallel database system.

Patrick Valduriez has authored and co-authored over 140 technical papers and several books; among which, "Principles of Distributed Database Systems" published by Prentice Hall in 1991 and 1999 (2nd edition), "Object Technology" published by Thomson Computer Press in 1997, and “Relational Databases and Knowledge Bases” published by Addison-Wesley in 1990.

He has been a trustee of the VLDB endowment and an associate editor of several journals; including ACM Transactions on Database Systems, the VLDB Journal, Distributed and Parallel Databases, Internet and Databases: Web Information Systems, etc. He has also served as program chair of PDIS'93, SIGMOD'97, VLDB'98 (industrial program), VLDB'99 (European program). In 2004, he was the general chair of the ACM SIGMOD/PODS conference which was held in Paris (first time outside North America).