Increasing productivity in high energy physics data mining with a domain specific visual query language [Elektronische Ressource] / vorgelegt von Vasco Miguel Moreira do Amaral

Increasing productivity in High Energy Physics data
mining with a Domain Speci c Visual Query
Language
Inauguraldissertation
zur Erlangung des akademischen Grades
eines Doktors der Naturwissenschaften
der Universit at Mannheim
vorgelegt von
Licenciado em Engenharia Inform atica e de Computadores
Instituto Superior Tecnico, Universidade Tecnica de Lisboa
Vasco Miguel Moreira do Amaral
aus Cascais, Portugal
Mannheim, 2004Dekan: Professor Dr. Jurgen Pottho , Universitat Mannheim
Referent: Dr. Guido Moerkotte, Universitat
Korreferent: Professor Dr. Reinhard Manner, Universitat Mannheim
Tag der mundlic hen Prufung: 17. Februar 2005Acknowledgments
I thank my mother, father, brother and Patricia for all the care, love
and moral support.
My gratitude goes also:
To Prof. Dr. Guido Moerkotte and to Dr. Sven Helmer, for believing
in my work and for all the technical support while advising my thesis.
To the Pi3 department for the friendly atmosphere that makes a
pleasant working environment.
To Simone Seeger for helping me with the English corrections of my
text.
To the Portuguese Governmental Foundation of Science and Tech-
nology FCT for the Phd. scholarship (ref. SFRH / BD / 8918 /
2002).
To Prof. Dr. Jo~ ao Carvalho project manager of the Portuguese LIP
Hera-b group, and to Prof. Dr. Ant onio Amorim. Due to them and
to this project I got introduced to the HEP world and contacted
with a real running HEP experiment.
To some of my good friends that contributed in a way or in the
other to this beautiful phase of my life: Levi Lucio, Andrej Gorisek,
Ant onio Rendas, Hugo Castelo Branco, Steven Aplin, Lawrence
Jones, Carl-Christian, Rita Torres, Daniel Peralta.
To Science, the noble and beautiful Mankind’s greatest invention!Zusammenfassung
Diese Arbeit entwickelt die erste anwendungsspezi sc he visuelle An-
fragesprache fur Hochenergiephysik. Nach dem aktuellen Stand der Tech-
nik ist Analyse von experimentellen Ergebnissen in der Hochenergiephysik
ein sehr aufwendiger Vorgang. Die Verwendung allgemeiner h oherer Pro-
grammiersprachen und komplexer Bibliotheken fur die Erstellung und
Wartung der Auswertungssoftware lenkt die Wissenschaftler von den Kern-
fragen ihres Gebiets ab. Unser Ansatz fuhrt eine neue Abstraktionsebene
in Form einer visuellen Programmiersprache ein, in der die Physiker die
gewunsc hten Ergebnisse in einer ihrem Anwendungsgebiet nahen Notation
formulieren k onnen.
Die Validierung der Hypothese erfolgte durch die Entwicklung einer
Sprache und eines Software-Prototyps. Neben einer formalen Syntax wird
die Sprache durch eine translationale Semantik de niert. Die Semantik
wird dabei mittels einer Ubersetzung in eine durch spezielle Gruppierung-
soperatoren erweiterte NF2-Algebra spezi ziert. Die vom Benutzer er-
stellten visuellen Anfragen werden durch einen Compiler in Code fur eine
Zielplattform ub ersetzt. Die Benutzbarkeit der Sprache wurde durch eine
Benutzerstudie validiert, deren qualitative und quantitative Ergebnisse
vorgestellt werden.Abstract
We propose the rst Domain Speci c Visual Query language for High
Energy Physics in order to tackle the problem of the physicist’s reduced
productivity in the High Energy Physics data mining phase. This ap-
proach comes in contrast to the current one where the user is distracted
from Physics by having to code his queries using a general purpose lan-
guage and complex frameworks. Our new language introduces an abstrac-
tion layer where the physicists describe their queries using a notation from
their domain of speech. We validated our approach by designing the lan-
guage and implementing a prototype. The language is de ned by a formal
syntax together with a semantics de ned translationally into a interme-
diate language, an NF2-Algebra extended by us with special grouping
operators. A visual language compiler generates a target source code that
deals with the particular existing frameworks. The usability of this pro-
posed language is also evaluated in this report by performing a study with
real users. We discuss in this report quantitative and qualitative mea-
surements concerning the user’s productivity, by comparing the former
traditional approach with our new one.Table of Contents
1 Introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Scienti c Domain of the Thesis . . . . . . . . . . . . . . . 3
1.4 Thesis Outline . . . . . . . . . . . . . . . . . . . . . . . . . 3
I Problem De nition 5
2 Context of the Work 7
2.1 Overview of High Energy Physics . . . . . . . . . . . . . . 7
2.2 The Detector . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.1 The Machinery . . . . . . . . . . . . . . . . . . . . 10
2.2.2 On-line System - the Triggers and Data Acquisition
System . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.3 O -line System - Data Reconstruction . . . . . . . 14
2.2.4 Analysis . . . . . . . . . . . . . . . . . . . . 17
2.3 Historic Perspective of the Analysis Systems . . . . . . . . 17
2.3.1 Unstructured Approach . . . . . . . . . . . . . . . 18
2.3.2 Analysis Frameworks . . . . . . . . . . . . . . . . . 21
2.3.3 Object-oriented Frameworks . . . . . . . . . . . . . 23
2.3.4 Current and Future Trends . . . . . . . . . . . . . . 24
2.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3 The Physics Analysis Process 27
3.1 De ning Physics Analysis- Low versus High Level . . . . . 27
3.2 Monte Carlo Simulation . . . . . . . . . . . . . . . . . . . 28
3.3 Analysis Schema . . . . . . . . . . . . . . . . . . . . . . . 29
iii TABLE OF CONTENTS
3.4 The Query Patterns . . . . . . . . . . . . . . . . . . . . . . 31
3.4.1 Query Steps . . . . . . . . . . . . . . . . . . . . . . 32
3.4.2 Example Query . . . . . . . . . . . . . . . . . . . . 34
3.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4 Problem statement 37
4.1 The Problem . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.2 Time Consuming Querying Process . . . . . . . . . . . . . 39
4.3 Motivation for the Thesis . . . . . . . . . . . . . . . . . . . 41
4.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
II Preliminary Concepts 43
5 Query Systems 45
5.1 Introduction to Query Systems . . . . . . . . . . . . . . . 45
5.2 Query Systems Taxonomy . . . . . . . . . . . . . . . . . . 46
5.2.1 Textual Query Languages . . . . . . . . . . . . . . 48
5.2.2 Non-Textual Query Languages . . . . . . . . . . . . 50
5.2.3 Visual Database Interfaces . . . . . . . . . . . . . . 58
5.2.4 Summary of Features . . . . . . . . . . . . . . . . . 59
5.3 Building a Visual Query System . . . . . . . . . . . . . . . 59
5.3.1 The Language . . . . . . . . . . . . . . . . . 61
5.3.2 Human Factors . . . . . . . . . . . . . . . . . . . . 61
5.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
6 Domain Speci c Modeling 63
6.1 Introduction to Domain Speci cit y . . . . . . . . . . . . . 63
6.2 Modeling Strategy . . . . . . . . . . . . . . . . . . . . . . 64
6.3 DSL Engineering Process . . . . . . . . . . . . . . . . . . . 66
6.4 Advantages and Disadvantages . . . . . . . . . . . . . . . . 66
6.5 DSL \Attempts" in HEP . . . . . . . . . . . . . . . . . . . 68
6.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
III Tackling the Problem 71
7 The Solution 73
7.1 Proposed Approach . . . . . . . . . . . . . . . . . . . . . . 73TABLE OF CONTENTS iii
7.2 Why a DSVQL? . . . . . . . . . . . . . . . . . . . . . . . . 75
7.3 Expected Results . . . . . . . . . . . . . . . . . . . . . . . 75
7.3.1 System Overview . . . . . . . . . . . . . . . . . . . 76
7.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
8 Query Language - PHEASANT QL 79
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 79
8.2 Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
8.2.1 Concrete versus Abstract Syntax . . . . . . . . . . 80
8.2.2 Overview of PHEASANT QL . . . . . . . . . . . . 80
8.2.3 PHEASANT QL Alphabet - Symbolic Notation . . 81
8.2.4 Grammar . . . . . . . . . . . . . . . . . . . . . . . 89
8.3 Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
8.3.1 The Target Language - Intermediate Algebra Oper-
ators . . . . . . . . . . . . . . . . . . . . . . . . . . 95
8.3.2 Language Description . . . . . . . . . . . . . . . . . 111
8.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
9 Prototype Framework - PHEASANT 139
9.1 General Overview . . . . . . . . . . . . . . . . . . . . . . . 139
9.1.1 Roles and Use Cases . . . . . . . . . . . . . . . . . 140
9.1.2 Architecture . . . . . . . . . . . . . . . . . . . . . . 141
9.1.3 Technology Used for the Implementation . . . . . . 143
9.2 User Interface - The Visual Editor . . . . . . . . . . . . . . 144
9.2.1 Related Work and Design Decisions . . . . . . . . . 144
9.2.2 The Architecture of the Visual Editor . . . . . . . . 147
9.2.3 Future Work . . . . . . . . . . . . . . . . . . . . . . 151
9.3 The Generation of a Logical Query Plan . . . . . . . . . . 152
9.3.1 AST Generator . . . . . . . . . . . . . . . . . . . . 153
9.3.2 Logical Query Plan Generator . . . . . . .