The Relational Completeness of the DNA Query Language DNAQL

DNAQL is a query language for databases implemented as DNA molecules in solution, with well-known DNA wetlab procedures as operators. DNAQL focusses on faithful implementability in DNA, and, as a result, does not include powerful, but difficult to implement, features like nonterminating/recursive hybridization needed for general computation (i.e., Turing-completeness). In this paper we show that DNAQL is relationally complete, i.e., the full relational algebra can be performed by DNAQL programs.