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

Sample space, Sample Space is the totality of all possible out...

Sample Space is the totality of all possible outcomes of an experiment. Hence if the experiment was inspecting a light bulb, the only possible outcomes

Inverse tangent, Inverse Tangent : Following is the definition of the inve...

Inverse Tangent : Following is the definition of the inverse tangent.  y = tan -1 x     ⇔ tan y = x                     for            -∏/2 ≤ y ≤ ?/2 Again, we have a limi

What are natural numbers and whole numbers, What are Natural Numbers and Wh...

What are Natural Numbers and Whole Numbers? Natural numbers are the numbers that you "naturally" use for counting: 1, 2, 3, 4, ... The set of whole numbers is the set of

How many feet huge is her dining room, Audrey measured the width of her din...

Audrey measured the width of her dining room in inches. It is 150 inches. How many feet huge is her dining room? There are 12 inches in a foot. Divide 150 by 12 to find out the

Auxiliary methods for information distribution, AUXILIARY METHODS There...

AUXILIARY METHODS There are other reprographic methods which although commonly used earlier, are now mainly used for specific purposes. We think you should be aware of these me

Find the values of k, If the vertices of a triangle are (1, k), (4, -3), (-...

If the vertices of a triangle are (1, k), (4, -3), (-9, 7) and its area is 15 sq units, find the value(s) of k..

Example of identify the pre-requisites, Ravi is a teacher of Class 4 in a m...

Ravi is a teacher of Class 4 in a municipal school in Delhi. When the new school year started, he opened the textbook and started teaching the children how to write 4-digit numbers

How much sales tax did she pay if items was 6 percent, Lindsay purchased a ...

Lindsay purchased a pocketbook for $45 and a pair of shoes for $55. The sales tax on the items was 6%. How much sales tax did she pay? Find out the price of the two items toget

One integer is two more than another what is greater integer, One integer i...

One integer is two more than another. The sum of the lesser integer and double the greater is 7. What is the greater integer? Let x = the greater integer and y = the lesser int

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