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.

 

Posted Date: 3/1/2013 12:41:37 AM | Location : United States

Ask an Expert

Related Discussions:- Determine the properties and query are definable in datalog, Assignment Help, Ask Question on Determine the properties and query are definable in datalog, Get Answer, Expert's Help, Determine the properties and query are definable in datalog Discussions

Write discussion on Determine the properties and query are definable in datalog
Your posts are moderated

Write your message here..

Related Questions

Question, If X = {a, e, i, o, u} and Y = {a, b, c, d, e}, then what is Y - ... If X = {a, e, i, o, u} and Y = {a, b, c, d, e}, then what is Y - X ?

Using euclid''s algorithm find the value of x & y, If d is the HCF of 30, 7... If d is the HCF of 30, 72, find the value of x & y satisfying d = 30x + 72y. (Ans:5, -2 (Not unique) Ans:    Using Euclid's algorithm, the HCF (30, 72) 72 = 30 × 2 + 12

Rolles therom, f(x)=sin x+cos x in the interval {0,90} f(x)=sin x+cos x in the interval {0,90}

Point of difference and parity, give definition and example give definition and example

Matric, fgdg ggghfr hhrhfrf hfrrg jhj hjgg dear friend ghr tu vgu jyyiu ui ... fgdg ggghfr hhrhfrf hfrrg jhj hjgg dear friend ghr tu vgu jyyiu ui u huik bgyuiiyts husk

Machines, descuss the seauencing problem for n jobs on two and three machin... descuss the seauencing problem for n jobs on two and three machines

Integer exponents, We will begin this chapter by looking at integer exponen... We will begin this chapter by looking at integer exponents.  Actually, initially we will suppose that the exponents are +ve as well. We will look at zero & negative exponents in a

Phase plane, Before proceeding along with in fact solving systems of differ... Before proceeding along with in fact solving systems of differential equations there's one topic which we require to take a look at. It is a topic that's not at all times taught in

Holistic markrting, necessity of holistic marketing? necessity of holistic marketing?

How many more cm are required to reach the average monthly, Thomas is remai... Thomas is remaining track of the rainfall in the month of May for his science project. The first day, 2.6 cm of rain fell. On the second day, 3.4 cm fell. On the third day, 2.1 cm