Translating Relational Queries into Iterative Programs

این کتاب با استفاده از روش‌ها و تکنیک‌هایی از حوزه‌های برنامه‌نویسی تابعی و تبدیل برنامه، مشکل ترجمه پرس‌و‌جوهای رابطه‌ای را به برنامه‌های تکراری بررسی می‌کند. بخش اول دو الگوریتم را ارائه می‌کند که برنامه‌های تکراری را از مشخصات پرس و جو مبتنی بر جبر تولید می‌کنند. در حالی که الگوریتم اول مبتنی بر تبدیل برنامه های بازگشتی است، الگوریتم دوم از عبارات تابعی برای تولید فرم تکراری نهایی استفاده می کند. در بخش دوم، همین تکنیک ها برنامه های کارآمدی را برای ارزیابی توابع کل در سیستم های پایگاه داده رابطه ای ایجاد می کنند. در چندین مرحله، برنامه‌هایی که پس از مرتب‌سازی، تجمیع را انجام می‌دهند، به برنامه‌هایی تبدیل می‌شوند که در حین مرتب‌سازی، تجمع را انجام می‌دهند. بخش سوم سپس Lisp-Dialect T را به عنوان یک زبان پیاده سازی ممکن برای سیستم های پایگاه داده بررسی می کند. این کتاب تمام تحولات را با قوانین تبدیل توصیف می کند. خواننده می‌تواند انتظار یک برخورد رسمی از تبدیل‌های پیشنهادی را داشته باشد که مبنایی برای اثبات درستی الگوریتم‌ها فراهم می‌کند و در عین حال، بینش مهمی در مورد تکنیک‌ها و روش‌های توسعه‌یافته برای تبدیل ارائه می‌دهد. علاوه بر این، توصیف سطح بالا و دقیق الگوریتم‌ها بلافاصله به پیاده‌سازی آنها منجر می‌شود و به گسترش آنها اجازه می‌دهد تا نیازهای جدید را برآورده کنند. به طور کلی، استفاده از قوانین تبدیل و روش های تبدیل، رویکرد جدیدی را برای پردازش پرس و جو در سیستم های پایگاه داده رابطه ای معرفی می کند.

This book investigates the problem of translating relational queries into iterative programs using methods and techniques from the areas of functional programming and program transformation. The first part presents two algorithms which generate iterative programs from algebra-based query specifications. While the first algorithm is based on the transformation of recursive programs, the second uses functional expressions to generate the final iterative form. In the second part the same techniques generate efficient programs for the evaluation of aggregate functions in relational database systems. In several steps, programs which perform aggregation after sorting, are transformed into programs which perform aggregation while sorting. The third part then investigates the Lisp-dialect T as a possible implementation language for database systems. The book describes all transformations by transformation rules. The reader can expect a formal treatment of the proposed transformations which provide the basis for proving the correctness of the algorithms and, at the same time, give important insight into the techniques and methods developed for the transformation. Additionally, the high-level, detailed description of the algorithms immediately leads to their implementation and allows their extension to meet new requirements. Overall, the use of transformation rules and transformation methods introduces a new approach to query processing in relational database systems.