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

Find the maximum and minimum brightness values, Variable stars are ones who...

Variable stars are ones whose brightness varies periodically. One of the most visible is R Leonis; its brightness is modelled by the function where t is measured in days.

Functions of many variables, There may be more than one independent v...

There may be more than one independent variable which determines the value of y. The dimension of a function is determined by the number of independent variables in the

Argument, what is the difference between argument and principle argument

what is the difference between argument and principle argument

Trigonometry, explain the formular for finding trigonometry

explain the formular for finding trigonometry

Arc length with polar coordinates, Arc Length with Polar Coordinates H...

Arc Length with Polar Coordinates Here we need to move into the applications of integrals and how we do them in terms of polar coordinates.  In this part we will look at the a

How many miles required to be driven for both services cost, Easy Rider tax...

Easy Rider taxi service charges a pick-up fee of $2 and $1.25 for each mile. Luxury Limo taxi service charges a pick-up fee of $3.25 and $1 per mile. How many miles required to be

Trigonometry, If sec A = x+i/x, prove that sec A + tan A = 2x or 1/2x

If sec A = x+i/x, prove that sec A + tan A = 2x or 1/2x

Mensuration, a hollow cone is cut by a plane parallel to the base and the u...

a hollow cone is cut by a plane parallel to the base and the upper portion is removed. if the volume of the frustum obtained is 26/27 of volume of the cone. find at what height abo

Determine the area of the shaded region, The diagram below shows the cross ...

The diagram below shows the cross section of a pipe  1/2  inch thick that has an inside diameter of 3 inches. Determine the area of the shaded region in terms of π. a. 8.75π i

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