Determine the properties and query are definable in datalog, Mathematics

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







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
Related Questions
find k,is -2 a root of the equation 3x2

In Figure, what are the angles of depression from the observing positions O 1 and O 2 of the object at A?

The C.P. of 20 articles is same as theS.P. of x articles.Article profit is 25%.Find x

Following is some more common functions that are "nice enough". Polynomials are nice enough for all x's. If f ( x) = p ( x ) /q (x ) then f(x) will be nice enough provid

I am greater than 30 and less than 40. The sum of my digits is less than 5. who am I?

Q. Find the number of ways three letter "words" can be chosen from the alphabet if none of the letters can be repeated? Solution:  There are 26 ways of choosing the first lett

larry spends 3/4 hours twice a day walking and playing with his dog. He spends 1/6 hours twice a day feeding his dog. how much time does larry spend on his dog each day?

Calculate the mean, variance & standard deviation of the number of heads in a simultaneous toss of three coins.     SOLUTION:    Let X denotes the number of heads in a simu

DEVELOPING ESTIMATION SKILLS :  A study was done with some Class 3 and Class 4 children of five village schools to gauge how well they had understood the standard algorithms. The

Integrate following. ∫ -2   2 4x 4 - x 2   + 1dx Solution In this case the integrand is even & the interval is accurate so, ∫ -2   2 4x 4 - x 2   + 1dx = 2∫ o