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

Systems of differential equations, For this point we've only looked as solv...

For this point we've only looked as solving particular differential equations. Though, many "real life" situations are governed through a system of differential equations. See the

Initial conditions and boundary conditions, Initial Condition...

Initial Conditions and Boundary Conditions In many problems on integration, an initial condition (y = y 0 when x = 0) or a boundary condition (y = y

Prime Ideals, Given a standard 2x3 matrix show the ideal formed by the 2x2 ...

Given a standard 2x3 matrix show the ideal formed by the 2x2 minors is Prime.

Indices, 4n to the power 3/2 = 8 to the power minus 1/3. find the value of ...

4n to the power 3/2 = 8 to the power minus 1/3. find the value of n.

Complex number, If z=re i ? ,find the value of |e iz | Solution)   z=r(c...

If z=re i ? ,find the value of |e iz | Solution)   z=r(cos1+isin1) |e iz |=|e ir(cos1+isin1) |=|e -rsin1 |=e -rsin1

General approach of exponential functions, General approach of Exponential ...

General approach of Exponential Functions : Before getting to this function let's take a much more general approach to things. Let's begin with b = 0 , b ≠ 1. Then an exponential f

Define a*b for given matrix, Define A*B where:                A =  | 3 -...

Define A*B where:                A =  | 3 -3  6 |          B = |  6   1 |                          | 0  4  2 |              |  0  -5 |

What is the probability of tossing a head, Q. What is the probability of to...

Q. What is the probability of tossing a head? List the sample space for tossing a coin once. What is the probability of tossing a head? Solution:  If you tossed a coin once

Multiplication of complex numbers, Multiplication of complex numbers Af...

Multiplication of complex numbers After that, let's take a look at multiplication.  Again, along with one small difference, it's possibly easiest to just think of the complex n

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