2. ANALYTICAL QUERY PROCESSINGA num

2. ANALYTICAL QUERY PROCESSING
A number of domain-specific analytical queries are seen in
the scientific databases. Many of these queries take superlinear
processing time if handled in the traditional DBMS
way. Some examples of basic queries in molecular simulation
databases are listed in table 1. Many of these queries return
the results in the form of histograms as approximations of
statistical distributions. The query processing time for large
volume data sets is significantly high. The complexity of the
query adds to this time, making the running time unimaginable.
The disk I/O and network transfer times worsen the
execution time even more. As we have seen in the introduction
section, the queries in scientific data sets are analytical
and therefore make at least one pass over the whole data
set. These queries can not be answered quickly using any of
the traditional query execution methods or plans. Thus, the
processing of queries on scientific data sets is very expensive.
In this thesis we propose to compute queries efficiently and
compress the data for saving disk space, I/O and transmission
time (details in section 3).
2.1 General Approach
The traditional databases answer queries by generating
plans that use the indexes whenever possible. A multidimensional
tree index is built to store a digest of the data.
Each tree node caches such a digest of all the data points
it holds. At query runtime, aggregate queries are answered
by accessing the digest of the specific region. The distributive
queries can be answered by storing the regional query
results as digest. However, storing algebraic aggregates in
the from of digest needs further exploration of the field. We
propose an approach that requires linear time to build thetree. Small queries can be answered in constant time and the
regional queries in time proportional to the number of tree
nodes accessed at runtime. We propose an algorithm that
builds a Quad/Oct-tree structure to partition the data into
different disjoint regions to answer the queries efficiently.
Correlation Functions: Holistic aggregates are one of
the challenging queries in scientific data sets. Efficient processing
of such queries is not possible by caching a very small
digest of the data. A group of holistic aggregates we focus
on are called multi-body correlation functions (m-BCF) [20].
A m-BCF computes statistical measure for all m-particle tuples
in the data. Processing m-BCF queries, on data of Nbodies,
in naive way requires O(Nm) computational time.
As an example of 2-BCF, the distribution of all pairwise
distances is known as a radial distribution function (RDF)
and often computed in the form of a 1D histogram named
Spatial Distribution Histogram (SDH). Similarly, the density
function can be viewed as a 1-BCF. Being the building
blocks of many critical analytics [6, 19], the m-BCFs are of
importance to scientific data analysis and thus the focus of
this part of the thesis work.
The obvious challenges for such query processing are: 1)
identify the correct data digest to store in the tree nodes;
and 2) design of query processing algorithms that utilize
such digest.

ผลลัพธ์ (ไทย) 1:

