Wrokflow programming and provenance query model
Download as pptx, pdf0 likes36 views
This document defines key concepts for a workflow programming and provenance query model, including workflows, data, modules, dataflow, and properties. It proposes three fundamental queries - Decide, Sequence, and Map - that can answer provenance questions about workflows. These three queries are shown to be sufficient to address provenance queries posed in several other research works. Query results are proposed to be visualized through techniques like DAGs and tables.
More Related Content
What's hot (20)
Similar to Wrokflow programming and provenance query model (20)
Recently uploaded (20)
Wrokflow programming and provenance query model
- 1. Workflow Programming & Provenance Query Model - The Theory Rayhan Ferdous SR Lab Dept. of CS U of S
- 2. Definitions • Workflow • Data • Module • Dataflow • Module Invocation • Query
- 3. Workflow (Definition) • A Workflow W = (V, E) is a Directed Acyclic Graph where, • V = {v : v D M} • E = {e : e F} • D = A set to represent Data (Defined later) • M = A set to represent Module (Defined later) • F = A set to represent Dataflow (Defined later)
- 4. Data (Definition) • Data is a workflow element from W = (V, E) where, • D = {d : d V, d = (p1, p2, …, pn) } • p P • P = An ordered set to represent properties (defined later)
- 5. Module (definition) • Module is a workflow element from W = (V, E) where, • M = {m : m V, m = (p1, p2, …, pn) } • p P • P = An ordered set to represent properties (defined later)
- 6. Properties (definition) • Properties P = (p1, p2, …, pn) is an ordered set associated with any data d D and module m M from a workflow W where, • p = Null | Any
- 7. Dataflow (definition) • A Dataflow F is an ordered tuple containing two workflow elements to represent a directed edge in workflow W where, • F = (d, m) | (m, d) • d D • m M • (d, m) is considered as input dataflow, written as d → m • (m, d) is considered as output dataflow, written as m → d
- 8. Module invocation • A module invocation K is an ordered tuple containing two dataflows where, • K = { (f1 , f2) : f1 = (di , m), f2 = (m, do) }
- 9. Mathematical Rules Support • Workflow W containing all the defined elements is a graph itself • So, it supports all the rules of Graph Theory inherently
- 10. Data Analytics Lifecycle and Query • Workflow can be used in any phase of data analytics • If a query system can be applied upon all the phases of analytics lifecycle → it can be taken as elementary • We present a fundamental query system (only one) • And 2 others that are derived from the first one (Total 3 queries) • That can be used to answer any provenance question
- 11. Answering Query • In our approach, to answer a query we use data visualization • Data visualization enables storytelling about data as well as answer multiple queries at the same time
- 12. Analytics Lifecycle phase – Base question – Problem type 1. Discovery (Do I have enough information?) (Discovery) 2. Data Preparation (Do I have enough good quality data?) (Discovery) 3. Model Planning (Can I refine the analytics pipeline?) (Prediction/Recommendation) 4. Model Building (Is the model robust enough?) (Prediction/Recommendation) 5. Communicate Results (Reporting) (Prediction/Recommendation) 6. Operationalize (Execution)
- 13. Category of questions that queries could answer Analytics Past event Discovery Elementary Query Present event Monitoring Online Time Series Query Future event Prediction/ Recommendation Mapping Query
- 14. The elementary Query (our proposal) • An elementary query Q is a function that returns an ordered element of type R satisfying certain condition(s) from any Workflow W. • Q = f(R, W, C) • R = (r1, r2, … , rk) is an ordered set where r P • C = Boolean condition
- 15. A workflow can be regenerated with a sequence of Query results • We can use the first elementary query to generate a sequence of dataflows. • Example: • Q1 = A → B • Q2 = B → C • Q3 = C → D • That gives A → B → C → D
- 16. A dataset can be prepared by mapping results from two distinct queries • The mapping function can be regenerated using the first elementary query • Example: • Q1 = (x1 , x2 , … , xn) • Q2 = (y1 , y2 , … , yn) • Q1 ↔ Q2 is an one to one mapping between the ordered sets that gives ( (x1 , y1) , (x2 , y2) , … , (xn , yn) )
- 17. Proposal • We propose a fundamental set of 3 queries for answering provenance questions. • Decide (the first query) • Sequence (the second query) • Map (the third query)
- 18. How complete are the 3 queries ? • Check with different research works
- 19. Ghoshal et al., "Provenance from log files: a BigData problem." Proceedings of the Joint EDBT/ICDT 2013 Workshops. • Match – Select Rule: Decide • Link Rule: Map • Remap Rule: Map
- 20. Akidau et al., “The dataflow model: a practical approach to balancing correctness, latency, and cost in massive-scale, unbounded, out-of-order data processing." Proceedings of the VLDB Endowment, 2015 • What results are being computed?: Decide • Where in event time they are being computed?: Decide • When in processing time they are materialized?: Decide • How earlier results relate to later refinements?: Sequence
- 21. Anand et al., "Techniques for efficiently querying scientific workflow provenance graphs." EDBT 2010. • Lineage query – Sequence • Function query - Decide
- 22. Buneman et al., "Why and where: A characterization of data provenance." International conference on database theory. 2001. • Why provenance (source data query) : Sequence • Where provenance (Mapping with database) : Map
- 23. Cheney et al., "Provenance in databases: Why, how, and where." Foundations and Trends® in Databases, 2009 • Why provenance (source) : Decide • How provenance (lineage) : Sequence • Where provenance (source in database): Decide
- 24. Answering through Visualization • Decide – Visualization not necessary or Tabular format • Sequence – DAG • Map – Tabular format
- 25. To visualize analytical analytical results • This is query dependent
- 26. Conclusion