Fundamentals of Physical Design and Query Compilation

Query compilation is the problem of translating user requests formulated over purely conceptual and domain specific ways of understanding data, commonly called logical designs, to efficient executable programs called query plans. Such plans access various concrete data sources through their low-level often iterator-based interfaces. An appreciation of the concrete data sources, their interfaces and how such capabilities relate to logical design is commonly called a physical design. This book is an introduction to the fundamental methods underlying database technology that solves the problem of query compilation. The methods are presented in terms of first-order logic which serves as the vehicle for specifying physical design, expressing user requests and query plans, and understanding how query plans implement user requests. Table of Contents: Introduction / Logical Design and User Queries / Basic Physical Design and Query Plans / On Practical Physical Design / Query Compilation and Plan Synthesis / Updating Data

David Toman is an Associate Professor in the David R. Cheriton School of Computer Science at the University of Waterloo. His research focuses on database theory and systems, query processing under constraints and query compilation, as well as temporal aspects of data management, and logic in Computer Science, in general. Recently, he has been focusing on database schema languages based on Description Logic enriched with various forms of identification constraints. The languages investigated in this line of research are tailored to enabling compilation of queries formulated over a high-level conceptual schema to code that is executed over low-level physical layouts of data, such as records and pointer structures. He has published extensively in his research area including preparing invited contributions to several reference collections, such as the Encyclopedia of Database Systems and the Handbook of Temporal Reasoning in Artificial Intelligence. He earned Bachelor’s and Master’s degrees from the Masaryk University in Czechoslovakia in 1992 and a PhD from Kansas State University in 1996, all in Computer Science. He has been awarded numerous research grants, including the NATO-NSERC Postdoctoral fellowship and the Ontario Premier’s Research Excellence Award. Grant Weddell is an Associate Professor in the David R. Cheriton School of Computer Science at the University of Water[1]loo. His research interests fall generally in the area of databases, broadly interpreted, with a focus on the fundamental problems that surface when one combines high-level formatted data access, e.g., SQL queries on relational databases, with higher level transaction and client interaction models, e.g., models supporting “begin transaction” and “end transaction”, and/or more detailed temporal specifications of client interaction. He has a particular interest in databases with an underlying data source that corresponds to the contents of a main memory, and is particularly motivated by applications that involve embedded software that must support very high throughput or very low response time for data access and update. More recently, he has worked on description logics and ontology languages, query containment, and, more generally, semantic query optimization, constraint theory, including temporal constraints and logics, and algorithms and data structures relating to semantic search and tableau-based reasoning.