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

Browse archivesActive forum topics 
Recent comments
19 hours 27 min ago
1 day 2 hours ago
1 day 12 hours ago
1 day 14 hours ago
2 days 13 hours ago
2 days 16 hours ago
2 days 17 hours ago
2 days 17 hours ago
2 days 19 hours ago
2 days 22 hours ago