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.

 

Posted Date: 3/1/2013 12:41:37 AM | Location : United States

Ask an Expert

Related Discussions:- Determine the properties and query are definable in datalog, Assignment Help, Ask Question on Determine the properties and query are definable in datalog, Get Answer, Expert's Help, Determine the properties and query are definable in datalog Discussions

Write discussion on Determine the properties and query are definable in datalog
Your posts are moderated

Write your message here..

Related Questions

Fraction, how to do fraction? how to do fraction?

Forecast errors, Forecast Errors Differences among actual results and ... Forecast Errors Differences among actual results and predictions may arise from many reasons. They may arise from random influences, usual sampling errors, option of the wrong

#title.simpal harmonic motion., #questionShow that the system oscillates in... #questionShow that the system oscillates in simple harmonic motion demonstrated by; , for which the general solution where X = (x – x0)..

Simulation model, Thorwarth M., Arisha, A. and Harper P., (2009) Simulation... Thorwarth M., Arisha, A. and Harper P., (2009) Simulation model to investigate flexible workload management for healthcare and servicescape environment, Proceedings of the 2009 Win

Help!!!, The equation -2x^2-kx-2=0 has two different real soultions. find t... The equation -2x^2-kx-2=0 has two different real soultions. find the set of possible values for k.

How to left shifts and right shifts a graph, Q. How to Left shifts and righ... Q. How to Left shifts and right shifts a graph? Ans. When you're translating (shifting) a graph, it's easy to get subtracting and adding mixed up. It seems counter-intuiti

Sovle equations with rational coefficents, How do you do this? How do you do this?

Find out the x-y coordinates of the points - tangents, Find out the x-y coo... Find out the x-y coordinates of the points in which the following parametric equations will have horizontal or vertical tangents. x = t 3 - 3t        y = 3t 2 - 9 Solut

We know this equation a°=1.prove this?, we know that log1 to any base =0 ta... we know that log1 to any base =0 take antilog threfore a 0 =1

Knowing your learner, Here, we have tried to present some of the different ... Here, we have tried to present some of the different thinking and learning processes of preschool and primary school children, in the context of mathematics learning. We have speci