Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/49897
Title: The Relational Completeness of the DNA Query Language DNAQL
Authors: BRIJDER, Robert 
GILLIS, Joris 
VAN DEN BUSSCHE, Jan 
Issue Date: 2026
Publisher: ASSOC COMPUTING MACHINERY
Source: Acm Transactions on Database Systems, 51 (4) (Art N° 20)
Abstract: 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 article, we show that DNAQL is relationally complete, i.e., the full relational algebra can be performed by DNAQL programs.
Notes: Brijder, R (corresponding author), Eindhoven Univ Technol, M&CS Dept, Eindhoven, Netherlands.
r.brijder@tue.nl; joris.gillis@gmail.com; jan.vandenbussche@uhasselt.be
Keywords: Query languages;CCS Concepts: • Information systems → Relational database query languages;• Hardware → Biology- related information processing;molecular computing;• Theory of computation → Models of computation;relational algebra;Additional Key Words and Phrases: Query languages, molecular computing, relational algebra, DNA computing, relational completeness;DNA computing;relational completeness
Document URI: http://hdl.handle.net/1942/49897
ISSN: 0362-5915
e-ISSN: 1557-4644
DOI: 10.1145/3779650
ISI #: 001842592100001
Rights: 2026 Copyright held by the owner/author(s). This work is licensed under a Creative Commons Attribution 4.0 International License.
Category: A1
Type: Journal Contribution
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
3779650.pdfPublished version445.57 kBAdobe PDFView/Open
Show full item record

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.