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

Solid Mensuration, The two sides of a triangle are 17 cm and 28 cm long, an...

The two sides of a triangle are 17 cm and 28 cm long, and the length of the median drawn to the third side is equal to 19.5 cm. Find the distance from an endpoint of this median to

Other ways to aid learning maths, OTHER WAYS TO AID LEARNING :  Here we sh...

OTHER WAYS TO AID LEARNING :  Here we shall pay particular attention to the need for repetition, learning from other children, and utilising errors for learning.

Determine the position and nature of stationary points, Question. Deter...

Question. Determine the position and nature of stationary points of the function? f(x,y)= y/x -x 2 +y 2

Explain similar figures in similarity, Explain Similar Figures in similarit...

Explain Similar Figures in similarity ? Similar figures are figures that have the same shape but not necessarily the same size, so the image of a figure is similar to the orig

Conclusion of egroff''s theorem and lusin''s theorem, (1) Show that the con...

(1) Show that the conclusion of Egroff's theorem can fail if the measure of the domain E is not finite. (2) Extend the Lusin's Theorem to the case when the measure of the domain E

Marginal cost & cost function, Marginal cost & cost function  The cost ...

Marginal cost & cost function  The cost to produce an additional item is called the marginal cost and as we've illustrated in the above example the marginal cost is approxima

Design a diagram by transformation, On a graph, design a diagram by transfo...

On a graph, design a diagram by transformation the given graph of f (x), -2 ≤ x ≤ 2. Briefly Define the other graphs in terms of f (x) and specify their domains. The diagram n

Lucy youth group increased $1, Lucy's youth group increased $1,569 for char...

Lucy's youth group increased $1,569 for charity. They decided to split the money evenly between 3 charities. How much will each charity receive? Divide the money raised through

Shares and dividends, I need to make an assignment on this topic what shoul...

I need to make an assignment on this topic what should i write in it

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