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

Browse archives
Active forum topics 
Recent comments
8 weeks 15 hours ago
8 weeks 19 hours ago
8 weeks 19 hours ago
30 weeks 2 days ago
34 weeks 3 days ago
36 weeks 1 day ago
36 weeks 1 day ago
38 weeks 5 days ago
43 weeks 3 days ago
43 weeks 3 days ago