Determine the properties and query are definable in datalog, Mathematics

Assignment Help:

We now focus on the use of Datalog for defining properties and queries m graphs.

(a) Suppose that P is some property of graphs definable in Datalog. Show drat P is preserved under extensions and homomorphisms. That is, if G is a graph satisfying P, then every supergraph of G (i.e., graph extending G) satisfies P, and if h is a graph homomorphism, then h (G) satisfies P.

Which of the following properties and queries on graphs are definable in Datalog?

b) The number of vertices is even.

(c) There is a simple path (i.e., a path without repeated vertices) of even length between two specified vertices.

(d) The binary relation T containing all pairs of vertices (a, D) for which there is a path of even length from o to b. Provide either a Datalog program defining the property or query or an argument why the property or query is not definable in Datalog.

 


Related Discussions:- Determine the properties and query are definable in datalog

Interpretation, Interpretation A high value of r as +0.9 or - 0...

Interpretation A high value of r as +0.9 or - 0.9 only shows a strong association among the two variables but doesn't imply that there is a causal relationship that is

Smith keeps track of poor work, Smith keeps track of poor work. Often on af...

Smith keeps track of poor work. Often on afternoon it is 5%. If he checks 300 of 7500 instruments what is probability he will find less than 20 substandard?

If t2+t+1=0 , t=w,w 2 L.H.S (w+w 2 ) + (w 2 + w) 2 ........  1  + 1 ....

t=w,w 2 L.H.S (w+w 2 ) + (w 2 + w) 2 ........  1  + 1 ..... But every third term is of the form: (w 3n +w 3n ) 2 =22 There are nine such terms. Their sum is 36. The rema

Taylor series, If f(x) is an infinitely differentiable function so the Tayl...

If f(x) is an infinitely differentiable function so the Taylor Series of f(x) about x=x 0 is, Recall that, f (0) (x) = f(x) f (n) (x) = nth derivative of f(x)

Complex roots - second order differential equations, We will be looking at ...

We will be looking at solutions to the differential equation, in this section ay′′ + by′ + cy = 0 Wherein roots of the characteristic equation, ar 2 + br + c = 0 Those

Explain peano''s axioms with suitable example, Question 1 Explain Peano's ...

Question 1 Explain Peano's Axioms with suitable example Question 2 Let A = B = C= R, and let f: A→ B, g: B→ C be defined by f(a) = a+1 and g(b) = b 2 +1. Find a) (f °g

Example to compute limit, calculates the value of the following limit. ...

calculates the value of the following limit. Solution Now, notice that if we plug in θ =0 which we will get division by zero & so the function doesn't present at this

Find a power series representation for the function, Find a power series re...

Find a power series representation for the subsequent function and find out its interval of convergence. g (x) = 1/1+x 3 Solution What we require to do here is to rela

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd