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

Standard deviation, i need to work out the standard deviation of 21.4

i need to work out the standard deviation of 21.4

Hypothesis testing of the difference between proportions, Hypothesis Testin...

Hypothesis Testing Of The Difference Between Proportions Illustration Ken industrial producer have manufacture a perfume termed as "fianchetto." In order to test its popul

Constructing a dfa/nfa or a regex), Let ∑ = (0, 1). Define the following la...

Let ∑ = (0, 1). Define the following language: L = {x | x contains an equal number of occurrences of 01 and 10} Either prove L is regular (by constructing a DFA/NFA or a rege

Quadratic equation assignment, what is number of quadratic equation that ar...

what is number of quadratic equation that are unchanged by squaring their roots is There are four such cases x 2   =0 root 0 (x-1) 2 =0  root 1 x(x+1)=0  roots  0 and 1

Prove asymptotic bounds for recursion relations, 1. (‡) Prove asymptotic b...

1. (‡) Prove asymptotic bounds for the following recursion relations. Tighter bounds will receive more marks. You may use the Master Theorem if it applies. 1. C(n) = 3C(n/2) + n

ConnectEd, How do I increase and decrease tax and sales

How do I increase and decrease tax and sales

Perimeter, what is the perimeter of a rhombus

what is the perimeter of a rhombus

Integers , (-85) from (-21) and explain me

(-85) from (-21) and explain me

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