DOC PREVIEW
Duke CPS 296.1 - Logic-Based Approach

This preview shows page 1-2 out of 5 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

1Answering Queries Using Views:Logic-Based ApproachCPS 296.1Topics in Database Systems2Logic-based approach• Often used in data integration• Focuses on finding as many answers as possible• Bucket-based algorithms– Levy et al. “Querying Heterogeneous Information Sources Using Source Descriptions.” VLDB, 1996– Pottinger and Levy. “A Scalable Algorithm for Answering Queries Using Views.” VLDB, 2000– Mitra. “An Algorithm for Answering Queries Efficiently Using Views.” ADBC, 2001• Inverse-rules algorithm– Duschka et al. “Recursive Query Plans for Data Integration.” Journal of Logic Programming, 20003Brute-force algorithm• Q: a CQ to be answered• V1, V2, …: views (also defined as CQ’s)• To find a rewriting of Q using Vi’s– Try each possible join of Vi’s as a rewriting for Q– Expand all Vi’s in the join (that is, replace each Viby its definition)– Test if the expansion (also a CQ) is contained in Q– Q is rewritten as a union of these rewritings!Too many possibilities to explore4Expanding a rewriting•Example– View: grandparent(X, Z) :- parent(X, Y), parent(Y, Z)– Rewriting of a query: g-g-g-grandparent(X, Z) :grandparent(X, Y), grandparent(Y, Z)– Expansion: g-g-g-grandparent(X, Z) :-parent(X, Y1), parent(Y1, Y),parent(Y, Y2), parent(Y2, Z)• Watch the use of variables– Use the query variables for the head of the views– Make sure variables “local” to different views do not clash with each other5Bucket algorithm• Remember there should be a containing mapping from Qto a rewriting (with views expanded)– Each subgoal of Q must be covered by some view in the rewriting; that is, the query subgoal must map to some subgoal in some view– A distinguished variable (one that appears in the head of a rule) in Q must map to a distinguished variable in some view– For a shared variable X (one that appears more than once in the body of a rule; i.e., needed for join) in Q, either• X maps to a distinguished variable in some view, or• All query subgoals involving X map to subgoals of a single view6Examples (slide 1)• A is not distinguished, and not shared– A can map to Z in the expansion of V (not distinguished)• B is not distinguished, but shared– Given the A mapping, B should map to Y in V (distinguished)– Other occurrences of B can map to distinguished variables in some other view (say Y in V’)Rewriting … V(X, Y)…V’(…, Y, …)Expansion p(X, W), q(W, Z), r(Z, Y)…Y…Query Q(D, E) :- … r(A, B)…s(B, C)27Examples (slide 2)• A is not distinguished, and not shared– A can map to W in the expansion of V (not distinguished)• B is not distinguished, but shared– Given the A mapping, B is forced to Z (not distinguished)– The other occurrence of B now has no place to go!• V has no s subgoal• Another view expansion would not have Z as a variableRewriting … V(X, Y)…Expansion p(X, W), q(W, Z), r(Z, Y)…Query Q(D, E) :- … q(A, B)…s(B, C)?8Examples (slide 3)• A is not distinguished, and not shared– A can map to W in the expansion of V (not distinguished)• B is not distinguished, but shared– Given the A mapping, B is forced to Z (not distinguished)– This mapping also happens to work out for the other occurrence of B–So B is completely “covered” by VRewriting … V(X, Y)…Expansion p(X, W), q(W, Z), r(Z, Y)…Query Q(D, E) :- … q(A, B)…r(B, C)9Examples (slide 4)• A is distinguished– Then A must map to a distinguished variable in a view expansion– Otherwise the target variable cannot appear in the head of the rewritingRewriting Q’(X, U) :- … V(X, Y)…Expansion … p(X, W), q(W, Z), r(Z, Y)…Query Q(A, D) :- … p(A, B)…q(B, C)10Buckets (slide 1)One bucket for each subgoal p(A1, …, An) of Q• For each view V, check each subgoal of the form p(X1, …, Xn) in V• Put this view subgoal into the bucket if– There is a mapping from A1, …, Anto X1, …, Xn(the only reason there might not be is if there were duplicate occurrences among the Ai’s)– If Aiis distinguished or shared in Q, then Xiis distinguished in V!Intuition: V covers this query subgoal11Buckets (slide 2)One bucket for each shared variable B in Q•Let GG, Bbe the set of subgoals in Q containing B• For each view V, check each possible subset GVof the subgoals in V such that there is a containment mapping from GG, Bto GV!Intuition: V covers all query subgoals containing B• Put GVinto the bucket if– The containment mapping maps all distinguished variables in Q to distinguished variables in V12Example of filling buckets (slide 1)•Views– grandparent(X, Y) :- parent(X, Z), parent(Z, Y)– great-grandparent(U, V) :-parent(U, S), parent(S, T), parent(T, V)•Query– query(A, B) :-parent(A, C), parent(C, D), parent(D, E),parent(E, F), parent(F, G), parent(G, B)• Buckets– 6 buckets for 6 query subgoals– 5 buckets for 5 shared variables (C, D, E, F, G)313Example of filling buckets (slide 2)• Consider the bucket for parent(A, C)– A is distinguished and C is shared– No view subgoal has two distinguished variables– So the bucket is empty• Consider the bucket for parent(C, D)– Both C and D are shared– So the bucket is empty• Similarly, buckets for other query subgoals are emptygrandparent(X, Y) :- parent(X, Z), parent(Z, Y)great-grandparent(U, V) :- parent(U, S), parent(S, T), parent(T, V)query(A, B) :- parent(A, C), parent(C, D), parent(D, E),parent(E, F), parent(F, G), parent(G, B)14Example of filling buckets (slide 3)• Consider the bucket for C– Need to find a containment mapping from{ parent(A, C), parent(C, D) } to view subgoals– For grandparent view, we have• { parent(X, Z), parent(Z, Y) }– For great-grandparent view, we have• { parent(U, S), parent(S, T) }• What about { parent(S, T), parent(T, V) }?grandparent(X, Y) :- parent(X, Z), parent(Z, Y)great-grandparent(U, V) :- parent(U, S), parent(S, T), parent(T, V)query(A, B) :- parent(A, C), parent(C, D), parent(D, E),parent(E, F), parent(F, G), parent(G, B)15Example of filling buckets (slide 4)• Consider the bucket for D– Need to find a containment mapping from{ parent(C, D), parent(D, E) } to view subgoals– For grandparent view, we have• { parent(X, Z), parent(Z, Y) }– For great-grandparent view, we have• { parent(U, S), parent(S, T) }• { parent(S, T), parent(T, V) }grandparent(X, Y) :- parent(X, Z), parent(Z, Y)great-grandparent(U, V) :- parent(U, S), parent(S, T), parent(T, V)query(A, B)


View Full Document

Duke CPS 296.1 - Logic-Based Approach

Documents in this Course
Lecture

Lecture

18 pages

Lecture

Lecture

6 pages

Lecture

Lecture

13 pages

Lecture

Lecture

5 pages

Load more
Download Logic-Based Approach
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Logic-Based Approach and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Logic-Based Approach 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?