--%>
Assignment Help - homework help

Problem on Datalog for defining properties

The focus is on  the use of Datalog for defining properties  and queries on graphs.

(a) Assume that P is some property of graphs  definable in the Datalog. Show that P is preserved beneath extensions  and homomorphisms. That is, when G is a graph satisfying P, then for every supergraph of G (i.e., graph  extending G) satisfies  P, and  when h is a graph homomorphism, then h(G) satisfies P. Which of the below properties  and queries on graphs are definable in the Datalog?

(b) The number  of vertices  are even.

(c) There is a simple path (that is, a path without repeated vertices) of even length among two specified vertices.

(d) The binary relation? Having all pairs of vertices (a, b) for which  there  is a path of even length from a to b.

Given either a Datalog program stating the property or query or an argument why the property or query is not definable in the Datalog.

   Related Questions in Mathematics

  • Q : Properties for polynomial Specify the

    Specify the important properties for the polynomial.

    		•
  • Q : First-order formulas over the

    Consider the unary relational symbols P and L, and the binary relational symbol On, where P(a) and I(a) encode that a is apoint and a (sraight) line in the 2-dimensional space, respectively, while On(a,b) encodes  that a is a point, b is a line, and o lies on b.

    		•
  • Q : Explain Black–Scholes model Explain

    Explain Black–Scholes model.

    		•
  • Q : Probability and Stochastic assignment

    Introduction to Probability and Stochastic Assignment 1: 1. Consider an experiment in which one of three boxes containing microchips is chosen at random and a microchip is randomly selected from the box.

    		•
  • Q : Use MS Excel to do the computations

    Select a dataset of your interest (preferably related to your company/job), containing one variable and atleast 100 data points. [Example: Annual profit figures of 100 companies for the last financial year]. Once you select the data, you should compute 4-5 summary sta

    		•
  • Q : Problem on Maple (a) Solve the

    (a) Solve the following  by: (i) First reducing the system of first order differentiat equations to a second order differential equation. (ii) Decoupling the following linear system of equa

    		•
  • Q : Problem on Linear equations Anny, Betti

    Anny, Betti and Karol went to their local produce store to bpought some fruit. Anny bought 1 pound of apples and 2 pounds of bananas and paid $2.11.  Betti bought 2 pounds of apples and 1 pound of grapes and paid $4.06.  Karol bought 1 pound of bananas and 2

    		•
  • Q : Set Theory & Model of a Boolean Algebra

    II. Prove that Set Theory is a Model of a Boolean Algebra The three Boolean operations of Set Theory are the three set operations of union (U), intersection (upside down U), and complement ~.  Addition is set

    		•
  • Q : Row-echelon matrix Determine into which

    Determine into which of the following 3 kinds (A), (B) and (C) the matrices (a) to (e) beneath can be categorized:       Type (A): The matrix is in both reduced row-echelon form and row-echelon form. Type (B): The matrix

    		•
  • Q : Linear programming model of a Cabinet

    A cabinet company produces cabinets used in mobile and motor homes. Cabinets produced for motor homes are smaller and made from less expensive materials than those for mobile homes. The home office in Dayton Ohio has just distributed to its individual manufacturing ce

    		•