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

Sqares, Recently I had an insight regarding the difference between squares ...

Recently I had an insight regarding the difference between squares of sequential whole numbers and the sum of those two whole numbers. I quickly realized the following: x + (x+1)

.., the circumference of a circle C of radius r is given by C=2pR.taking p ...

the circumference of a circle C of radius r is given by C=2pR.taking p to be 22/7 a)find the circumference when the radius is 28 cm b)find the radius when the circumference is 484

Daily revenue for next 30 days, Owner of a computer repair shop has daily r...

Owner of a computer repair shop has daily revenue with mean $7200 and SD $1200 Daily revenue for next 30 days will be monitored. What is probability that daily revenue for those 30

Algebra ii, How do you graph a hyperbola?

How do you graph a hyperbola?

Cylinder, #question Show that the enveloping cylinder of the conicoid ax 2 ...

#question Show that the enveloping cylinder of the conicoid ax 2 + by 2 + cz 2 = 1 with generators perpendicular to the z-axis meets the plane z = 0 in parabolas

Linear programming, #question.As office manager of her firm, Marcellyne has...

#question.As office manager of her firm, Marcellyne has been directed to buy new filing cabinets. She knows that cabinet A costs $10, requires 6 square feet of floor space, and hol

Prove that its inclination is given by cot = b cot - a, Two stations due...

Two stations due south of a leaning tower which leans towards the north are at distances a and b from its foot.  If α ,  β be the elevations of the top of the tower from these

Explain english system in details, Explain English System in details? T...

Explain English System in details? There are three types of measurements that can be taken using the English System: length, distance, weight, and capacity. Length and dista

Allied mathematics, The tenth term in the binomial expansion of (1-1/4)(1-1...

The tenth term in the binomial expansion of (1-1/4)(1-1/5)(1-1/6)...(1-1/n+3) is equal to

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