國立虎尾科技大學 |

Early Detection of Business Rule Violations.

Record Type:	Language materials, manuscript : Monograph/item
Title/Author:	Early Detection of Business Rule Violations./
Author:	Mackey, Isaac A.
Description:	1 online resource (152 pages)
Notes:	Source: Dissertations Abstracts International, Volume: 85-04, Section: B.
Contained By:	Dissertations Abstracts International85-04B.
Subject:	Computer science. -
Online resource:	click for full text (PQDT)
ISBN:	9798380616676

Early Detection of Business Rule Violations.
Mackey, Isaac A.

Early Detection of Business Rule Violations. - 1 online resource (152 pages)

Source: Dissertations Abstracts International, Volume: 85-04, Section: B.

Thesis (Ph.D.)--University of California, Santa Barbara, 2023.

Includes bibliographical references

The rise of automated systems and sensor networks in virtually all areas of industry and social life means many technologies produce streams of events rich with information. These technologies demand algorithms for evaluating queries on streams, coordinating systems that communicate with events, and monitoring streams with respect to specified constraints. In monitoring, constraints that define correct behavior, e.g., business goals, legal requirements, resource limitations, or safety and security concerns are specified in a formal language; then, an event stream is analyzed at runtime to determine if the constraints are satisfied or violated. To make monitoring effective, it is important to detect constraint violations at the earliest possible time, which we call the early violation detection problem.We study early violation detection for a class of constraints called rules that restrict time gaps between events and compare events' data contents. We show that (1) the general problem of early violation detection for an arbitrary set of rules is unsolvable and (2) early violation detection is possible for various subclasses of rules. For (1), we show early violation detection is closely related to the problem of finite satisfiability (whether or not a given set of rules can be satisfied by a finite event stream) and prove that finite satisfiability for a set of rules is undecidable with a reduction from the empty-tape Turing machine halting problem, which implies that early violation detection is unsolvable in general. For (2), we study restricted classes of rules. A recent proof of Kamp's Theorem provides a translation algorithm for "dataless" rules through translation to linear temporal logic. yielding formulas hyper-exponential in the size of the input rule.We present translation algorithms for two subclasses of dataless rules, improving the output size from hyper-exponential to single- and double-exponential, respectively. For rules with data, we first present a technique that calculates deadlines from time gaps between events, then use deadlines for early violation detection for individual rules. We extend these algorithms to monitor an acyclic set of rules by applying a chase process and satisfiability testing. We also report the performance of an implementation of these algorithms. Finally, we consider acyclic sets of rules with aggregation functions over time windows, combining the chase and satisfiability techniques with an encoding of aggregation functions in Presburger arithmetic.

Electronic reproduction.
Ann Arbor, Mich. :
ProQuest,
2024

Mode of access: World Wide Web

ISBN: 9798380616676Subjects--Topical Terms:

573171
Computer science.
Subjects--Index Terms:

Automated reasoningIndex Terms--Genre/Form:

554714
Electronic books.

Early Detection of Business Rule Violations.
LDR:03807ntm a2200361K 4500 001 1141624
005 20240318062657.5
006 m o d
007 cr mn ---uuuuu
008 250605s2023 xx obm 000 0 eng d
020 $a 9798380616676
035 $a (MiAaPQ)AAI30640206
035 $a AAI30640206
040 $a MiAaPQ $b eng $c MiAaPQ $d NTU
100 1 $a Mackey, Isaac A. $3 1465525
245 1 0 $a Early Detection of Business Rule Violations.
264 0 $c 2023
300 $a 1 online resource (152 pages)
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
500 $a Source: Dissertations Abstracts International, Volume: 85-04, Section: B.
500 $a Advisor: Su, Jianwen.
502 $a Thesis (Ph.D.)--University of California, Santa Barbara, 2023.
504 $a Includes bibliographical references
520 $a The rise of automated systems and sensor networks in virtually all areas of industry and social life means many technologies produce streams of events rich with information. These technologies demand algorithms for evaluating queries on streams, coordinating systems that communicate with events, and monitoring streams with respect to specified constraints. In monitoring, constraints that define correct behavior, e.g., business goals, legal requirements, resource limitations, or safety and security concerns are specified in a formal language; then, an event stream is analyzed at runtime to determine if the constraints are satisfied or violated. To make monitoring effective, it is important to detect constraint violations at the earliest possible time, which we call the early violation detection problem.We study early violation detection for a class of constraints called rules that restrict time gaps between events and compare events' data contents. We show that (1) the general problem of early violation detection for an arbitrary set of rules is unsolvable and (2) early violation detection is possible for various subclasses of rules. For (1), we show early violation detection is closely related to the problem of finite satisfiability (whether or not a given set of rules can be satisfied by a finite event stream) and prove that finite satisfiability for a set of rules is undecidable with a reduction from the empty-tape Turing machine halting problem, which implies that early violation detection is unsolvable in general. For (2), we study restricted classes of rules. A recent proof of Kamp's Theorem provides a translation algorithm for "dataless" rules through translation to linear temporal logic. yielding formulas hyper-exponential in the size of the input rule.We present translation algorithms for two subclasses of dataless rules, improving the output size from hyper-exponential to single- and double-exponential, respectively. For rules with data, we first present a technique that calculates deadlines from time gaps between events, then use deadlines for early violation detection for individual rules. We extend these algorithms to monitor an acyclic set of rules by applying a chase process and satisfiability testing. We also report the performance of an implementation of these algorithms. Finally, we consider acyclic sets of rules with aggregation functions over time windows, combining the chase and satisfiability techniques with an encoding of aggregation functions in Presburger arithmetic.
533 $a Electronic reproduction. $b Ann Arbor, Mich. : $c ProQuest, $d 2024
538 $a Mode of access: World Wide Web
650 4 $a Computer science. $3 573171
650 4 $a Computer engineering. $3 569006
653 $a Automated reasoning
653 $a Runtime monitoring
653 $a Temporal logic
655 7 $a Electronic books. $2 local $3 554714
690 $a 0984
690 $a 0464
710 2 $a ProQuest Information and Learning Co. $3 1178819
710 2 $a University of California, Santa Barbara. $b Computer Science. $3 1182528
773 0 $t Dissertations Abstracts International $g 85-04B.
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=30640206 $z click for full text (PQDT)