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

Negative and positives, in 1970 a record 1.5 of rain fell in one minute at ... in 1970 a record 1.5 of rain fell in one minute at Basse Terre, guadaloupe in the caribbnean.at this rate, how much rain fell in 3 seconds or 0.05 of a minutes?

Compositions of relations, Let Consider R A Χ B, S B Χ C be two relation... Let Consider R A Χ B, S B Χ C be two relations. Then compositions of the relations S and R given by SoR A Χ C and is explained by (a, c) €(S o R) iff € b € B like (a, b) € R,

Project, elliptical path of celestial bodies elliptical path of celestial bodies

Dif eq, y"-3y''-4y=2sinx y"-3y''-4y=2sinx

Introduction to mathematics, We know that one has to deal with ... We know that one has to deal with numbers in day-to-day life irrespective of his inclination and field of work. Also one cannot refute the fact

How many points did he score during his senior year, Michael scored 260 poi... Michael scored 260 points during his junior year on the school basketball team. He scored 20% more points during his senior year. How many points did he score during his senior yea

Determine the ratio in which the line 2x + y -4 = 0, Determine the ratio in... Determine the ratio in which the line 2x + y -4 = 0 divide the line segment joining the points A (2,-2) and B (3, 7).Also find the coordinates of the point of division. [Ans:2 :

Number sequence, what is the formula to find a sequence on a string of numb... what is the formula to find a sequence on a string of numbers?

Solving trigonometric equations, tan 2x = 1 tan 2x = 1

Ratios, the ratio of boys to girls in the sixth grade is 2:3 if there are ... the ratio of boys to girls in the sixth grade is 2:3 if there are 24 boys, how many are girls?