TOP-K projection queries for probabilistic business processes

ABSTRACT

A Business Process (BP) consists of some business activities undertaken by one or more organizations in pursuit of some business goal. Tools for querying and analyzing BP specifications are extremely valuable for companies. In particular, given a BP specification, identifying the top-k flows that are most likely to occur in practice, out of those satisfying a given query criteria, is crucial for various applications such as personalized advertizement and BP web-site design.

This paper studies, for the first time, top-k query evaluation for queries with projection in this context. We analyze the complexity of the problem for different classes of distribution functions for the flows likelihood, and provide efficient (PTIME) algorithms whenever possible. Furthermore, we show an interesting application of our algorithms to the analysis of BP execution traces (logs), for recovering missing information about the run-time process behavior, that has not been recorded in the logs.

REFERENCES

• 1: S. Abiteboul and P. Senellart. Querying and updating probabilistic information in xml. In Proc. of EDBT, 2006.
• 2: Catriel Beeri , Anat Eyal , Simon Kamenkovich , Tova Milo, Querying business processes, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 3: Catriel Beeri , Anat Eyal , Tova Milo , Alon Pilberg, Monitoring business processes with queries, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 4: S. Bhiri, W. Gaaloul, and C. Godart. Mining and improving composite web services recovery mechanisms. Int. J. Web Service Res., 5(2), 2008.
• 5: Business Process Execution Language for Web Services. http://www.ibm.com/developerworks/library/ws-bpel/.
• 6: Oracle bpel process manager administrator's guide - configuring and viewing bpel process logs. http://download.oracle.com/docs/cd/E11036-01/integrate.1013/b28982/logging.htm.
• 7: T. Brazdil, A. Kucera, and O. Strazovsky. On the decidability of temporal properties of probabilistic pushdown automata. In Proc. of STACS, 2005.
• 8: Sara Cohen , Benny Kimelfeld , Yehoshua Sagiv, Incorporating constraints in probabilistic XML, Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376916.1376933]
• 9: Mariano P. Consens , Alberto O. Mendelzon, The G+/GraphLog Visual Query System, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.388, May 23-26, 1990, Atlantic City, New Jersey, United States
• 10: Bruno Courcelle, The monadic second-order logic of graphs. I. recognizable sets of finite graphs, Information and Computation, v.85 n.1, p.12-75, March 1990 [doi>10.1016/0890-5401(90)90043-H]
• 11: Nilesh Dalvi , Dan Suciu, Efficient query evaluation on probabilistic databases, Proceedings of the Thirtieth international conference on Very large data bases, p.864-875, August 31-September 03, 2004, Toronto, Canada
• 12: D. Deutch and T. Milo. Querying structural and behavioral properties of business processes. In Proc. of DBPL, 2007.
• 13: Daniel Deutch , Tova Milo, Type inference and type checking for queries on execution traces, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453898]
• 14: D. Deutch and T. Milo. Evaluating top-k queries over business processes. In Proc. of ICDE, 2009.
• 15: K. Etessami and M. Yannakakis. Algorithmic verification of recursive probabilistic state machines In Proc. of TACAS, 2005.
• 16: Nir Friedman , Lise Getoor , Daphne Koller , Avi Pfeffer, Learning Probabilistic Relational Models, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.1300-1309, July 31-August 06, 1999
• 17: W. Gaaloul and C. Godart. Mining workflow recovery from event based logs. In Business Process Management, 2005.
• 18: J. G. Kemeny and J. L. Snell. Finite Markov Chains. Springer, 1976.
• 19: Benny Kimelfeld , Yuri Kosharovsky , Yehoshua Sagiv, Query efficiency in probabilistic XML models, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376687]
• 20: Benny Kimelfeld , Yehoshua Sagiv, Matching twigs in probabilistic XML, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 21: Zohar Manna , Amir Pnueli, The temporal logic of reactive and concurrent systems, Springer-Verlag New York, Inc., New York, NY, 1992
• 22: S. P. Meyn and R. L. Tweedie. Markov Chains and Stochastic Stability. Springer-Verlag, 1993.
• 23: T. Oates, S. Doshi, and F. Huang. Estimating maximum likelihood parameters for stochastic context-free graph grammars. In Proc. of ILP, 2003.
• 24: C. Re, N. N. Dalvi, and D. Suciu. Efficient top-k query evaluation on probabilistic data. In Proc. of ICDE, 2007.
• 25: Mark Reynolds, An axiomatization of PCTL, Information and Computation, v.201 n.1, p.72-119, 25 August 2005 [doi>10.1016/j.ic.2005.03.005]
• 26: P. Sen and A. Deshpande. Representing and querying correlated tuples in probabilistic databases. In Proc. of ICDE, 2007.