. States, For both BAXML and TA, all states are mapped to a constant state (so all information about the states is lost)

. Events and B. For, active calls ?g are mapped to ? and calls !g are mapped to g or to ? (so some function calls can be hidden); for TA, a service ? is mapped to ? or to ? (so again, some services can be hidden)

V. Fun and T. Of, Recall that the definition of simulation does not require effective construction of the simulating schema (even though all our positive simulation results are constructive) We can show that one cannot effectively construct a TA specification simulating a given BAXML schema, with respect to the above views. THEOREM 6.9. There is no algorithm that, given as input a BAXML schema W 1 and a view V 1 ? V fun produces a TA schema W 2 with a view V 2 ? V serv such that V 1 Moreover, this holds even for BAXML schemas of bounded depth. PROOF. The proof is based on a reduction from the implication problem for functional and inclusion dependencies (FDs and IDs), known to be undecidable. Specifically, we consider instances of the implication problem of the form ? |= f , where ? is a set of FDs and IDs, and f an FD. We consider a BAXML schema S whose initial instance consists of a single external function !e under the root. The function returns a tree representing an arbitrary finite relation, of the form shown in Figure 6. Specifically, each tuple is adorned with one function !f ? for each ID ? in ?

. Additionally, Satisfaction of the FDs in ?, and violation of f, are ensured by static constraints. The guard of !g simply checks that the relation returned by the call to !e is non-empty. We consider the view V S retaining all functions. It is easy to check that ? |= f iff there is a blocking run of S whose view under V S is ? = init.e.g.(block) ? (we ignore the constant state) Indeed, since no function !f ? can be called, all IDs in ? are satisfied. Recall that satisfaction of the FDs in ? and violation of f are ensured by the constraints. Thus, the non-empty instance returned by e satisfies ? and violates f. Now suppose towards a contradiction that one can effectively construct, for each BAXML schema as above, a corresponding artifact system ? with a view V ? ? V serv so that By definition, the first event in both

T. Let and . !-e-be-the-subtree-of, e ) must be w-bisimilar to V (T ) for every subtree T ? T init , where T init consists of the subtrees of [?] whose roots have incoming edge init In other words, ? must simulate S regardless of its database In particular, this must be the case for the empty database. Thus, let T ? be the subtree in T init corresponding to the empty database. From the above it follows that Recall that ? |= f iff V S (T !e ) contains a path from the root labeled e.g.block, this happens iff V ? (T ? ) contains a path from the root labeled ? * .e.? * .g.? * .block. By definition of ?, since V S (T !e ) has no infinite branches of ?-transitions (in fact no ?-transitions at all), V ? (T ? ) may not have infinite branches of ?-transitions

T. Also-note-that and . Finitely, this is because in artifact systems, each transition other than init generates only finitely many non-isomorphic states from each given state) It follows that from each given node, the set of lengths of ?-paths originating at that node is bounded (otherwise, an easy induction shows that there must be an infinite path of ?-transitions from that node) This allows to effectively generate a breadth-first expansion of V ? (T ? ) (modulo isomorphism) until the first 3 non-? transitions occur along all branches, This allows deciding if a path labeled ? * .e.? * .g.? * .block starting from the root exists in V ? (T ? ), and provides a procedure for testing whether ? |= f

A. , S. Bourhis, P. And-marinoiu, and A. G. , The AXML artifact model, Time, 2009.

A. , S. Bourhis, P. And-vianu, and V. , Comparing workflow specification languages: a matter of views, ICDT, pp.78-89, 2011.

A. , S. Herr, L. And, and J. V. Den-bussche, Temporal versus first-order logic to query temporal databases, ACM SIGMOD- SIGACT-SIGART Symp. on Principles of Database Systems (PODS), 1996.

A. , S. Segoufin, L. And-vianu, and V. , Static analysis of active XML systems, ACM SIGMOD-SIGACT-SIGART Symp. on Principles of Database Systems (PODS). Full paper in ACM TODS, p.4, 2008.

A. , S. Vianu, V. Fordham, B. And-yesha, and Y. , Relational transducers for electronic commerce, Journal of Computer and System SciencesJCSS), vol.61, issue.2, pp.236-269, 2000.

A. , N. Atluri, V. And-huang, and W. , Modeling and analysis of workflows using Petri nets, Journal of Intelligent Information Systems, vol.10, issue.2, pp.131-158, 1998.

A. , N. Milo, T. Neven, F. Suciu, D. And-vianu et al., XML with data values: typechecking revisited, Journal of Computer and System SciencesJCSS), vol.66, issue.4, pp.688-727, 2003.

A. , R. Benedikt, M. Etessami, K. Godefroid, P. Reps et al., Analysis of recursive state machines, ACM Trans. Program. Lang. Syst, vol.27, issue.4, pp.786-818, 2005.

