3 ms·
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 y
by 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 agoComputing natural joins requires unification.
- rntz 10y agoNatural 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 agoWhat 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 agoFirst 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