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

Multiplyig, why is multiplying inportent in our lifes

why is multiplying inportent in our lifes

How many feet is the width of the deck, A pool is surrounded through a deck...

A pool is surrounded through a deck that has the similar width all the way around. The total area of the deck only is 400 square feet. The dimensions of the pool are 18 feet throug

Draw the digraph for the partial order, 1. Consider the relation on A = {1,...

1. Consider the relation on A = {1, 2, 3, 4} with relation matrix: Assume that the rows and columns of the matrix refer to the elements of A in the order 1, 2, 3, 4. (a)

Local maxima, Given that f(x,y) = 3xy -  x 2 y  - xy 2 . Fi nd all the poin...

Given that f(x,y) = 3xy -  x 2 y  - xy 2 . Fi nd all the points on the surface z = f(x, y)where local maxima, local minima, or saddles occur

Obtain the sum of the squares of values, This question is in the form of an...

This question is in the form of an exercise and questions designed to give you more insight into signal processing. On the Moodle site for the module there is an EXCEL file called

Comparison-types of word problems related to subtraction, Comparison - the...

Comparison - the difference between two groups or numbers, namely, how much one is greater than the other, how much more is in one group than in the other. (e.g., if Munna has

Build a fine automaton which accept all words, Build a Fine Automaton which...

Build a Fine Automaton which accept all words which have different first and last letters (that is if the word starts with an "a" to be accepted it should end with "b" and vice ver

Statistics., the mean and standarddeviation of set a is -x ans s respective...

the mean and standarddeviation of set a is -x ans s respectively.find the mean and standard deviation of set b

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