User loginNavigation 
Looking for references on the expressiveness and computational completeness of a relational programming languageThe basic operations of a relational query language are equivalent to first order predicate calculus, which means they fall short of being computationally complete. This applies equally to modern SQL excluding SQL/PSM (which adds a procedural language) as it did to Codd's original proposals. I have created a language Andl which implements the relational algebra augmented by (a) the ability to compute new values that are not in any relation (b) ad hoc aggregation functions (c) ordered queries (like SQL windowing) and (d) recursive fixpoint queries (equivalent to transitive closure or SQL Recursive Common Table Expressions. I speculate that without any explicit looping or branching constructs, and based on relations as the only holder of state, that this language is Turing Complete. At any event it is capable of a surprising range of interesting computations (such as a Sudoku solver). I am looking for references or theoretical work, or other implementations, to pursue this question. By davidb at 20160819 11:40  LtU Forum  previous forum topic  next forum topic  other blogs  4779 reads

Browse archivesActive forum topics 
Recent comments
16 hours 8 min ago
22 hours 59 min ago
1 day 2 hours ago
1 day 3 hours ago
1 day 5 hours ago
1 day 20 hours ago
2 days 44 min ago
5 days 7 hours ago
1 week 2 days ago
1 week 2 days ago