We propose a method of syntactic pattern recognition for eXtensible Markup Language query matching on eXtensible Markup Language streams. A set of declarative grammar rules is generated, and then its parser, which is produced by full-fledged compiler tools, can be used to match multiple queries concurrently with only one-time scan on eXtensible Markup Language streams. The grammar is proved unambiguous with lemmas and theorems. We also analyze the time complexity and prove the correctness of multiple-query matching. Several experiments were conducted to demonstrate the efficiency and scalability of the proposed method in various aspects. As a result, the proposed method is beneficial for building efficient eXtensible Markup Language–based publish/subscribe applications.
AltinelMFranklinMJ (2000) Efficient filtering of XML documents for selective dissemination of information. In: Proceedings of the 26th international conference on very large data bases, Cairo, Egypt, 10–14 September, pp. 53–64. Burlington, MA, USA: Morgan Kaufmann.
3.
BoyerRSMooreJS (1977) A fast string searching algorithm. Communications of the ACM20(10): 762–772.
4.
BrunoNKoudasNSrivastavaD (2002) Holistic twig joins: optimal XML pattern matching. In: Proceedings of the 2002 ACM SIGMOD international conference on management of data, Madison, WI, 3–6 June, pp. 310–321. New York: ACM.
5.
ChanCYFelberPGarofalakisM. (2002) Efficient filtering of XML documents with XPath expressions. VLDB Journal11(4): 354–379.
6.
ChouCPJeaKF (2013) Grammar-based matching of multiple continuous queries on XML streams. In: Proceedings of the 7th International conference on complex, intelligent, and software intensive systems, Taichung, Taiwan, 3–5 July.
7.
ChouCPJeaKFLiaoHH (2011) A syntactic approach to twig-query matching on XML streams. Journal of Systems and Software84(6): 993–1007.
8.
DiaoYAltinelMFranklinMJ. (2003) Path sharing and predicate evaluation for high-performance XML filtering. ACM Transactions on Database Systems28(4): 467–516.
9.
FredkinE (1960) Trie memory. Communications of the ACM3(9): 490–499.
10.
FuKSAizermanMA (1976) Syntactic methods in pattern recognition. IEEE Transactions on Systems Man and Cybernetics6(8): 590–591.
11.
HurWBaeHKangSH (2003) Customizable workflow monitoring. Concurrent Engineering: Research and Applications11(4): 313–325.
12.
JoungYSLimJHHyunSJ. (2001) A metadata repository system for an efficient description of visual multimedia documents. Concurrent Engineering: Research and Applications9(2): 93–104.
13.
KwonJRaoPMoonB. (2005) FiST: scalable XML document filtering by sequencing twig patterns. In: Proceedings of the 31st international conference on very large data bases, Trento, 4–6 October, pp. 217–228. New York: ACM.
14.
KwonJRaoPMoonB. (2008) Value-based predicate filtering of XML documents. Data & Knowledge Engineering67(1): 51–73.
15.
KwonJRaoPMoonB. (2009) Fast XML document filtering by sequencing twig patterns. ACM Transactions on Internet Technology9(4): 13:1–13:51.
LiuZLZhangZChenY (2012) A scenario-based approach for requirements management in engineering design. Concurrent Engineering: Research and Applications20(2): 99–109.
18.
RaoPMoonB (2004) PRIX: indexing and querying XML using prufer sequences. In: Proceedings of the 20th international conference on data engineering, Boston, MA, 30 March–2 April, pp. 288–299. New York: IEEE.
19.
SalloumMTsotrasVJ (2009) Efficient and scalable sequence-based XML filtering. In: Proceedings of the 12th international workshop on the web and databases, Providence, RI, 28 June.
20.
TerryDGoldbergDNicholsD. (1992) Continuous queries over append-only databases. In: Proceedings of the 1992 ACM SIGMOD international conference on management of data, vol. 21, San Diego, CA, 2–5 June, pp. 321–330. New York: ACM.
21.
WuXTheodoratosD (2013) A survey on XML streaming evaluation techniques. VLDB Journal22(2): 177–202.
