Видео

This is what I was looking for. Are they even worth learning?

The practical examples come later in the course. Neo4j is one type of graph database discussed further on to study its implementation of knowledge graphs.

It is dry material but I found the 3 views of property graphs to be very interesting.

Right, so let me answer to the second two paragraphs first. Your idea of what P-hard for data complexity (and Exp-hard for combined complexity) means seem to be correct. The actual rules that are used to put this into practice mimic the computation of a Turing machine in Datalog. For the most part, this is not too hard (we often describe Turing machine computations using rule-like statements anyway, as in "if the machine is in state q and sees symbol a, then it changes to state p, writes a b, and moves to the left"). To make this work in Datalog, the main idea is that the relational structure (database) that gets computed should look like a "trace" of the TM run: the tape (memory) will be a chain-like structure where every element is a cell, and we will have a new tape for every moment in time (so every time point, from start to end, is in the model). The challenge is to come up with a good encoding for things like "cell 23 at time step 42". If the computation is not too long (polynomial), we can simply assume that the relevant coordinates (like "23" and "42") are given to us with the input and we merely create pairs of them during the computation. That's the idea for the P-hardness proof. If we want to show Exp-hardness, we need to create a lot more "cells" in some way. The idea for doing this is to use facts with long lists of parameters (e.g., if I have 10 parameters in a predicate and 2 constants, I can already represent 2^10 facts). Indeed, the number of facts one can get is exponential, but the exponent is given by the arity of predicates. For Exp-hardness, the input should determine the exponent, so the arity of predicates must grow if we want to process larger input instances. This is why this is no longer "data complexity". Other than this complication (which turns "addresses" of cells into lists of constants), the rules that describe the actual Turing machine behaviour are basically the same as in the PTime case. If you want a more formal explanation, the complete Datalog programs needed for these encodings can be found in a 2001 survey paper "Complexity and Expressive Power of Logic Programming" by Evgeny Dantsin and colleagues. It should be easy to find and free to access online. Now to the first question. It is really true and there is no error in the video here. Datalog is P-complete for data complexity, yet there are problems over databases that can be decided in PTime but not with a Datalog program. A simple example of the latter would be: "Find out if the database does not contain the fact q(a)". There is nothing contradictory in this situation. P-hardness (for data complexity) just means that we could find a "cheap" reduction from any problem in P to Datalog query answering (with a fixed rule set). The ability (or, as it is here, non-ability) to express all problems in a complexity class directly (without any reduction) is known as the *descriptive complexity* of a database query language. If we can express all problems in P with a query language, then we say that the language *captures P*. As for Datalog, it does not capture P, but what it captures is still difficult enough to be P-hard. If we want to capture P, we can do that by adding some more features: input negation and successor ordering. I have some more details on these in my course on database theory (iccl.inf.tu-dresden.de/web/Database_Theory_(SS2022)/en Lecture "Datalog Complexity"). A more detailed explanation of what "expressing" a query in a query language is given in our work "Capturing Homomorphism-Closed Decidable Queries with Existential Rules" (Camille Bourgeaux et al. , it's about a different query language, but the introduction to expressivity applies to Datalog just the same).

@@knowledge-basedsystemstudr9413 > If the computation is not too long (polynomial), [...] Right, I think I understand. I think we could do the same in a less direct way: the Cook-Levin theorem (3-SAT is NP-Complete) builds a boolean circuit bounded in space and time which simulates a polynomial-time Turing machine. Instead of asking "is there an input such that <blah>" we're asking "is <blah> for this particular input", since we're working with deterministic p-time TMs. I think I can figure out how to convert logic gates to Datalog. We could also reduce directly from the circuit value problem (which is P-complete). I guess the datalog is something like: canOutput(GATE, true) :- hasType(GATE, and), hasInput(GATE, X), hasInput(GATE, Y), canOutput(X, true), canOutput(Y, true). canOutput(GATE, true) :- hasType(GATE, or), hasInput(GATE, X), canOutput(X, true). canOutput(GATE, false) :- hasType(GATE, and), hasInput(GATE, X), canOutput(X, false). canOutput(GATE, false) :- hasType(GATE, or), hasInput(GATE, X), hasInput(GATE, Y), canOutput(X, false), canOutput(Y, false). [canOutput if hasType(_, not) is left as an exercise.] ... and then the reduction on "true and not true" produces: canOutput(gensym1, true). canOutput(gensym2, true). hasType(gensym3, not). hasInput(gensym3, gensym2). hasType(gensym4, and). hasInput(gensym4, gensym1). hasInput(gensym4, gensym3). ... and this database can be computed in log space by walking over the input string repeatedly. Maybe I need to insist that the circuit is presented in a way that's easy (enough) to parse. Since no input value canOutput both true and false, it follows that no gate can output both true and false, and thus by induction canOutput(the circuit's output gate, true) is in the database iff the circuit value is true, so that shall be the query. [The "fixpoint of (database <- database union stuff-we-can-derive-in-one-step)" then is the wavefront of evaluated gates, terminating once all gates have been evaluated.] Also, upon thinking about it I now understand my initial confusion: emptiness of the answer set (the criterion used in reductions) is not the same as an arbitrary predicate about the database being true. [Of course if you can evaluate the predicate in polynomial time there exists a family of derived datalog programs with non-empty query responses exactly for those instances where the predicate is true, by the above reduction. But that's a very different statement.] Thanks for taking the time to write a thorough answer. [I bookmark this if I want to chase down the exptime-completeness proof.]

@@knowledge-basedsystemstudr9413 This might be the smartest comment on RUclips.