Generating plans from proofs
We present algorithms for answering queries making use of information about source integrity constraints, access restrictions, and access costs. Our method can exploit the integrity constraints to find plans even when there is no direct access to relations appearing in the query. We look at differen...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Published: |
Association for Computing Machinery
2016
|
| _version_ | 1797102830815805440 |
|---|---|
| author | Benedikt, M Tsamoura, E Cate, B |
| author_facet | Benedikt, M Tsamoura, E Cate, B |
| author_sort | Benedikt, M |
| collection | OXFORD |
| description | We present algorithms for answering queries making use of information about source integrity constraints, access restrictions, and access costs. Our method can exploit the integrity constraints to find plans even when there is no direct access to relations appearing in the query. We look at different kinds of plans, depending on the kind of relational operators that are permitted within their commands. To each type of plan we associate a semantic property that is necessary for having a plan of that type. The key idea of our method is to move from a search for a plan to a search for a proof of the corresponding semantic property, and then generate a plan from a proof. We provide algorithms for converting proofs to plans, and show that they will find a plan of the desired type whenever such a plan exists. We show that while discovery of one proof allows us to find a single plan that answers the query, we can explore alternative proofs to find lower-cost plans. |
| first_indexed | 2024-03-07T06:11:22Z |
| format | Journal article |
| id | oxford-uuid:ef9dcf13-fcde-43cc-91d2-30b03010c409 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T06:11:22Z |
| publishDate | 2016 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | oxford-uuid:ef9dcf13-fcde-43cc-91d2-30b03010c4092022-03-27T11:41:30ZGenerating plans from proofsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:ef9dcf13-fcde-43cc-91d2-30b03010c409Symplectic Elements at OxfordAssociation for Computing Machinery2016Benedikt, MTsamoura, ECate, BWe present algorithms for answering queries making use of information about source integrity constraints, access restrictions, and access costs. Our method can exploit the integrity constraints to find plans even when there is no direct access to relations appearing in the query. We look at different kinds of plans, depending on the kind of relational operators that are permitted within their commands. To each type of plan we associate a semantic property that is necessary for having a plan of that type. The key idea of our method is to move from a search for a plan to a search for a proof of the corresponding semantic property, and then generate a plan from a proof. We provide algorithms for converting proofs to plans, and show that they will find a plan of the desired type whenever such a plan exists. We show that while discovery of one proof allows us to find a single plan that answers the query, we can explore alternative proofs to find lower-cost plans. |
| spellingShingle | Benedikt, M Tsamoura, E Cate, B Generating plans from proofs |
| title | Generating plans from proofs |
| title_full | Generating plans from proofs |
| title_fullStr | Generating plans from proofs |
| title_full_unstemmed | Generating plans from proofs |
| title_short | Generating plans from proofs |
| title_sort | generating plans from proofs |
| work_keys_str_mv | AT benediktm generatingplansfromproofs AT tsamourae generatingplansfromproofs AT cateb generatingplansfromproofs |