2. แบบสอบถามวิเคราะห์ประมวลผลจำนวนแบบสอบถามวิเคราะห์เฉพาะโดเมนจะเห็นในฐานข้อมูลทางวิทยาศาสตร์ ใช้แบบสอบถามเหล่านี้มากมาย superlinearเวลาประมวลผลถ้าจัดการใน DBMS แบบดั้งเดิมวิธีการ ตัวอย่างแบบสอบถามพื้นฐานในการจำลองโมเลกุลฐานข้อมูลแสดงในตาราง 1 ของแบบสอบถามเหล่านี้กลับผลลัพธ์ในรูปแบบของฮิสโตแกรมเป็นเพียงการประมาณของการกระจายทางสถิติ เวลาการประมวลผลแบบสอบถามสำหรับขนาดใหญ่ค่าระดับเสียงจะสูงมาก ความซับซ้อนของการสอบถามเพิ่มเวลานี้ ทำให้ใช้เวลาคับขันWorsen ดิสก์ I/O และเวลาโอนย้ายเครือข่ายเวลาดำเนินการมากยิ่งขึ้น เราได้เห็นในบทนำส่วน แบบสอบถามในชุดข้อมูลทางวิทยาศาสตร์วิเคราะห์ทำผ่านน้อยกว่าข้อมูลทั้งหมดดังนั้นตั้งค่า แบบสอบถามเหล่านี้สามารถไม่ได้รับการตอบอย่างรวดเร็วโดยใช้ใด ๆวิธีการดำเนินการแบบสอบถามดั้งเดิมหรือแผน ดังนั้น การประมวลผลการสอบถามเกี่ยวกับชุดข้อมูลทางวิทยาศาสตร์มีราคาแพงมากในวิทยานิพนธ์นี้ เราเสนอการคำนวณแบบสอบถามมีประสิทธิภาพ และบีบอัดข้อมูลเพื่อประหยัดเนื้อที่ I/O และส่งเวลา (รายละเอียดในส่วนที่ 3)2.1 วิธีทั่วไปฐานข้อมูลดั้งเดิมตอบแบบสอบถาม โดยสร้างแผนที่ใช้ดัชนีเมื่อใดก็ ตามที่เป็นไปได้ มีหลายมิติดัชนีแผนภูมิถูกสร้างขึ้นเพื่อเก็บย่อยของข้อมูลแต่ละโหนดแผนภูมิมมากเช่นย่อยของจุดข้อมูลทั้งหมดจะเก็บ ในขณะทำแบบสอบถาม ตอบแบบสอบถามโดยเข้าถึงแยกย่อยเฉพาะภาค การแจกแจงสามารถจะตอบแบบสอบถาม โดยเก็บแบบสอบถามระดับภูมิภาคผลลัพธ์เป็นการแยกย่อย อย่างไรก็ตาม เก็บผลพีชคณิตในการจากของย่อยต้องเติมสำรวจของฟิลด์ เราเสนอวิธีการที่ต้องใช้เวลาเชิงเส้นเพื่อสร้าง thetree สอบถามขนาดเล็กสามารถตอบในเวลาที่คงและแบบสอบถามระดับภูมิภาคในสัดส่วนกับจำนวนของต้นไม้โหนที่รันไทม์การเข้าถึง เราเสนอขั้นตอนวิธีการที่สร้างเป็นรูปสี่เหลี่ยม/ตุลาคมโครงสร้างสามารถแบ่งข้อมูลลงในภูมิภาคตัวแตกต่างกันเพื่อตอบคำถามมีประสิทธิภาพความสัมพันธ์ฟังก์ชัน: ผลแบบองค์รวมเป็นหนึ่งแบบสอบถามที่ท้าทายในชุดข้อมูลทางวิทยาศาสตร์ ประมวลผลที่มีประสิทธิภาพแบบสอบถามดังกล่าวเป็นไปไม่ได้ โดยแคชมีขนาดเล็กมากย่อยของข้อมูล กลุ่มของเราเน้นผลแบบองค์รวมบนเรียกว่าความสัมพันธ์ของร่างกายหลายฟังก์ชัน (m-BCF) [20]M-BCF ตัววัดสถิติ tuples m-อนุภาคทั้งหมดในข้อมูล ประมวลผลแบบสอบถาม m-BCF ข้อมูลของ Nbodiesในขำน่า ทางต้องใช้เวลาคำนวณ O(Nm)เป็นตัวอย่าง 2-BCF กระจายทั้งแพร์ไวส์เรียกว่าเป็นฟังก์ชันการกระจายรัศมี (RDF) ระยะทางและมักจะมีการคำนวณในแบบฟอร์มของฮิสโตแกรม 1D ชื่อกระจายฮิสโตแกรม (SDH) ในทำนองเดียวกัน ความหนาแน่นฟังก์ชันสามารถดูได้เป็น 1-BCF เป็นอาคารบล็อกของหลายสำคัญวิเคราะห์ [6, 19], BCFs เมตรมีความสำคัญการวิเคราะห์ข้อมูลทางวิทยาศาสตร์ดังนั้นจุดเน้นของส่วนนี้ของงานวิทยานิพนธ์ความท้าทายชัดเจนสำหรับการประมวลผลแบบสอบถามดังกล่าวมี: 1)ระบุแยกย่อยข้อมูลถูกเก็บในโหนดแผนภูมิและ 2) ของอัลกอริทึมที่ใช้ในการประมวลผลแบบสอบถามแยกย่อยดังกล่าว

ผลลัพธ์ (ไทย) 3:

2 . วิเคราะห์ประมวลผลแบบสอบถาม
หมายเลขของโดเมนเฉพาะวิเคราะห์แบบสอบถามจะเห็นใน
ฐานข้อมูลทางวิทยาศาสตร์ หลายคำถามเหล่านี้ต้องใช้เวลาในการประมวลผล superlinear
ถ้าจัดการในทาง DBMS
แบบดั้งเดิม ตัวอย่างบางส่วนของคำถามพื้นฐานในฐานข้อมูลจำลอง
โมเลกุลอยู่ในตารางที่ 1 หลายคำถามเหล่านี้กลับ
ผลลัพธ์ในรูปแบบของฮิสโตแกรมเป็นการ
การแจกแจงทางสถิติ เวลาการประมวลผลแบบสอบถามสำหรับชุดข้อมูลขนาดใหญ่
เล่มเป็นอย่างสูง ความซับซ้อนของ
สอบถามเพิ่มครั้งนี้ ทำให้เวลาวิ่งไม่ได้ .
ดิสก์ I / O และเวลาโอนเครือข่ายเสื่อมโทรม
ประหารเวลามากขึ้น ตามที่เราได้เห็นในส่วนบทนำ
, คําสั่งในชุดข้อมูลทางวิทยาศาสตร์ คือวิเคราะห์
จึงทำให้อย่างน้อยหนึ่งผ่านข้อมูลทั้งหมด
ชุด คำถามนี้ไม่สามารถตอบได้อย่างรวดเร็วโดยใช้ใด ๆของวิธีการแบบดั้งเดิมตาม
แบบสอบถามหรือแผน ดังนั้น ,
การประมวลผลของแบบสอบถามชุดข้อมูลทางวิทยาศาสตร์ที่มีราคาแพงมาก .
ในวิทยานิพนธ์นี้ได้เสนอค่าต่างๆ ได้อย่างมีประสิทธิภาพ และ
การบีบอัดข้อมูลเพื่อประหยัดพื้นที่ดิสก์ I / O และเวลาส่ง
( รายละเอียดในข้อ 3 )
21 วิธีการทั่วไป

