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

Standard conventions in game theory, Standard conventions in game theory ...

Standard conventions in game theory Consider the given table: Y   3 -4 X -2 1

Solving ratios, you are in charge of making punch for an upcoming dance. th...

you are in charge of making punch for an upcoming dance. the punch recipe makes 5 cups of punch by making 3 cups of cranberry juice with 2 cups of apple juice. What is the ratio of

Illustration of simpson rule, By using n = 4 and all three rules to approxi...

By using n = 4 and all three rules to approximate the value of the following integral. Solution Very firstly, for reference purposes, Maple provides the following valu

Differentiate functions h (t ) = 2t5 + t2- 5 / t2 , Differentiate f...

Differentiate following functions.                       h (t ) = 2t 5 + t 2 - 5 / t 2 We can simplify this rational expression as follows.                       h (t )

Ellipse, How we find locus of the middle points of chord of an ellipse whic...

How we find locus of the middle points of chord of an ellipse which are drawn through the positive end of the minor axes

Polar coordinates - parametric equations & polar coordinates, Polar Coordin...

Polar Coordinates Till this point we've dealt completely with the Cartesian (or Rectangular, or x-y) coordinate system.  Though, as we will see, this is not all time the easie

Variation and proportion, i am not getting what miss has taught us please w...

i am not getting what miss has taught us please will you will help me in my studies

Sketch the graph of h (t ) = 1 - 5e 1/(t/2), Sketch the graph of h (t ) = ...

Sketch the graph of h (t ) = 1 - 5e  1/(t/2) Solution : Let's primary get a table of values for this function. Following is the sketch. The major point behin

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