พีชคณิตสารสนเทศ

Q: หลักการพื้นฐานและคำจำกัดความ

สัจพจน์ของพีชคณิตสองประเภทนอกเหนือจากสัจพจน์ของแลตทิซ: ( Φ , ดี ) {\displaystyle (\Phi ,D)} ดี {\displaystyle D}

คำว่า " พีชคณิตสารสนเทศ " หมายถึงเทคนิคทางคณิตศาสตร์ในการประมวลผลสารสนเทศ ทฤษฎีสารสนเทศแบบคลาสสิกมีที่มาจากโคลด แชนนอน เป็นทฤษฎีเกี่ยวกับการส่งผ่านสารสนเทศ โดยพิจารณาถึงการสื่อสารและการจัดเก็บ อย่างไรก็ตาม ที่ผ่านมายังไม่ได้พิจารณาว่าสารสนเทศมาจากแหล่งต่างๆ และมักจะถูกรวมเข้าด้วยกัน นอกจากนี้ ในทฤษฎีสารสนเทศแบบคลาสสิกยังละเลยประเด็นที่ว่าเราต้องการแยกส่วนต่างๆ ออกจากข้อมูลชิ้นหนึ่งที่เกี่ยวข้องกับคำถามเฉพาะเจาะจง

การกำหนดการดำเนินการเหล่านี้ในเชิงคณิตศาสตร์นำไปสู่พีชคณิตของข้อมูลซึ่งอธิบายโหมดพื้นฐานของการประมวลผลข้อมูล พีชคณิตดังกล่าวเกี่ยวข้องกับรูปแบบทางคณิตศาสตร์หลายอย่างของวิทยาการคอมพิวเตอร์ซึ่งดูเหมือนจะแตกต่างกันในแง่ผิวเผิน เช่น ฐานข้อมูลเชิงสัมพันธ์ ระบบตรรกะเชิงรูปธรรมหลายระบบ หรือปัญหาเชิงตัวเลขของพีชคณิตเชิงเส้นสิ่งนี้ช่วยให้สามารถพัฒนาขั้นตอนการประมวลผลข้อมูลทั่วไป และทำให้เกิดการรวมวิธีการพื้นฐานของวิทยาการคอมพิวเตอร์ โดยเฉพาะอย่างยิ่ง การ ประมวล ผลข้อมูลแบบกระจาย

ข้อมูลเกี่ยวข้องกับคำถามที่เฉพาะเจาะจง มาจากแหล่งข้อมูลที่แตกต่างกัน ต้องมีการรวบรวม และสามารถมุ่งเน้นไปที่คำถามที่น่าสนใจได้ จากการพิจารณาเหล่านี้ พีชคณิตข้อมูล ( Kohlas 2003 ) จึงเป็นพีชคณิตสองประเภท : $(\Phi ,D)$

โดยที่เป็นเซมิกรุปซึ่งแสดงถึงการรวมกันหรือการรวมกลุ่มของข้อมูล และเป็นแลตทิซของโดเมน (ที่เกี่ยวข้องกับคำถาม) ซึ่งลำดับบางส่วนสะท้อนถึงระดับความละเอียดของโดเมนหรือคำถาม และเป็นการดำเนินการแบบผสมที่แสดงถึงการโฟกัสหรือการสกัดข้อมูล $\Phi$ $D$

ข้อมูลและการดำเนินงาน

กล่าวโดยละเอียด ในพีชคณิตแบบสองประเภทจะมีการกำหนดการดำเนินการต่อไปนี้ $(\Phi ,D)$

การผสมผสาน: $\otimes :\Phi \otimes \Phi \rightarrow \Phi ,~(\phi ,\psi )\mapsto \phi \otimes \psi$
การโฟกัส: $\Rightarrow :\Phi \otimes D\rightarrow \Phi ,~(\phi ,x)\mapsto \phi ^{\Rightarrow x}$

นอกจากนี้ยังมีการกำหนดการดำเนินการแบบแลตติสทั่วไป (เช่น การตัดกันและการรวมเข้าด้วยกัน) ไว้ ด้วย $D$

หลักการพื้นฐานและคำจำกัดความ

สัจพจน์ของพีชคณิตสองประเภทนอกเหนือจากสัจพจน์ของแลตทิซ: $(\Phi ,D)$ $D$

เซมิกรุ๊ป: $\Phi$ เป็นเซมิกรุปสลับที่ได้ภายใต้การรวมกับองค์ประกอบที่เป็นกลาง (ซึ่งแสดงถึงข้อมูลที่ว่างเปล่า)
การกระจายตัวของการโฟกัสเหนือการรวมกัน: $(\phi ^{\Rightarrow x}\otimes \psi )^{\Rightarrow x}=\phi ^{\Rightarrow x}\otimes \psi ^{\Rightarrow x}$

