Generating Plans from Proofs

Generating Plans from Proofs

The Interpolation-based Approach to Query Reformulation

Michael Benedikt, Julien Leblay, Balder ten Cate, Efthymia Tsamoura
ISBN: 9781627059541 | PDF ISBN: 9781627059428
Copyright © 2016 | 205 Pages | Publication Date: March, 2016

BEFORE YOU ORDER: You may have Academic or Corporate access to this title. Click here to find out: 10.2200/S00703ED1V01Y201602DTM043


Ordering Options: Paperback $70.00   E-book $56.00   Paperback & E-book Combo $87.50

Why pay full price? Members receive 15% off all orders.
Learn More Here

Read Our Digital Content License Agreement (pop-up)

Purchasing Options:

Query reformulation refers to a process of translating a source query - a request for information in some high-level logic-based language - into a target plan that abides by certain interface restrictions. Many practical problems in data management can be seen as instances of the reformulation problem. For example, the problem of translating an SQL query written over a set of base tables into another query written over a set of views; the problem of implementing a query via translating to a program calling a set of database APIs; the problem of implementing a query using a collection of web services.

In this book we approach query reformulation in a very general setting that encompasses all the problems above, by relating it to a line of research within mathematical logic. For many decades logicians have looked at the problem of converting "implicit definitions" into "explicit definitions," using an approach known as interpolation. We will review the theory of interpolation, and explain its close connection with query reformulation. We will give a detailed look at how the interpolation-based approach is used to generate translations between logic-based queries over different vocabularies, and also how it can be used to go from logic-based queries to programs.

Table of Contents

Vocabulary-based Target Restrictions
Access Methods and Integrity Constraints
Reformulation Algorithms for TGDs
Low-cost Plans Via Proof Search
Authors' Biographies

About the Author(s)

Michael Benedikt, Oxford University
Michael Benedikt is Professor of Computer Science at Oxford University and a fellow of University College Oxford. He came to Oxford after a decade in U.S. industrial research laboratories, including positions as Distinguished Member of Technical Staff at Bell Laboratories and visiting researcher at Yahoo! Labs. He has worked extensively in mathematical logic, finite model theory, verification, database theory, and database systems, and has served as chair of the ACM's main database theory conference, Principles of Database Systems. The current focus of his research is Web data management, with recent projects including querying of the deep Web, querying and integration of annotated data, and querying of web services.

Julien Leblay, National Institute of Advanced Industrial Science and Technology (AIST)
Julien Leblay is a Research Scientist at the National Institute of Advanced Industrial Science and Technology (AIST) in Tokyo, Japan. As part of the Artificial Intelligence Research Center, his research interests encompass data management and query processing in general, with a particular focus on applications to Web data, i.e., data typical found on web services and Open Data repositories. From October 2013 to February 2015, Julien was a postdoctoral research assistant at the University of Oxford under the supervision of Michael Benedikt. During this period, his work covered query optimization under constraints
and access restrictions. Julien obtained his Ph.D. in Computer Science from the Université Paris-Sud and Inria, France, under the supervision of Francois Goasdoue and Ioana Manolescu. Prior to his academic career, he worked in industry for several years as a software engineer and consultant on topics ranging from machine translation to data integration.

Balder ten Cate, Google, Inc.
Balder ten Cate is a software engineeer at Google. He is also an Associate Adjunct Professor at UC Santa Cruz, where he is a member of the database research group and is currently advising two graduate students. Previously, he was a computer scientist at LogicBlox Inc, contributing to the development of a smart database system that combines transactions, analytics, planning, and business logic, powering a new class of smart enterprise applications. He was also a visiting researcher at INRIA, ENS de Cachan, and IBM Research – Almaden. Balder ten Cate received his Ph.D. from the University of Amsterdam for a thesis on the model theory of extended modal languages. His research interests are in data management and applications of logic in computer science.

Efthymia Tsamoura, Oxford University
Efthymia Tsamoura received her B.Sc. in 2007 and her Ph.D. in 2013 both from the computer science department of Aristotle University of Thessaloniki, Greece. Since 2013, Efthymia is a postdoctoral researcher in the computer science department of Oxford University. Her research interests lie in the fields of distributed query optimization, multi-objective query optimization, data integration, and query answering under constraints. Efthymia received several awards during both her undergraduate and postgraduate studies.

Browse by Subject
Case Studies in Engineering
ACM Books
SEM Books
0 items

Note: Registered customers go to: Your Account to subscribe.

E-Mail Address:

Your Name: