Is there a completeness property for query languages (like SQL, Cypher, Datalog, etc) that is analogous to Turing completeness in programming languages? I wondered if it is something like being able to describe any subset of the facts in the database.

  • $\begingroup$ stackoverflow.com/questions/900055/… $\endgroup$ – Evil May 11 '18 at 19:51
  • 1
    $\begingroup$ Chapter 18 of Foundations of Databases by Abiteboul, Hull, and Vianu discusses the relationship between the expressive power of various (theoretical) query languages and specifically highly expressive languages that are "complete" for queries (in a sense they define). $\endgroup$ – Derek Elkins May 12 '18 at 0:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.