เพื่อให้ข้อมูลหนึ่งสามารถนำไปรวมกับข้อมูลอีกข้อมูลหนึ่งในโดเมนเดียวกันได้เราอาจเริ่มต้นด้วยการเน้นข้อมูลที่สองก่อนแล้วค่อยนำมารวมกัน ก็ได้ $x$ $x$ $x$

การถ่ายทอดของการโฟกัส: $(\phi ^{\Rightarrow x})^{\Rightarrow y}=\phi ^{\Rightarrow x\wedge y}$

เพื่อให้ข้อมูลเกี่ยวกับและ มีความชัดเจนมากขึ้น เราอาจเน้นข้อมูลไปที่ $x$ $y$ $x\wedge y$

ภาวะเสื่อมสมรรถภาพทางเพศ: $\phi \otimes \phi ^{\ลูกศรขวา x}=\phi$

ข้อมูลหนึ่งๆ ที่นำมารวมกับส่วนอื่นๆ ของตัวมันเอง ไม่ได้ก่อให้เกิดสิ่งใหม่ใดๆ

สนับสนุน: $\forall \phi \in \Phi ,~\exists x\in D$ โดยที่ $\phi =\phi ^{\ลูกศรขวา x}$

ข้อมูลแต่ละส่วนอ้างอิงถึงอย่างน้อยหนึ่งโดเมน (คำถาม)

พีชคณิตสองประเภทที่สอดคล้องกับสัจพจน์เหล่านี้เรียกว่าพีชคณิต สารสนเทศ $(\Phi ,D)$

ลำดับของข้อมูล

สามารถกำหนดลำดับข้อมูลบางส่วนได้โดยการกำหนดเงื่อนไข ว่า ถ้าหมายความว่ามีข้อมูลน้อยกว่าถ้า ไม่เพิ่มข้อมูลใหม่ใดๆ ให้กับเซมิกรุปเป็นเซมิแลตทิซที่สัมพันธ์กับลำดับนี้ กล่าวคือสัมพันธ์กับโดเมน (คำถาม) ใดๆสามารถกำหนดลำดับบางส่วนได้โดยการกำหนดเงื่อนไขว่า ถ้ามันแสดงถึงลำดับของเนื้อหาข้อมูลของและที่สัมพันธ์กับโดเมน (คำถาม) $\phi \leq \psi$ $\phi \otimes \psi =\psi$ $\phi$ $\psi$ $\psi$ $\Phi$ $\phi \otimes \psi =\phi \vee \psi$ $x\in D$ $\phi \leq _{x}\psi$ $\phi ^{\Rightarrow x}\leq \psi ^{\Rightarrow x}$ $\phi$ $\psi$ $x$

พีชคณิตข้อมูลที่มีป้ายกำกับ

คู่โดยที่และก่อให้เกิดพีชคณิตสารสนเทศที่มีป้ายกำกับ กล่าว โดยละเอียดกว่า นั้นในพีชคณิตแบบเรียงลำดับสองประเภทจะมีการกำหนดการดำเนินการต่อไปนี้ $(\phi ,x)\$ $\phi \in \Phi$ $x\in D$ $\phi ^{\ลูกศรขวา x}=\phi$ $(\Phi ,D)\$

การติดฉลาก: $d(\phi ,x)=x\$
การผสมผสาน: $(\phi ,x)\otimes (\psi ,y)=(\phi \otimes \psi ,x\vee y)~~~~$
การฉายภาพ: $(\phi ,x)^{\downarrow y}=(\phi ^{\Rightarrow y},y){\text{ for }}y\leq x$

แบบจำลองของพีชคณิตสารสนเทศ

ต่อไปนี้เป็นรายการตัวอย่างของพีชคณิตสารสนเทศที่ไม่ครบถ้วน:

พีชคณิตเชิงสัมพันธ์ : การลดรูปของพีชคณิตเชิงสัมพันธ์ที่มีการเชื่อมต่อตามธรรมชาติเป็นส่วนประกอบ และการฉายภาพตามปกติ คือ พีชคณิตข้อมูลที่มีป้ายกำกับดูตัวอย่าง
ระบบข้อจำกัด : ข้อจำกัดก่อให้เกิดพีชคณิตสารสนเทศ ( Jaffar & Maher 1994 )
Semiring valued algebras : C-Semirings induce information algebras ( Bistarelli, Montanari & Rossi1997 );( Bistarelli et al. 1999 );( Kohlas & Wilson 2006 )
ตรรกศาสตร์ : ระบบตรรกศาสตร์หลายระบบก่อให้เกิดพีชคณิตสารสนเทศ ( Wilson & Mengin 1999 ) รีดักต์ของพีชคณิตทรงกระบอก ( Henkin, Monk & Tarski 1971 ) หรือพีชคณิตพหุนามเป็นพีชคณิตสารสนเทศที่เกี่ยวข้องกับตรรกศาสตร์ภาคแสดง ( Halmos 2000 )
พีชคณิตของโมดูล : ( Bergstra, Heeering & Klint 1990 );( de Lavalette 1992 )
ระบบเชิงเส้น : ระบบสมการเชิงเส้นหรืออสมการเชิงเส้นก่อให้เกิดพีชคณิตสารสนเทศ ( Kohlas 2003 )

