Extremal Separation Problems for Temporal Instance Queries
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917687320379392 |
|---|---|
| author | Jung, Jean Christoph Ryzhikov, Vladislav Wolter, Frank Zakharyaschev, Michael |
| author_facet | Jung, Jean Christoph Ryzhikov, Vladislav Wolter, Frank Zakharyaschev, Michael |
| contents | The separation problem for a class Q of database queries is to find a query in Q that distinguishes between a given set of `positive' and `negative' data examples. Separation provides explanations of examples and underpins the query-by-example paradigm to support database users in constructing and refining queries. As the space of all separating queries can be large, it is helpful to succinctly represent this space by means of its most specific (logically strongest) and general (weakest) members. We investigate this extremal separation problem for classes of instance queries formulated in linear temporal logic LTL with the operators conjunction, next, and eventually. Our results range from tight complexity bounds for verifying and counting extremal separators to algorithms computing them. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_03511 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Extremal Separation Problems for Temporal Instance Queries Jung, Jean Christoph Ryzhikov, Vladislav Wolter, Frank Zakharyaschev, Michael Databases Logic in Computer Science I.2.4; F.2.2 The separation problem for a class Q of database queries is to find a query in Q that distinguishes between a given set of `positive' and `negative' data examples. Separation provides explanations of examples and underpins the query-by-example paradigm to support database users in constructing and refining queries. As the space of all separating queries can be large, it is helpful to succinctly represent this space by means of its most specific (logically strongest) and general (weakest) members. We investigate this extremal separation problem for classes of instance queries formulated in linear temporal logic LTL with the operators conjunction, next, and eventually. Our results range from tight complexity bounds for verifying and counting extremal separators to algorithms computing them. |
| title | Extremal Separation Problems for Temporal Instance Queries |
| topic | Databases Logic in Computer Science I.2.4; F.2.2 |
| url | https://arxiv.org/abs/2405.03511 |