On the feasibility of semantic query metrics
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915211398610944 |
|---|---|
| author | Fletcher, George Wood, Peter Yakovets, Nikolay |
| author_facet | Fletcher, George Wood, Peter Yakovets, Nikolay |
| contents | We consider the problem of defining semantic metrics for relational database queries. Informally, a semantic query metric for a query language $L$ is a metric function $δ:L\times L\to \mathbb{N}$ where $δ(Q_1, Q_2)$ represents the length of a shortest path between queries $Q_1$ and $Q_2$ in a graph. In this graph, nodes are queries from $L$, and edges connect semantically distinct queries where one query is maximally semantically contained in the other. Since query containment is undecidable for first-order queries, we focus on the simpler language of conjunctive queries. We establish that defining a semantic query metric is impossible even for conjunctive queries. Given this impossibility result, we identify a significant subclass of conjunctive queries where such a metric is feasible, and we establish the computational complexity of calculating distances within this language. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_18214 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the feasibility of semantic query metrics Fletcher, George Wood, Peter Yakovets, Nikolay Databases We consider the problem of defining semantic metrics for relational database queries. Informally, a semantic query metric for a query language $L$ is a metric function $δ:L\times L\to \mathbb{N}$ where $δ(Q_1, Q_2)$ represents the length of a shortest path between queries $Q_1$ and $Q_2$ in a graph. In this graph, nodes are queries from $L$, and edges connect semantically distinct queries where one query is maximally semantically contained in the other. Since query containment is undecidable for first-order queries, we focus on the simpler language of conjunctive queries. We establish that defining a semantic query metric is impossible even for conjunctive queries. Given this impossibility result, we identify a significant subclass of conjunctive queries where such a metric is feasible, and we establish the computational complexity of calculating distances within this language. |
| title | On the feasibility of semantic query metrics |
| topic | Databases |
| url | https://arxiv.org/abs/2503.18214 |