A. , M. Fan, W. And-libkin, and L. , Consistency of XML specifications, ACM SIGMOD-SIGACT-SIGART Symp. on Principles of Database Systems (PODS), 2002.

K. Bhattacharya, C. E. Gerede, R. Hull, R. Liu, and J. And-su, Towards Formal Analysis of Artifact-Centric Business Process Models, Int. Conf. on Business Process Management (BPM), 2007.

B. , M. Muscholl, A. Schwentick, T. Segoufin, L. And-david et al., Two-variable logic on words with data, IEEE Symp. on Logic in Computer Scince (LICS), 2006.

C. , D. Giacomo, G. D. Hull, R. And-su, and J. , Artifact-centric workflow dominance, IEEE Int. Conf. on Service-Oriented Computing and Applications (ICSOC, pp.130-143, 2009.

D. , S. And, and R. Lazi´clazi´-lazi´c, LTL with the freeze quantifier and register automata, ACM Trans. Comput. Logic, vol.10, issue.3, pp.1-30, 2009.

D. , A. Hull, R. Patrizi, F. And-vianu, and V. , Automatic verification of data-centric business processes, Int. Conf. on Database Theory (ICDT), 2009.

D. , A. Sui, L. And-vianu, and V. , Specification and verification of data-driven web applications, Journal of Computer and System SciencesJCSS), vol.73, issue.3, pp.442-474, 2007.

D. , V. And, and P. Gastin, First-order definable languages In Logic and Automata: History and Perspectives, pp.261-306, 2008.

D. , G. Hull, R. Kumar, B. Su, J. And-zhou et al., A framework for optimizing distributed workflow executions, 1999.

F. , W. And, and L. Libkin, On XML integrity constraints in the presence of DTDs, ACM SIGMOD-SIGACT-SIGART Symp. on Principles of Database Systems (PODS), 2001.

F. , C. Hull, R. And-su, and J. , Automatic construction of simple artifact-based business processes, Int. Conf. on Database Theory (ICDT), 2009.

G. , D. Hornick, M. And, and A. Sheth, An overview of workflow management: From process modeling to workflow infrastructure management, pp.119-153, 1995.

G. , C. E. Bhattacharya, K. And-su, and J. , Static analysis of business artifact-centric operational models, IEEE Int. Conf. on Service-Oriented Computing and Applications (ICSOC), 2007.

G. , C. E. And, and J. Su, Specification and verification of artifact behaviors in business process models, IEEE Int. Conf. on Service- Oriented Computing and Applications (ICSOC), 2007.

H. , R. Llirbat, F. Kumar, B. Zhou, G. Dong et al., Optimization techniques for data-intensive decision flows, Int. Conf. on Data Engineering (ICDE), 2000.

H. , R. Llirbat, F. Simon, E. Su, J. Dong et al., Declarative workflows that support easy modification and dynamic browsing, Proc. Int. Joint Conf. on Work Activities Coordination and Collaboration, 1999.

M. , D. Et, and . Al, OWL-S: Semantic markup for web services, 2003.

M. , S. A. Son, T. C. And-zeng, and H. , Semantic web services, IEEE Intelligent Systems, vol.16, issue.2, pp.46-53, 2001.

M. , W. And, and D. Paper, Using Harel's statecharts to model business workflows, J. of Database Management, vol.13, issue.3, pp.17-34, 2002.

N. , S. And-mcilraith, and S. , Simulation, verification and automated composition of web services, Int. World Wide Web Conf. (WWW), 2002.

N. , F. Schwentick, T. And-vianu, and V. , Finite state machines for strings over infinite alphabets, ACM Trans. Comput. Logic, vol.5, issue.3, pp.403-435, 2004.

N. , A. And, and N. S. Caswell, Business artifacts: An approach to operational specification, IBM Systems Journal, vol.42, issue.3, pp.428-445, 2003.

J. Van-benthem, Modal correspondence theory, 1976.

W. Van-der-aalst, Business Process Management Demystified: A Tutorial on Models, Systems and Standards for Workflow Management, Lectures on Concurrency and Petri Nets, 2004.

W. M. Van-der-aalst, THE APPLICATION OF PETRI NETS TO WORKFLOW MANAGEMENT, Journal of Circuits, Systems and Computers, vol.08, issue.01, pp.21-66, 1998.

W. M. Van-der-aalst, . And, and A. H. Hofstede, Workflow Patterns, Proc. of the Fourth Int. Workshop on Practical Use of Coloured Petri Nets and the CPN Tools, 2002.

W. , J. And, and A. Kumar, A framework for document-driven workflow systems, Int. Conf. on Business Process Management (BPM), pp.285-301, 2005.