Projects per year

## Abstract

A query Q has a bounded rewriting using a set of views if there exists a query Q′ expressed in the same language as Q, such that given a dataset D, Q(D) can be computed by Q′ that accesses only cached views and a small fraction D

This paper studies the problem for deciding whether a query has a bounded rewriting given a set V of views and a set A of access constraints. We establish the complexity of the problem for various query languages, from Σ

_{Q}of D. We consider datasets D that satisfy a set of access constraints, a combination of cardinality constraints and associated indices, such that the size |D_{Q}| of D_{Q}and the time to identify D_{Q}are independent of |D|, no matter how big D is.This paper studies the problem for deciding whether a query has a bounded rewriting given a set V of views and a set A of access constraints. We establish the complexity of the problem for various query languages, from Σ

^{p}_{3}-complete for conjunctive queries (CQ), to undecidable for relational algebra (FO). We show that the intractability for CQ is rather robust even for acyclic CQ with fixed V and A, and characterize when the problem is in PTIME. To make practical use of bounded rewriting, we provide an effective syntax for FO queries that have a bounded rewriting. The syntax characterizes a core subclass of such queries without sacrificing the expressive power, and can be checked in PTIME.Original language | English |
---|---|

Title of host publication | PODS '16 Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems |

Publisher | ACM Press |

Pages | 107-119 |

Number of pages | 13 |

ISBN (Print) | 978-1-4503-4191-2 |

DOIs | |

Publication status | Published - 2016 |

Event | 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems - San Francisco, United States Duration: 26 Jun 2016 → 1 Jul 2016 http://sigmod2016.org/ |

### Conference

Conference | 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems |
---|---|

Abbreviated title | SIGMOD PODS 2016 |

Country | United States |

City | San Francisco |

Period | 26/06/16 → 1/07/16 |

Internet address |