[10 points] Datalog A positive Boolean tree has leaves labeled with 0 or 1, and

Question

[10 points] Datalog A positive Boolean tree has leaves labeled with 0 or 1, and internal nodes which are operators AND, OR. The root of a boolean tree returns 0 or 1, determined by computing from the leaves upwards in the obvious way. We can represent a binary positive boolearn tree using the following stored (EDB) predicates . Leaf0(x): a unary table containing the identifiers of each leaf labeled 0. (Alterna- if r is tively, you can think of Leaf0(x) as a logical predicate that is true of node a leaf labeled 0.) Leafl(x): a unary table containing the identifiers of each leaf labeled 1. And(x,y. 2): a ternary table containing tuples (x, y2) if whose children are nodes y and is an AND node . Or(z, y,U2): a ternary table containing tuples (x,yi,U2) fx is an OR node whose children are nodes yi and y Root(x): a unary table containing the identifier of the root node. Write a datalog query that computes the boolean relation Answer) which is true if and only if the root node returns 1.

Explanation / Answer

Answer: See the sample datalog query below:

--------------------------------------

treeexpr(x,y1,y2):Or(x,y1,y2),And(y1,l1,l2),And(y2,l1,l2),Leaf0(l1),Leaf1(l2)
rootvalue(x,y1,y2):- treeexpr(x,y1,y2),Root(x) is 1
Answer(x,y1,y2):-rootvalue(x,y1,y2) is true

-----------------------------------

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.