ตัวอย่างการคำนวณ: พีชคณิตเชิงสัมพันธ์

ให้เป็นเซตของสัญลักษณ์ที่เรียกว่าแอตทริบิวต์ (หรือชื่อคอลัมน์ ) สำหรับแต่ละให้เป็นเซตที่ไม่ว่างเปล่า ซึ่งเป็นเซตของค่าที่เป็นไปได้ทั้งหมดของแอตทริบิวต์ $α$ ตัวอย่างเช่น ถ้า แล้วอาจเป็นเซตของสตริง ในขณะที่และเป็นเซตของจำนวนเต็มที่ไม่เป็นลบทั้งคู่ ${\mathcal {A}}$ $\alpha \in {\mathcal {A}}$ $U_{\alpha }$ ${\mathcal {A}}=\{{\text{name}},{\text{age}},{\text{income}}\}$ $U_{\text{name}}$ $U_{\text{age}}$ $U_{\text{income}}$

ให้. $x$ -tupleคือฟังก์ชัน $f$ โดยที่ และสำหรับแต่ละเซตของ $x$ -tuple ทั้งหมดจะถูกแทนด้วย. สำหรับ $x$ -tuple $f$ และเซตย่อย ข้อจำกัดจะถูกกำหนดให้เป็น $y$ -tuple $g$ โดยที่สำหรับทุก. $x\subseteq {\mathcal {A}}$ ${\hbox{dom}}(f)=x$ $f(\alpha )\in U_{\alpha }$ $\alpha \in x$ $E_{x}$ $y\subseteq x$ $f[y]$ $g(\alpha )=f(\alpha )$ $\alpha \in y$

ความสัมพันธ์ $R$ บน $x$ คือเซตของ $x$ -tuple กล่าวคือ เซตย่อยของy เซตของแอตทริบิวต์ $x$ เรียกว่าโดเมนของ $R$ และใช้ สัญลักษณ์ แทนการฉายภาพของ $R$ ไปยัง $y$ นิยามได้ดังนี้: $E_{x}$ $d(R)$ $y\subseteq d(R)$

\pi _{y}(R):=\{f[y]\mid f\in R\}.

การเชื่อมต่อ (Join)ของความสัมพันธ์ $R$ บนตัวแปร $x$ และความสัมพันธ์ $S$ บนตัวแปร $y$ ถูกกำหนดดังนี้:

R\bowtie S:=\{f\mid f\quad (x\cup y){\hbox{-tuple}},\quad f[x]\in R,\;f[y]\in S\}.

ตัวอย่างเช่น ให้ $R$ และ $S$ เป็นความสัมพันธ์ดังต่อไปนี้:

R={\begin{array}{|c|c|}\hline {\text{name}}&{\text{age}}\\\hline {\text{A}}&{\text{34}}\\{\text{B}}&{\text{47}}\\\hline \end{array}}\qquad S={\begin{array}{|c|c|}\hline {\text{name}}&{\text{income}}\\\hline {\text{A}}&{\text{20,000}}\\{\text{B}}&{\text{32,000}}\\\hline \end{array}}

ดังนั้นจุดเชื่อมต่อของ $R$ และ $S$ คือ:

R\bowtie S={\begin{array}{|c|c|}\hline {\text{name}}&{\text{age}}&{\text{income}}\\\hline {\text{A}}&{\text{34}}&{\text{20,000}}\\{\text{B}}&{\text{47}}&{\text{32,000}}\\\hline \end{array}}

ฐานข้อมูลเชิงสัมพันธ์ที่มีการเชื่อมต่อแบบธรรมชาติ (natural join) เป็นการรวมกัน และการฉายภาพแบบปกติ $π$ นั้นเป็นพีชคณิตสารสนเทศ การดำเนินการต่างๆ ได้รับการกำหนดไว้อย่างดีแล้ว เนื่องจาก $\bowtie$

