>> Datalog /happens/ to be a subset of Prolog syntactically, but their semantics are very different. An analogy is how LL parsers and LR parsers can both parse context free grammars, but their properties are different -- LL parsers parse from "top down" and thus will not halt on left-recursive grammars (just like Prolog) while LR parsers parse from "bottom up" and can support left-recursive grammars, at the cost of increased space.
You have to be careful when you're talking about "semantics" because there's a difference between the semantics of a language and the semantics of its execution. Like you say, Datalog is normally evaluated bottom-up, with what we call a TP Operator. If a Datalog program is evaluated top-down, like a Prolog program, then it's not guaranteed to terminate. On the flip side, Prolog is normally evaluated by SLD-Resolution, implemented as a Depth-First Search with backtracking and so it can get stuck in loops on left-recursions, as you say very correctly, but it can also be evaluated by SLG-Resolution, implemented as Breadth-First Search with memoization (a.k.a. tabling) in which case it _doesn't_ get stuck in loops on left-recursions.
In short, no I wouldn't agree that Datalog "happens" to be a subset of Prolog syntactically. That's what it is, by design. Evaluation is a different matter.
And this is where we get into the discussion of trade-offs.
>> Note that the demand transformation / magic set optimization, which is a common optimization, closes the gap between Datalog and Prolog semantically. In particular, it gives Datalog the best of both worlds: (1) increased speed, because it is not computing all possible facts, just the ones "reachable" from the query (like Prolog) and also (2) termination guarantee because all programs in the base Datalog language terminate.
Well I'm not sure whether that's right because I'm not sure what are the two "worlds" we get the best of. Efficiency is one thing. When you say that Datalog is not computing all facts, I understand this as saying it doesn't have to ground the Herbrand base of a logic program, like ASP has to, for example. True.
But the important trade-off (in my opinion anyway) is between efficiency and completeness, which is another way to look at termination guarantees, a.k.a. decidability. If a language, under some inference rule, is decidable, then it is not complete. And that's the limitation with Datalog, which comes from the fact it's a function-free language [1]. Without functions there is much you can't do. For example, function free Datalogs can't have lists, the main data structure in Prolog (other than well, "terms") because the Prolog list-constructor operator ([Head|Tail]) is a function. Without functions you can't do integer arithmetic. And so on.
I'm not sure how Datalog systems deal with those limitations (I don't really work with Datalog). I suspect they bolt-on some extra-logical system to do e.g. arithmetic, pretty much like Prolog does. In any case, the limitations of Datalog are I guess the reason it's popular as a database query language, because you don't really need arithmetic, or lists, in a database query language. But recursion, that terminates, is nice to have.
Btw, if you have a reference to the creation of Datalog older than the one I linked to, please share it. I've been trying to find the "original" datalog reference for a while and couldn't. I have no idea at this point who, exactly, came up with it, and how.
___________________
[1] Prolog is not function free, but calls its functions "terms". Which is very confusing because it also calls everything else a "term"; including constants, which it calls "atoms", and literals, i.e. atoms and negations of atoms. If you're lost, that's because you should. Prolog is a terminological atrocity.