--%>

Problem on Datalog for defining properties

The focus is on  the use of Datalog for defining properties  and queries on graphs.

(a) Assume that P is some property of graphs  definable in the Datalog. Show that P is preserved beneath extensions  and homomorphisms. That is, when G is a graph satisfying P, then for every supergraph of G (i.e., graph  extending G) satisfies  P, and  when h is a graph homomorphism, then h(G) satisfies P. Which of the below properties  and queries on graphs are definable in the Datalog?

(b) The number  of vertices  are even.

(c) There is a simple path (that is, a path without repeated vertices) of even length among two specified vertices.

(d) The binary relation? Having all pairs of vertices (a, b) for which  there  is a path of even length from a to b.

Given either a Datalog program stating the property or query or an argument why the property or query is not definable in the Datalog.

   Related Questions in Mathematics

  • Q : Competitive equilibrium 8. Halloween is

    8. Halloween is an old American tradition. Kids go out dressed in costume and neighbors give them candy when they come to the door. Spike and Cinderella are brother and sister. After a long night collecting candy, they sit down as examine what they have. Spike fi

  • Q : State Measuring complexity Measuring

    Measuring complexity: Many algorithms have an integer n, or two integers m and n, as input - e.g., addition, multiplication, exponentiation, factorisation and primality testing. When we want to describe or analyse the `easiness' or `hardness' of the a

  • Q : Problem on Datalog for defining

    The focus is on  the use of Datalog for defining properties  and queries on graphs. (a) Assume that P is some property of graphs  definable in the Datalog. Show that P is preserved beneath extensions  and homomo

  • Q : Problem on Maple (a) Solve the

    (a) Solve the following  by: (i) First reducing the system of first order differentiat equations to a second order differential equation. (ii) Decoupling the following linear system of equa

  • Q : Abstract Boolean Algebra I. Boolean

    I. Boolean Algebra Define an abstract Boolean Algebra, B,  as follows:  The three operations are:  +   ( x + y addition) ( x y multiplic

  • Q : Problem on mass balance law Using the

    Using the mass balance law approach, write down a set of word equations to model the transport of lead concentration. A) Draw a compartmental model to represent  the diffusion of lead through the lungs and the bloodstream.

  • Q : Define Big-O notation Big-O notation :

    Big-O notation: If f(n) and g(n) are functions of a natural number n, we write f(n) is O(g(n)) and we say f is big-O of g if there is a constant C (independent of n) such that f

  • Q : How do it? integral e^(-t)*e^(tz) t

    integral e^(-t)*e^(tz) t between 0 and infinity for Re(z)<1

  • Q : Who independently developed

    Who independently developed a model for simply pricing risky assets?

  • Q : Containee problem For queries Q 1 and Q

    For queries Q1 and Q2, we say Q1 is containedin Q2, denoted Q1 C Q2, iff Q1(D) C Q2