$d(R\bowtie S)=d(R)\cup d(S)$
ถ้าเช่นนั้น $x\subseteq d(R)$ $d(\pi _{x}(R))=x$

เป็นที่เห็นได้ชัดว่าฐานข้อมูลเชิงสัมพันธ์นั้นสอดคล้องกับสัจพจน์ของพีชคณิตสารสนเทศที่มีป้ายกำกับ:

เซมิกรุป: $(R_{1}\bowtie R_{2})\bowtie R_{3}=R_{1}\bowtie (R_{2}\bowtie R_{3})$ และ $R\bowtie S=S\bowtie R$
การถ่ายทอด: ถ้าเช่นนั้น $x\subseteq y\subseteq d(R)$ $\pi _{x}(\pi _{y}(R))=\pi _{x}(R)$
การผสมผสาน: ถ้าและแล้ว $d(R)=x$ $d(S)=y$ $\pi _{x}(R\bowtie S)=R\bowtie \pi _{x\cap y}(S)$
ความคงที่: ถ้าเช่นนั้น $x\subseteq d(R)$ $R\bowtie \pi _{x}(R)=R$
สนับสนุน: ถ้าเช่นนั้น $x=d(R)$ $\pi _{x}(R)=R$

การเชื่อมต่อ

พีชคณิตการประเมินค่า: การละทิ้งสัจพจน์ความเท่าเทียมกันนำไปสู่พีชคณิตการประเมินค่าสัจพจน์เหล่านี้ได้รับการแนะนำโดย ( Shenoy & Shafer 1990 ) เพื่อขยายรูปแบบการคำนวณเฉพาะที่ ( Lauritzen & Spiegelhalter 1988 ) จากเครือข่ายเบย์เซียนไปสู่รูปแบบทั่วไปมากขึ้น รวมถึงฟังก์ชันความเชื่อ ศักยภาพความเป็นไปได้ ฯลฯ ( Kohlas & Shenoy 2000 ) สำหรับรายละเอียดเพิ่มเติมในรูปแบบหนังสือ โปรดดูPouly & Kohlas (2011)
โดเมนและระบบสารสนเทศ: พีชคณิตสารสนเทศแบบกระชับ ( Kohlas 2003 ) เกี่ยวข้องกับโดเมน Scottและระบบสารสนเทศ Scott ( Scott 1970 ); ( Scott 1982 ); ( Larsen & Winskel 1984 )
ข้อมูลที่ไม่แน่นอน: ตัวแปรสุ่มที่มีค่าในพีชคณิตสารสนเทศแสดงถึงระบบการโต้แย้งเชิงความน่าจะเป็น ( Haenni, Kohlas & Lehmann 2000 )
ข้อมูลเชิงความหมาย: พีชคณิตสารสนเทศนำเสนอความหมายโดยการเชื่อมโยงข้อมูลกับคำถามผ่านการเน้นและการรวมกัน ( Groenendijk & Stokhof 1984 ); ( Floridi 2004 )
การไหลเวียนของข้อมูล: พีชคณิตสารสนเทศมีความเกี่ยวข้องกับการไหลของสารสนเทศ โดยเฉพาะอย่างยิ่งการจำแนกประเภท ( Barwise & Seligman 1997 )
การผุพังของต้นไม้: พีชคณิตสารสนเทศถูกจัดระเบียบเป็นโครงสร้างแบบลำดับชั้นคล้ายต้นไม้ และถูกแบ่งย่อยออกเป็นปัญหาที่เล็กกว่า
ทฤษฎีเซมิกรุป: ...
แบบจำลององค์ประกอบ: แบบจำลองดังกล่าวอาจถูกกำหนดขึ้นภายในกรอบของพีชคณิตสารสนเทศ: https://arxiv.org/abs/1612.02587
รากฐานเชิงสัจพจน์ที่ขยายเพิ่มเติมของพีชคณิตสารสนเทศและพีชคณิตการประเมินค่า: แนวคิดเรื่องความเป็นอิสระแบบมีเงื่อนไขเป็นพื้นฐานสำหรับพีชคณิตสารสนเทศ และมีรากฐานเชิงสัจพจน์ใหม่ของพีชคณิตสารสนเทศที่อิงตามความเป็นอิสระแบบมีเงื่อนไข ซึ่งเป็นการต่อยอดจากรากฐานเดิม (ดูด้านบน) สามารถดูได้ที่: https://arxiv.org/abs/1701.02658

รากฐานทางประวัติศาสตร์

สัจพจน์สำหรับพีชคณิตสารสนเทศได้มาจากระบบสัจพจน์ที่เสนอไว้ใน (Shenoy and Shafer, 1990) ดูเพิ่มเติมที่ (Shafer, 1991)