Paper Info
Title
The Exact Complexity of the First-Order Logic Definability Problem.
Abstract
We study the definability problem for first-order logic, denoted by FO-Def. The input of FO-Def is a relational database instance I and a relation R; the question to answer is whether there exists a first-order query Q (or, equivalently, a relational algebra expression Q) such that Q evaluated on I gives R as an answer. Although the study of FO-Def dates back to 1978, when the decidability of this problem was shown, the exact complexity of FO-Def remains as a fundamental open problem. In this article, we provide a polynomial-time algorithm for solving FO-Def that uses calls to a graph-isomorphism subroutine (or oracle). As a consequence, the first-order definability problem is found to be complete for the class GI of all problems that are polynomial-time Turing reducible to the graph isomorphism problem, thus closing the open question about the exact complexity of this problem. The technique used is also applied to a generalized version of the problem that accepts a finite set of relation pairs, and whose exact complexity was also open; this version is also found to be GI-complete.
Year
DOI
Venue
2016
10.1145/2886095
ACM Trans. Database Syst.
Keywords
Field
DocType
Definability problem, expressiveness, first-order logic, relational algebra
Finite set,Open problem,Existential quantification,Relational database,Computer science,Decidability,First-order logic,Relational algebra,Graph isomorphism problem,Database
Journal
Volume
Issue
ISSN
41
2
0362-5915
Citations 
PageRank 
References 
1
0.35
0
Authors
2
Name
Order
Citations
PageRank
Marcelo Arenas12618193.91
Gonzalo I. Diaz2292.72