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  4458 reads

Browse archivesActive forum topics 
Recent comments
1 hour 4 min ago
1 hour 41 min ago
1 hour 48 min ago
4 hours 55 min ago
7 hours 39 min ago
8 hours 57 min ago
9 hours 34 min ago
9 hours 50 min ago
10 hours 5 min ago
10 hours 23 min ago