แบบฐานข้อมูลตอบแบบสอบถามโดยการสร้างแผนการที่ใช้ดัชนีเมื่อใดก็ตามที่เป็นไปได้ ดัชนีต้นไม้หลายมิติ
ถูกสร้างขึ้นเพื่อเก็บย่อยของข้อมูล .
แต่ละต้นโหนดแคชเช่นย่อยทุกจุดข้อมูล
มันถือ ที่ตอบแบบสอบถามแบบสอบถาม Runtime รวม
โดยการเข้าถึงย่อยของภูมิภาคที่เฉพาะเจาะจง การกระจาย
แบบสอบถามสามารถตอบโดยเก็บผลลัพธ์ของแบบสอบถาม
ระดับย่อย อย่างไรก็ตาม การจัดเก็บตัวอย่างพีชคณิตใน
จากของย่อยต้องการสำรวจเพิ่มเติมในเขต เราเสนอวิธีการที่ต้องใช้
เวลาเชิงเส้นเพื่อสร้าง thetree . ข้อสงสัยเล็กๆ สามารถตอบได้ในเวลาที่คงที่และ
แบบสอบถามในภูมิภาคเวลาเป็นสัดส่วนกับจำนวนโหนดต้นไม้
เข้าถึง Runtime .เราเสนออัลกอริทึมที่
สร้างรูปสี่เหลี่ยม / ต.ค. ต้นไม้โครงสร้างพาร์ทิชันข้อมูลลง
ตอบแบบสอบถามแตกต่างกันยู่ภูมิภาคได้อย่างมีประสิทธิภาพ ฟังก์ชันสหสัมพันธ์ : ขัน

แบบองค์รวมเป็นหนึ่งในความท้าทายต่างๆ ในชุดข้อมูลทางวิทยาศาสตร์
การประมวลผลที่มีประสิทธิภาพ เช่น แบบสอบถามเป็นไปไม่ได้โดยแคชมีขนาดเล็กมาก
ย่อยของข้อมูล กลุ่มเราเน้น
แบบมวลรวมเมื่อเรียกฟังก์ชันสหสัมพันธ์ multi-body ( m-bcf ) [ 20 ] .
เป็น m-bcf คำนวณสถิติวัดทั้งหมด m-particle ทูเปิล
ในข้อมูล การประมวลผล m-bcf สอบถามข้อมูล nbodies
ในทาง , ไร้เดียงสาต้อง O ( nm ) เวลาคำนวณ .
เป็นตัวอย่างของ 2-bcf , การกระจายของระยะทางคู่
ทั้งหมดเป็นที่รู้จักกันเป็นฟังก์ชันการกระจายรัศมี ( RDF )
และมักจะทำในรูปแบบของกราฟและกราฟการกระจายเชิงพื้นที่ของ 1D ชื่อ
( SDH ) ส่วนฟังก์ชันความหนาแน่น
สามารถดูเป็น 1-bcf . การสร้างบล็อกของการวิเคราะห์ที่สำคัญมาก
6 [ 19 ] , m-bcfs มี
ความสำคัญการวิเคราะห์ข้อมูลทางวิทยาศาสตร์และดังนั้นจึงโฟกัส
นี้ส่วนหนึ่งของงานวิทยานิพนธ์ .
ความท้าทายที่ชัดเจนสำหรับการประมวลผลแบบสอบถามดังกล่าว คือ 1 )
ระบุข้อมูลที่ถูกต้องแยกย่อยเก็บในโหนด ;
2 ) แบบสอบถามการประมวลผลการออกแบบอัลกอริทึมที่ใช้
เรื่องย่อย