Prolog's resolution engine is more about logical inference - it will happily backtrack through different paths to find solutions.

What Graham proved specifically was about relational databases: if you try to maintain consistent joins across all possible paths (aka "join consistency"), it becomes an NP-complete problem. The "Universal Relation Problem" requires ALL possible join paths to give consistent results.

Prolog doesn't have verify consistency across an exponential number of join path, so I fail to see how it is a "universal relation" system.