2025/03/23 by Fletcher, George, Wood, Peter, Yakovets, Nikolay
#Databases (cs.DB) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2503.18214
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× L→ ℕ where δ(Q1, Q2) represents the length of a shortest path between queries Q1 and Q2 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.