zbMATH — the first resource for mathematics

Fundamentals of physical design and query compilation. (English) Zbl 1238.68004
Synthesis Lectures on Data Management 18. San Rafael, CA: Morgan & Claypool Publishers (ISBN 978-1-60845-278-1/pbk; 978-1-60845-279-8/ebook). xiii, 110 p. (2011).
This book presents, in terms of first-order logic (FOL), the fundamental methods used in database systems to solve query compilation. It consists of 6 chapters, one appendix on first-order logic and a bibliography.
Chapter 1 is a short introduction, which presents concepts of logical design, physical design and query compilation. Chapter 2, entitled Logic design and user queries, shows how the logical design for a database and user queries can be expressed in first-order logic. In the next chapter, Basic physical design and query plans, the authors present how the physical design can be represented in FOL and introduces a plan language, which consists of eight operators used to represent the query plans. Chapter 4illustrates how the plan language and basic data structures can be combined with FOL constraints in order to encode complex data structures, algorithms and physical design artifacts. Chapter 5, Query compilation and plan synthesis, presents the most important techniques that solve the problem of query compilation, which consists in translating user queries to executable and efficient query plans for a given database’s physical design. The final chapter deals with the problem of database updates through update compilation.
The book contains numerous examples, which help understand the presented concepts. Each chapter ends with a bibliography and a list of exercises. The book is thus useful for both teaching and research purposes.

68-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science
68P15 Database theory
03B10 Classical first-order logic
Full Text: DOI