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

Sketch the graph of h (t ) = 1 - 5e 1/(t/2), Sketch the graph of h (t ) = ...

Sketch the graph of h (t ) = 1 - 5e  1/(t/2) Solution : Let's primary get a table of values for this function. Following is the sketch. The major point behin

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

#Regular Expression, Find the Regular Grammar for the following Regular Exp...

Find the Regular Grammar for the following Regular Expression: a(a+b)*(ab*+ba*)b.

What is the vertex form for a quadratic equation, What is the Vertex Form f...

What is the Vertex Form for a Quadratic Equation ? The vertex form for a quadratic function is as follows: f(x) = a(x - h) 2 + k The graph of this function Is a parabola whos

Homework, joey asked 30 randomly selected students if they drank milk, juic...

joey asked 30 randomly selected students if they drank milk, juice, or bottled water with their lunch. He found that 9 drank milk, 16 drank juice, and 5 drank bottled water. If the

Xy Algebra, Find the values of x and y

Find the values of x and y

Operations and properties, use an expression to write an expression with fi...

use an expression to write an expression with five 3s that has a value of 0

Fraction word problems, Alan had 6 books. He read 1/3 of books last week. ...

Alan had 6 books. He read 1/3 of books last week. How many books did Alan read last week?

Multiplicative rule - rules of probability, Multiplicative Rule - Rules of ...

Multiplicative Rule - Rules of Probability It is used when there is a string of independent events for that individual probability is known and it is essential to know the ove

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