Khóa luận Ứng dụng Relational Interface cho Java

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Đỗ Duy Hưng ỨNG DỤNG RELATIONAL INTERFACE CHO JAVA KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin Cán bộ hướng dẫn: Ths. Phạm Thị Kim Dung HÀ NỘI – 2010 Lời cảm ơn Trước tiên, tôi xin gửi lời cảm ơn và lòng biết ơn sâu sắc đến thạc sỹ Phạm Thị Kim Dung, người đã tận tình chỉ bảo hướng dẫn tôi trong suốt quá trình thực hiện khoá luận tốt nghiệp. Tôi xin bày tỏ lời cảm ơn sâu sắc đến các thầy cô giáo đã giảng dạy tôi trong suốt bốn năm học qua, đã cho tôi nhiều kiến thức quý báu để tôi vững bước trên con đường học tập của mình. Tôi xin gửi lời cảm ơn tới các bạn trong lớp K51CB, và K51CNPM đã ủng hộ khuyến khích tôi trong suốt quá trình học tập tại trường. Và cuối cùng, tôi xin bày tỏ niềm biết ơn vô hạn tới bố mẹ, và những người bạn thân luôn bên cạnh, động viên tôi trong suốt quá trình thực hiện khoá luận tốt nghiệp. Hà Nội, ngày 22 tháng 05 năm 2010 Sinh Viên Đỗ Duy Hưng TÓM TẮT NỘI DUNG Hiện nay, thiết kế dựa trên thành phần (Component-based design) đang được ứng dụng và phát triền mạnh vì những lợi ích mà nó mang lại cho ngành công nghệ phần mềm. Thiết kế dựa trên thành phần giúp cho việc xây dựng các hệ thống phức tạp, như là hệ thống nhúng, hệ thống vật lý trở nên hiệu quả và đáng tin cậy. Với kích cỡ và độ phức tạp lớn của hệ thống này không cho phép thiết kế toàn bộ từ đầu, hoặc xây dựng nó như là một đơn vị đơn lẻ. Thay vào đó, hệ thống phải được thiết kế như là một tập hợp các thành phần, một số được xây dựng từ đầu, một số kế thừa lại. Giao diện (Interface) đóng một vai trò quan trọng trong thiết kế dựa trên thành phần vì chúng cung cấp phương tiện để mô tả cho thành phần. Một interface có thể được xem như là một bản tóm tắt, một đại diện của thành phần: giữ lại các thông tin cần thiết của thành phần, giấu thông tin không cần thiết và làm cho mô tả thành phần trở nên đơn giản và hiệu quả hơn. Trong khóa luận tốt nghiệp này, bằng việc sử dụng lý thuyết về relational interface, tôi xây dựng một công cụ tự động phân tích, trích rút các thành phần có trong file mã nguồn Java và biến đổi nó thành các relational interface, thực hiện việc kết hợp tự động các interface này với nhau. Để từ đó, ta có thể biết được khả năng kết hợp của các thành phần này với nhau. Interface mới được kết hợp vẫn giữ nguyên tính chất của các interface cũ. Qua đó, ta cũng có thể dự đoán được giá trị đầu ra của các thành phần nếu biết được giá trị đầu vào thông qua các tính chất. MỤC LỤC Bảng các kí hiệu nghĩa tiếng anh Kí hiệu Diễn giải Input Đầu vào Output Đầu ra Well-formed Định dạng hoàn chỉnh Well-formable Định dạng có thể hoàn chỉnh Interface Giao diện Relational Interface Giao diện quan hệ Stateless Phi trạng thái Stateful Có trạng thái Feedback Phản hồi Formal methods Các phương pháp hình thức Formal specification Đặc tả hình thức Assumption Giả thiết Guarantee Bảo đảm Refinement Làm mịn Danh mục hình vẽ Hình 3.1: Sơ đồ một interface cho ví dụ 4 17 Hình 3.2: Sơ đồ một interface với feedback 19 Hình 4.1: Hàm parse() trong lớp JavaFile.java 32 Hình 4.2: Hàm parse() trong lớp JavaClass.java 33 Hình 4.3: Hàm Tools.rename(JavaMethod jm) 34 Hình 4.4: Hàm Tools. getRInterfaceList(JavaClass jc) 37 Hình 4.5: Hàm Shorten trong lớp Expression.java 39 Hình 5.1: Giao diện làm việc của Netbeans 41 Hình 5.2: Minh họa cách cài đặt thư viện (1) 42 Hình 5.3: Minh họa cách cài đặt thư viện (2) 42 Hình 5.4: Kết quả thử nghiệm 5.3.1 đối với hàm main 43 Hình 5.5: Kết quả thử nghiệm 5.3.1 đối với hàm cong 43 Hình 5.6: Kết quả thử nghiệm 5.3.1 đối với hàm tru 43 Hình 5.7: Kết quả thử nghiệm 5.3.1 đối với hàm nhan 44 Hình 5.8: Kết quả thử nghiệm 5.3.1 đối với hàm chia 44 Hình 5.9: Kết quả thử nghiệm 5.3.1 đối với hàm triTuyetDoi 44 Hình 5.10: Kết quả thử nghiệm 5.3.2 với hàm cong 45 Hình 5.11: Kết quả thử nghiệm 5.3.2 đối với hàm tru 45 Hình 5.12: Kết quả thử nghiệm 5.3.2 đối với hàm nhan 45 Hình 5.13: Kết quả thử nghiệm 5.3.2 đối với hàm chia 45 Hình 5.14: Kết quả thử nghiệm 5.3.2 đối với hàm triTuyetDoi 45 Hình 5.15: Biểu đồ interface cho kết hợp chia(cong(a, b), tru(a, b)) 46 Hình 5.16: Kết quả thử nghiệm 5.3.3 đối với hàm main 47 CHƯƠNG 1: MỞ ĐẦU Đặt vấn đề Hiện nay, với sự phát triển mạnh mẽ của công nghệ thông tin, nhiều hệ thống lớn được xây dựng nên nhằm mục đích giải quyết những bài toán với độ phức tạp tương đương. Với kích thước và độ phức tạp của những hệ thống như vậy, đòi hỏi phải có một phương pháp thiết kế hợp lý, hiệu quả và đáng tin cậy. Phương pháp thiết kế dựa trên thành phần đáp ứng được yêu cầu này, bởi vì, thay vì phải thiết kế toàn bộ từ đầu, hệ thống được thiết kế như là một tập các thành phần. Các thành phần này hoặc là được xây dựng lại từ đầu, hoặc là được thừa kế từ những thành phần khác. Do vậy mỗi thành phần phải có tính độc lập cao và chuẩn đặc tả rõ ràng. Điều này thường được thể hiện qua interface (giao diện) của thành phần. Một interface có thể coi như một đặc tả của một thành phần. Việc kết hợp các thành phần cũng thông qua việc kết hợp các interface. Nội dung bài toán Trong phương pháp thiết kế dựa trên thành phần, interface chính là đặc tả của thành phần, nên quá trình đặc tả interface là một trong những bước quan trọng, cần được quan tâm. Do vậy, trong khóa luận này tôi muốn đề cập đến phương pháp xây dựng interface cho mỗi thành phần một cách tự động. Hiện nay có rất nhiều lý thuyết về interface được đưa ra để mô tả thành phần. Tuy nhiên, các các interface này thường gặp phải một số khó khăn như không bắt được quan hệ giữa giá trị đầu vào và đầu ra, hay khó khăn trong việc kết hợp các interface với nhau. Để khắc phục những nhược điểm này, tôi đề xuất việc sử dụng relational interface trong đặc tả interface cho mỗi thành phần. Nhiệm vụ chính của bài toán là xây dựng công cụ chuyển đổi các thành phần có trong mã nguồn của ngôn ngữ lập trình hướng đối tượng thành relational interface, rồi kết hợp các interface này với nhau một cách tự động. Cấu trúc khóa luận Phần còn lại của khóa luận được cấu trúc như sau: Chương 2: Giới thiệu chung về kỹ nghệ hướng thành phần, phương pháp hình thức, đặc tả hình thức, đặc tả giao diện. Một số loại interface (giao diện) cùng với những ưu điểm, hạn chế của chúng. Giới thiệu chung về relational interface. Chương 3: Mô tả nội dung lý thuyết của relational interface, về môi trường và khả năng lắp ghép. Lý thuyết về kết hợp relational interfaces [7]. Chương 4: Áp dụng lý thuyết về relational interface và một số lý thuyết khác để xây dựng công cụ tự động chuyển đổi từ file mã nguồn Java sang relational interface. Chương 5: Thử nghiệm công cụ và đánh giá. Chương 6: Kết luận. CHƯƠNG 2: GIỚI THIỆU CHUNG VỀ ĐẶC TẢ VÀ GIAO DIỆN Công nghệ phần mềm hướng thành phần Công nghệ phần mềm hướng thành phần (component-based software engineering [8]) là một trong những bước tiến của quá trình sản xuất phần mềm trong công nghiệp. Nhờ vào đó, việc sản xuất phần mềm trở nên phát triển mạnh mẽ. Ta cùng nhìn lại các ngành kĩ nghệ khác. Mỗi ngành kĩ nghệ đều có riêng cho mình một số thành tố cơ bản. Sự khác biệt của công nghệ phần mềm so với các ngành kĩ nghệ khác là ở chỗ sự lắp ráp các thành phần khác nhau của phần mềm còn mang tính tùy biến. Nghĩa là đưa ra cùng hai linh kiện (hay thành phần) phần mềm với cùng một thiết kế, hai lập trình viên có thể lắp ráp theo cách khác nhau. Nhận thức được điều này, kỹ nghệ hướng thành phần trong sản xuất phần mềm được bắt đầu áp dụng. Điều cơ bản mà mỗi thành phần phải có là: tính độc lập cao và có chuẩn đặc tả rõ ràng cho từng thành. Đặc tả này phải không phụ thuộc vào cấu trúc bên trong của thành phần. Dựa trên 2 điểm cơ bản này của một thành phần, điều đầu tiên khi bắt đầu thiết kế thành phần là quan tâm đến đặc tả của thành phần. Điều này thường được thể hiện qua interface (giao diện). Tiếp theo, tính độc lập của thành phần. Do tất cả các thành phần được kết nối qua interface thay vì trực tiếp, mọi quá trình xây dựng bên trong thành phần đều được khép kín. Sự phụ thuộc sẽ chủ yếu dựa vào interface. Vì vậy sẽ tách được sự phụ thuộc về cách xây dựng bên trong. Việc xây dựng thành phần có thể bằng bất cứ phương pháp nào dù là lập trình cấu trúc hay lập trình hướng đối tượng. Đặc tả hình thức Phương pháp hình thức bao gồm một số các hoạt động khác nhau như: đặc tả hệ thống hình thức, dẫn chứng và phân tích đặc tả, phát triển chuyển đổi, và kiểm chứng chương trình. Tất cả các hoạt động này đều phụ thuộc vào đặc tả hình thức của phần mềm. Một đặc tả hình thức phần mềm là một đặc tả được thể hiện bằng một loại ngôn ngữ mà từ vựng, cú pháp, ngữ nghĩa của nó được định nghĩa một cách hình thức. Điều này có nghĩa là ngôn ngữ đặc tả phải được dựa trên các khái niệm toán học với thuộc tính đã được nghiên cứu và dễ hiểu [3]. Các phương pháp hình thức Trong tin học, thuật ngữ phương pháp hình thức [8] (ngôn ngữ hình thức, đặc tả hình thức,…) thường được dùng để chỉ các kỹ thuật dựa trên cơ sở toán học dùng trong quá trình mô tả chi tiết (đặc tả), phát triển và kiểm chứng các hệ thông phần mềm cũng như phần cứng. Cách tiếp cận này thường áp dụng cho các hệ thống có kết cầu chặt chẽ, đòi hỏi độ tin cậy và tính an toàn cao, để đảm bảo rằng trong quá trình xây dựng, phát triển hệ thống không xảy ra một lỗi nào, hoặc nếu có thì cũng là rất ít. Các phương pháp hình thức đặc biệt hiệu quả trong các giai đoạn đầu của quá trình xây dựng hệ thống (thường ở giai đoạn xác định yêu cầu và đặc tả hệ thống), tuy nhiên, chúng cũng có thể được dùng trong toàn bộ quy trình phát triển hệ thống. Các phương pháp hình thức có thể được xếp loại theo 3 mức độ như sau: Mức 0: Đặc tả hình thức được sử dụng để đặc tả hệ thống trước khi phát triển nó. Trong nhiều trường hợp thì việc sử dụng phương pháp hình thức ở giai đoạn này tỏ ra đặc biệt hiệu quả, nhất là về mặt chi phí. Mức 1: Phát triển và kiểm chứng hình thức có thể được áp dụng để tạo ra một chương trình (hay một hệ thống) một cách tự động, dựa trên các đặc tả hình thức đã có trước đó. Quá trình này đặc biệt thích hợp đối với các hệ thống đòi hỏi độ tin cậy và tính an toàn cao. Mức 2: Chứng minh tự động. Đặc tả Mô tả các cấu trúc, hoạt động của các sự vật hiện tượng, quá trình nào đó. Việc mô tả này có thể ở mức độ khái quát, nhưng cũng có thể là những mô tả ở mức độ hết sức chi tiết. Có nhiều ngôn ngữ cho phép đặc tả: Ngôn ngữ tự nhiên Ngôn ngữ toán Ngôn ngữ lập trình Ngôn ngữ hình thức Đặc tả hình thức Đặc tả hình thức là đặc tả với các tính chất: Chính xác và nhất quán. Ngắn gọn nhưng đầy đủ. Có thể xử lý bởi máy tính. Đặc tả hình thức có các ứng dụng như sau: Sử dụng trong giai đoạn phân tích, thiết kế, nhằm mục đích tạo ra các phác hoạ chi tiết, cụ thể và chặt chẽ về hệ thống sẽ được xây dựng. Trong quá trình xây dựng hệ thống, các đặc tả này sẽ là công cụ định hướng để đảm bảo hệ thống được xây dựng một cách phù hợp và đầy đủ. Sau khi hệ thống được xây dựng thì đặc tả sẽ đóng vai trò là thước đo để kiểm chúng, khẳng định hệ thống được tạo ra có đúng đắn và tin cậy hay không. Giao diện Đặc tả giao diện Các hệ thống lớn thường được chia thành các hệ thống nhỏ và các hệ thống nhỏ này được phát triển độc lập. Các hệ thống nhỏ tận dụng các hệ thống nhỏ khác, nên một phần quan trọng của quá trình đặc tả là định nghĩa những giao diện của hệ thống nhỏ. Ngay khi các giao diện được định nghĩa và chấp nhận, các hệ thống nhỏ có thể được phát triển độc lập. Giao diện của hệ thống nhỏ thường được định nghĩa như là một tập các đối tượng hoặc kiểu dữ liệu trừu tượng. Chúng mô tả dữ liệu và những hoạt động mà có thể được truy cập thông qua giao diện của các hệ thống nhỏ. Do đó, một đặc tả giao diện của hệ thống nhỏ có thể được tạo nên bằng cách kết hợp đặc tả của các thành phần được tạo nên bởi các giao diện hệ thống nhỏ [3]. Thành phần và giao diện Một cách chung mô tả cấu trúc của hệ thống là sơ đồ khối. Một sơ đồ khối bao gồm các thực thể gọi là các khối được kết nối với nhau bởi một liên kết. Cách mô tả này phân loại một cấu hình (mạng) cho truyền thông giữa các khối. Một khối có thể trình bày một thành phần vật lý hoặc logic, ví dụ như một phần của phần cứng hoặc phần mềm. Nhưng phổ biến hơn là nó trình bày một mô tả trừu tượng của thành phần hoặc một mô tả của interface thành phần. Mô tả thành phần trả lời cho câu hỏi: Nó làm gì ?does it do? Và một mô tả interface trả lời cho câu hỏi: nó được sử dụng như thế nào? Mô tả thành phần có thể rất gần với thành phần cơ bản, hoặc nó có thể chỉ định một vài thuộc tính đơn của thành phần cơ bản. Các mô tả của interface cũng có thể là chi tiết nhiều hoặc ít, nhưng chúng phải bao gồm đầy đủ thông tin để xác định các thành phần cơ sở được kết hợp và liên kết như thế nào. Và giống như bất kỳ việc trừu tượng hóa tốt nào, chúng không nên bao gồm nhiều thông tin. Các nhà thiết kế thành phần thường tạo nên các giả định về môi trường mà trong đó một thành phần có thể được triển khai [5]. Các loại interface Interface automata: có thể được sử dụng để bắt các mối quan hệ giữa input – output trong mô hình song song không đồng bộ và trong hầu hết các kiểu thực thi [4]. Relational nets: là một mạng của các tiến trình mà không xác định liên kết giữa giá trị input và giá trị output [5]. Assume/guarantee (A/G) interfaces: phân chia giữa giả thiết các giá trị đầu vào dựa trên các đảm bảo về giá trị đầu ra, nhưng interface này không bắt được mối quan hệ giữa các input và output [5]. Extended interfaces: giống với relational interface, tuy nhiên interface này không được đánh giá cao bởi hạn chế tính chất của những bước làm mịn và thực thi độc lập là không có[6]. Moore interfaces: được định nghĩa bởi công thức ϕi và ϕo. Trong đó công thức ϕi chỉ rõ giá trị hợp lệ của các biến input tại các trạng thái tiếp theo khi mà trạng thái hiện tại được cho trước, và công thức ϕo chỉ rõ giá trị hợp lệ của các biến output tại các trạng thái tiếp theo khi mà trạng thái hiện tại được cho trước. Công thức này không cho phép miêu tả mỗi quan hệ giữa input và output tại cùng một trạng thái [2]. Hạn chế của các interface trên là không bắt được mối quan hệ giữa input và output. Lý thuyết về relational interface giải quyết các vấn đề đó bằng việc xây dựng một thành phần ξ trong interface. ξ là tập tất các quan hệ giữa input và output, mô tả ràng buộc giữa input và môi trường. Việc kết hợp tổng quát các interfaces, có thể đạt được thông qua hai toán tử có tên là parallel conposition ( kết hợp song song ) và connection ( kết nối ) [5],[6]. Điều này cho phép tạo ra các feedback loop (phản hồi lặp) tùy ý. Khi nghiên cứu về relational interface, có rất nhiều vấn đề nảy sinh từ feekback loop đồng bộ. Có thể tránh vẫn đề được nảy sinh bởi feekback loop bằng cách hạn chế các trường hợp mà feedback loop được cho phép. Cụ thể, ta cho phép một output của một interface I được kết nối với một trong các input x của nó chỉ trong trường hợp I là Moore đối với x, có nghĩa ràng buộc của I không phụ thuộc vào x. Statelful và stateless interface [7] nói đến hai dạng của interface là stateless interface ( giao diện phi trạng thái ) và stateful interface ( giao diện có trạng thái ). Stateful interface, một ràng buộc có thể khác nhau tại mỗi trạng thái khác nhau. Stateless interface có thể được xem như một trường hợp đặc biệt của stateful interface khi ràng buộc là giống nhau ở tất cả các trạng thái. Trong trường hợp stateful, ta phân biệt giữa well-formed interface và well-formable interface (hai khái niệm này trùng khớp trong trường hợp stateless interface). Với well-formed interface, các ràng buộc luôn luôn được thỏa mãn tại mọi trạng thái có thể đạt được (reachable state). Well-formable interface không nhất thiết phải là well-formed, nhưng mà có thể được chuyển thành well-formed bằng cách hạn chế một cách hợp lý các input. Relational interface Trong khóa luận này, tôi muốn đề cập đến relational interface [7]. Relational interface là một interface chỉ ra những relation ( quan hệ ) giữa những input và output. Xem xét ví dụ về một thành phần đồng bộ sẽ lấy input là một số n ≥ 0 và trả về output là n + 1. Interface cho mỗi thành phần có thể được mô tả như là một quan hệ nhị phân giữa input và output: các relation chứa tất cả các cặp (n, n+1) với n ≥ 0. Mỗi một relation có thể được hiểu như một ràng buộc giữa thành phần và môi trường ( environment ) của nó: ràng buộc chỉ ra rằng với mỗi input hợp lệ, thoải mãn điều kiện mà môi trường cung cấp cho thành phần thì sẽ có nhưng output hợp lệ được tạo ra từ thành phần đó. Tính năng nổi trội của relational interface là ở việc giải quyết vấn đề bắt được quan hệ giữa input và output. Ngoài ra, lý thuyết về composition (kết hợp), connection (kết nối), feedback loop (phản hồi lặp) có trong relational interface có thể dẫn tới những khẳ năng: Thiết kế phần mềm dựa trên relational interface là sự kết hợp giữa các interface mà trong đó, các ràng buộc phải được thỏa mãn, hoặc có thể thỏa mãn. Ta cũng có thể kiểm chứng và dự đoán được khả năng kết hợp của các interface lại với nhau. Ngoài ra, dựa trên các rằng buộc, ta cũng có thể dự đoán được kết quả đầu ra từ dữ liệu đầu vào. Khả năng tối ưu hóa thiết kế phần mềm bằng tính chất refinement và shared-refinement. Một khái niệm quan trọng của relational interface mà đã được nhắc đến ở trên đó là well-formed và well-formable. Điều này giúp cho các thành phần, hay nói đúng hơn là các relational interface được liên kết hay có thể liên kết được với nhau. Với những định hướng này, và do giới hạn của khóa luận, tôi sẽ giải quyết vấn đề a, b, c. Vấn đề và những chế còn lại sẽ được giải quyết trong những nghiên cứu sau này. CHƯƠNG 3: NỘI DUNG LÝ THUYẾT VỀ RELATIONAL INTERFACE Tóm tắt về relational interface đã mô tả ở phần 2.3.5, trong chương này, tôi sẽ đề cập đến nội dung lý thuyết về relational interface. Nội dung lý thuyết này được sử dụng từ [7]. Sơ bộ về bài viết và các ký hiệu Trong bài viết này ta sử dụng first-order logic (FOL) như là một ngôn ngữ để mô tả ràng buộc. Ta sử dụng 2 hằng số logic đó là true và false. Các ký hiệu: ¬ : phép phủ định, ∧ : phép và, ∨ : phép hoặc, → : phép suy ra, ≡ : phép tương đương, ∀ : với mọi và ∃ : tồn tại. Chúng ta sử dụng kí hiệu ≔ để định nghĩa cho một khái niệm hoặc một kí hiệu mới, ví dụ: x0 ≔ max {1, 2, 3} chỉ ra rằng x0 là giá trị lớn nhất của tập {1, 2, 3} Gọi V là tập hữu hạn các biến. Một thuộc tính trên V là một công thức FOL ϕ như vậy thì với mọi biến tự do của ϕ đều thuộc V. Một tập tất cả các thuộc tính trên V được kí hiệu là ℱ(V). Coi ϕ là một thuộc tính trên V và V’ là tập con hữu hạn của V, V’ = {v1, v2, …, vn}. Khi đó, ∃V’ : ϕ là một cách viết ngắn gọn của ∃v1 : ∃v2 : … : ∃vn : ϕ. Tương tự như vậy, ∀V’ : ϕ là cách viết ngắn gọn của ∀v1 : ∀v2 : … : ∀vn : ϕ. Chúng ta hoàn toàn có thể giả định rằng tất cả các biến là kiểu, có nghĩa là tất cả các biến được kết hợp với một tập xác định nào đó. Một phép gán trên một tập các biến V là một hàm cho tướng ứng mỗi biến trong V với một giá trị nào trong tập xác định của biến đó. Một bộ các phép gán trên V được kí hiệu là 𝒜(V). Nếu a là một phép gán ( assignment ) trên V1 và b là một là một phép gán trên V2 ,và V1 và V2 là 2 tập tách rời thì chúng ta sẽ sử dụng (a, b) để kí hiệu một phép gán kết hợp trên V1 ∪ V2. Một công thức ϕ là thỏa mãn nếu ở đó tồn tại một phép gán a trên các biến tự do của ϕ để a thỏa mãn ϕ, được kí hiệu là a ⊨ ϕ. Một công thức ϕ là hợp lệ nếu nó được thỏa mãn bởi mọi phép gán. Nếu coi S là một tập hợp, S* là kí hiệu của tập hợp của tất cả các chuỗi hữu hạn được tạo nên bởi các phần tử trong S. S* bao gồm cả các chuỗi rỗng, kí hiệu là ε. Nếu s, s’ thuộc S* thì s ∙ s’ là phép nối của s và s’. |s| kí hiệu độ dài của s ∈ S*, với |ε| = 0 và |s ∙ a| = |s| + 1, với a ∈ S. Nếu s = a1a2…an, thì phần tử thứ i của chuỗi, ai, được kí hiệu là si, với i = 1, … , n. Relational interfaces Định nghĩa 1 (Relational interface): một relational interface (hay một interface đơn giản) là 1 bộ I = ( X, Y, ξ ). Trong đó X, Y là 2 tập hữu hạn và tách rời của các biến