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

Explain basic concepts of parallel lines, Explain Basic Concepts of Paralle...

Explain Basic Concepts of Parallel Lines ? Parallel lines are defined in section 1.2 and we use "//" to denote it. From the definition, we can get the following two consequenc

Determine the probability that is of low quality, 1) A local factory makes ...

1) A local factory makes sheets of plywood. Records are kept on the number of mild defects that occur on each sheet. Letting the random variable x represent the number of mild de

How many days are there in a year, There are m months in a year, w weeks wi...

There are m months in a year, w weeks within a month and d days in a week. How many days are there in a year? In this problem, multiply d and w to obtain the total days in one

Linear equations in one variable, three prices are to be distributed in a q...

three prices are to be distributed in a quiz contest.The value of the second prize is five sixths the value of the first prize and the value of the third prize is fourfifth that of

Iti, Gm signal is better than am signal becuase

Gm signal is better than am signal becuase

What decimal is represented by point a on the number line, What decimal is ...

What decimal is represented by point A on the number line? The hash marks indicate units of 0.01 between 0.75 and 0.80. Point A is 0.77. See the ?gure below.

Solid mensuration, given dimensions: 130cm, 180cm, and 190cm is to be divid...

given dimensions: 130cm, 180cm, and 190cm is to be divided by a line bisecting the longest side shown from its opposite vertex. what''s the area adjacent to 180cm? ;

In the terms of x, The length of Kara's rectangular patio can be expressed ...

The length of Kara's rectangular patio can be expressed as 2x - 1 and the width can be expressed as x + 6. In the terms of x, what is the area of her patio? Since the area of a

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