5 ms·

How does this compare to a pure, recursion-free subset of Prolog? Not counting cosmetic differences, e.g., in Prolog, relation arguments are positional, whereas

How does this compare to a pure, recursion-free subset of Prolog? Not counting cosmetic differences, e.g., in Prolog, relation arguments are positional, whereas in the relational model, attributes have names.

rntz 10y ago
Prolog allows unification, which doesn't have a parallel in relational algebra. I'm not sure how much more power this gives you without recursion, though. If you're interested in connections between relational algebra (and SQL, and databases) and logic programming, you should look at Datalog, which is a restricted subset of Prolog that is akin to relational algebra plus fixed points (transitive closure, for example). In particular, Datalog forbids compound terms (like lists) and recursion in a negated position. I think Datalog without recursion/fixed-points is precisely as powerful as relational algebra, but I don't have a proof handy.
- catnaroek 10y ago
  Computing natural joins requires unification.
  - rntz 10y ago
    Natural joins only require equality testing. General unification is stronger. Prolog can unify [X,3|T] with [2,Y,4,5] to find X = 2, Y = 3, T = [4,5], for example.
    - catnaroek 10y ago
      What you're talking about requires compound data types in the first place (e.g., lists in your example), whereas in the relational model, attributes are normally assumed to range over primitive types. But, even in the absence of compound data types, the answer to a Prolog query may contain free variable, whereas the answer to SQL query may not. So you do have a point.
- yellowflash 10y ago
  First order logic can express precisely what relational algebra can express. And what Datalog represents is First order logic with least fixed point, in case if there is linear order on the data (cells), it could represent P-solvable problems. https://en.wikipedia.org/wiki/Descriptive_complexity_theory https://en.wikipedia.org/wiki/Descriptive_complexity_theory
eru 10y ago
You mean datalog? (You don't need to be recursion free. Just restrict your recursion very carefully.)
- catnaroek 10y ago
  It was intended to be a slightly snarky remark: “Oh, you tell me you implemented a subset of what Prolog can already do out of the box?” But apparently, it wasn't interpreted by others as such. :-|
  - eru 10y ago
    Oh, restriction to a carefully chosen subset can be a feature all by itself. Eg for data interchange compare json vs evaluating any random javascript expression. The latter is strictly more powerful than the former. The former is better. Or an example in the other direction: imagine Haskell-Prime, like Haskell, but you can mutate every variable. Strictly more powerful, but awful. (Or imagine adding GOTO to your favourite programming language.)
    - catnaroek 10y ago
      > Strictly more powerful, but awful. Wrong. The power of Haskell mostly comes from how easy it is to reason about code. Your proposed Haskell-Prime would be less powerful in this sense.
      - eru 10y ago
        I think we are in violent agreement.

rntz 10y ago

Prolog allows unification, which doesn't have a parallel in relational algebra. I'm not sure how much more power this gives you without recursion, though. If you're interested in connections between relational algebra (and SQL, and databases) and logic programming, you should look at Datalog, which is a restricted subset of Prolog that is akin to relational algebra plus fixed points (transitive closure, for example). In particular, Datalog forbids compound terms (like lists) and recursion in a negated position. I think Datalog without recursion/fixed-points is precisely as powerful as relational algebra, but I don't have a proof handy.

catnaroek 10y ago
Computing natural joins requires unification.
- rntz 10y ago
  Natural joins only require equality testing. General unification is stronger. Prolog can unify [X,3|T] with [2,Y,4,5] to find X = 2, Y = 3, T = [4,5], for example.
  - catnaroek 10y ago
    What you're talking about requires compound data types in the first place (e.g., lists in your example), whereas in the relational model, attributes are normally assumed to range over primitive types. But, even in the absence of compound data types, the answer to a Prolog query may contain free variable, whereas the answer to SQL query may not. So you do have a point.
yellowflash 10y ago
First order logic can express precisely what relational algebra can express. And what Datalog represents is First order logic with least fixed point, in case if there is linear order on the data (cells), it could represent P-solvable problems. https://en.wikipedia.org/wiki/Descriptive_complexity_theory https://en.wikipedia.org/wiki/Descriptive_complexity_theory

eru 10y ago

You mean datalog? (You don't need to be recursion free. Just restrict your recursion very carefully.)

catnaroek 10y ago
It was intended to be a slightly snarky remark: “Oh, you tell me you implemented a subset of what Prolog can already do out of the box?” But apparently, it wasn't interpreted by others as such. :-|
- eru 10y ago
  Oh, restriction to a carefully chosen subset can be a feature all by itself. Eg for data interchange compare json vs evaluating any random javascript expression. The latter is strictly more powerful than the former. The former is better. Or an example in the other direction: imagine Haskell-Prime, like Haskell, but you can mutate every variable. Strictly more powerful, but awful. (Or imagine adding GOTO to your favourite programming language.)
  - catnaroek 10y ago
    > Strictly more powerful, but awful. Wrong. The power of Haskell mostly comes from how easy it is to reason about code. Your proposed Haskell-Prime would be less powerful in this sense.
    - eru 10y ago
      I think we are in violent agreement.